정렬 알고리즘이란?(What is Sorting Algorithm?)

Sorting이란, 순서없이 나열된 요소들(elements,key)을 특정한 기준(내림차순 or 오름차순)에 따라 비교하여 재배열(rearrange)하는 것을 말한다.

---

정렬 알고리즘(Sorting Algorithm)

그렇다면 왜 정렬알고리즘을 사용할까? 정렬알고리즘은 자료탐색에 있어서 필수적이다.

 

예를 들어, 사전에서 단어를 찾고자 할 때 정렬되어 있지 않다면 찾고자하는 단어를 구하기 까지 오랜시간이 걸리게 된다.(비효율적이며 정보의 양이 많아지면 불가능해진다.)

 

여러 Sorting Algorithm의 분류와 특징들을 통해 상황에 알맞는… 효율적인 알고리즘을 선택할 수 있어야한다.

Sorting 기준

1. 오름차순(ascending) : 요소들이 증가하는 순서대로 재배열
2. 내림차순(descending) : 요소들이 감소하는 순서대로 재배열

Sorting 안정성(Stability)

A sorting method is stable if it preserves the relative order of equal keys in the array.

정렬 후에도 같은 키들의 상대적인 순서가 정렬 이전과 동일하게 유지되는 정렬 방법을 안정정렬이라 말하며, 삽입정렬(Insertion Sort)과 합병정렬(Merge Sort)이 이에 해당된다.

Sorting의 분류

1. 정렬이 수행되는 공간에 따른 분류
2. 정렬을 실행하는 방법에 따른 분류

수행되는 공간에 따른 분류

1. 내부정렬(Internal Sort)
   • 정렬하고자 하는 모든 요소들을 메모리에 올려 정렬을 수행
2. 외부정렬(External Sort)
   • 정렬하고자 하는 요소들이 너무 많아 일부만 따로 정렬 후 이를 다시 합하는 정렬

정렬을 실행하는 방법에 따른 분류

1. 교환(Exchange)
   1. 키 값을 비교하여 교환
   2. 버블정렬, 퀵정렬
2. 삽입(Insertion)
   1. 키 값을 비교하여 자료를 삽입
   2. 삽입정렬, 셀정렬
3. 병합(Merging)
   
   1. 키 값을 비교하고 자료를 병합(자료를 나눈 후 다시 합침)
   2. 2-way 정렬, n-way 정렬
4. 분배(Distribution)
   1. 키 값을 여러 개의 부분 집합으로 분배후 정렬
   2. 기수정렬
5. 선택(Selection)
   1. 특정 자료구조를 통해 정렬
   2. 선택정렬, 힙정렬

In-place sorting : 주어진 입력 배열 이외의 추가적인 메모리를 요구하지 않는 정렬로 대표적으로 선택정렬, 삽입정렬, 버블정렬 등이 있다.(swap을 위한 메모리를 의미하는 것이 아님)

정렬 알고리즘 비교

• 속도비교

sort speed

---

삽입정렬(Insertion Sort)

Insertion Sort : 원소의 적당한 위치를 찾아서 보내주는 정렬

개념

해당 value(원소)를 넣을 index(위치)를 찾아 value(원소)를 넣어주는 알고리즘으로 index(위치)를 정해졌는가? 위치를 찾는 것인가?

그 여부가 selection sort와의 차이점이다.

Insertion Sort

 

특징

• 제자리정렬(in-place sorting) 알고리즘
• 해당 자료의 위치를 찾아 해당위치에 삽입해주고 그 뒤 배열은 뒤로 한개의 index씩 밀어준다.
• 오름차순 기준으로 더 작거나 같은 value(원소)가 나오면 멈춘다.

Source Code

int* insertion_sort(int* arr) {
    for (int i = 0; i < 199; i++) {
        for (int j = i + 1; j > 0; j--) {
            if (arr[j-1] > arr[j]) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
            else {
                break;
            }   
        }
    }
    return arr;
}

복잡도

1. 시간복잡도 : i ~ n-1 까지의 모든 인덱스를 순회하며 최솟값을 찾기 때문에 다음의 시간복잡도를 갖는다
   • Best Case($ Big-
2. 공간복잡도 :