[알고리즘은 처음이라] Insertion Sort(삽입 정렬)

 

 

🌈요약

Insertion Sort란?
이전의 원소들과 비교해 삽입할 위치를 정한 후 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입해 정렬하는 알고리즘

시간복잡도
최악, 평균의 경우 O(n^2)
- 역으로 정렬 되어 있는 경우 

평균, 최선의 경우
- 이미 정렬이 되어 있는 경우

공간복잡도
O(n)
- 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되는 제자리 정렬

 

 

---

Selection Sort (선택 정렬)이란?

최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될만큼 좋은 정렬 알고리즘이다.

2번째 원소부터 시작해 이전의 원소들과 비교해 삽입할 위치를 정한 후 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입해 정렬하는 알고리즘

 

 

진행 과정(오름차순)

1. 1번 index의 값을 temp에 저장한다
2. temp와 이전에 있는 원소들의 값을 비교하며 삽입한다.
3. 1번으로 돌아가 다음 index의 값을 temp에 저장하고 반복한다. 

 

구현(Java)

void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index]; // 현재 index의 값을 저장
      int prev = index - 1; // 현재 index의 이전 위치를 저장
      while( (prev >= 0) && (arr[prev] > temp) ) {    // 2.
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}

 

1. 두번째 위치(1번 index)부터 탐색을 시작한다. 

 

2.prev가 음수가 되지 않고, prev 위치의 값이 temp보다 크면 값을 교환하고 prev를 한 칸 앞으로 이동한다.

 

3. 2번에서 반복문이 끝나게 되면 prev는 temp 값보다 작은 값 중 제일 큰 값의 위치(index)를 가리킨다. (prev+1)에 temp를 삽입한다.

 

 

시간복잡도

최악의 경우

역으로 정렬되어 있는 경우 

(n-1) + (n-2) + (n-3) + ... 2 + 1 >> n(n-1)/2 이기 때문에 O(n^2)

 

모두 정렬이 되어 있는 경우, 한 번씩만 비교하기 때문에 O(n)의 시간복잡도를 가진다.

이미 정렬 되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에, 탐색을 제외한 오버헤드가 매우 적기 때문에 현실적으로 최고의 정렬 알고리즘이 된다.

 

따라서 최선의 경우에는 O(n), 평균과 최악의 경우 O(n^2)의 시간복잡도를 갖게 된다.

 

 

 

공간복잡도

주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되기 때문에 O(n)

 

 

장점

• 알고리즘이 단순하다.
• 대부분의 원소가 정렬되어 있는 경우 매우 효율적일 수 있다.
• 정렬하고자하는 배열 안에서 교환하는 방식이기 때문에 다른 메모리 공간을 필요로 하지 않는다
  >> 제자리 정렬(in - place sorting)
• 안정 정렬(Stable Sort)이다.
• Selection Sort, Bubble Sort 같은 O(n^2) 알고리즘에 비해 상대적으로 빠르다

 

단점

• 시간복잡도가 최악, 평균 모두 O(n^2)으로 굉장히 비효율적이다.
• Bubble Sort, Selection Sort 와 마찬가지로 배열의 길이가 길어질수록 비효율적이다