1. 선택정렬

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

1.1 정렬과정

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다. (pass)
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

1.2 코드

1.2.1 Java

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

1.2.2 Python

def selection_sort(a):
    size = len(a)
    for i in range(size):
        minidx = i
        for j in range(i+1,size):
            if(a[minidx]>a[j]):
                minidx=j
        a[minidx],a[i] = a[i],a[minidx]
arr = [9,1,22,4,0,-1,1,22,100,10]
selection_sort( arr )
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

1.3 복잡도

1.3.1 시간복잡도

데이터의 개수가 n개라고 했을 때,

• 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1

• 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2

  ...

• (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

따라서 최선, 평균, 최악의 경우 시간 복잡도는 O(n^2)

1.3.2 공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.

1.4 장단점

• 장점

  • Bubble sort와 마찬가지로 알고리즘이 단순

  • Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

    => 제자리 정렬(in-place sorting)

• 단점

  • 불안정 정렬(Unstable Sort)

2. 삽입정렬

모든 요소를 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하여 정렬을 완성하는 알고리즘

2.1 정렬과정

1. 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

2.2 코드

2.2.1 Java

void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    // 2.
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}

2.2.2 Python

def insertion_sort(arr):
    for i in range(1, len(arr)) :
        j = i-1
        temp = arr[i]
        while j>=0 and arr[j]>temp :
            arr[j+1] = arr[j]
            j-=1
        arr[j+1] = temp
        
arr = [9,1,22,4,0,-1,1,22,100,10]
insertion_sort(arr)
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

2.3 복잡도

2.3.1 시간복잡도

• 최악의 경우

  • (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
  • 즉, O(n^2)

• 최선의 경우

  • 이미 정렬이 되어 있는 경우
  • 한번씩 밖에 비교를 안하므로 O(n)

2.3.2 공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.

2.4 장단점

• 장점

  • 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적

  • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

  • 안정 정렬(Stable Sort) 이다.

  • 선택정렬이나 거품정렬와 같은 O(n^2)이지만, 상대적으로 빠르다.

  • 삽입정렬은 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행됨.

    선택정렬의 경우 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색해야함

• 단점

  • O(n^2) 이라 느림