[C] 단순 선택 정렬과 단순 삽입 정렬

단순 선택 정렬

단순 선택 정렬(straight selection sort)은 가장 작은 요소를 선택해 알맞은 위치로 옮기는 과정을 반복하여 정렬하는 알고리즘이다.

#include <stdio.h>

int main() {

  int a[5], b;
  for(int i=0; i<5; i++){
    scanf("%d", &a[i]);
  }
  for(int i=0; i<5; i++){
    printf("%d|", a[i]);
  }
  printf("\n");

  for(int i=0; i<4; i++){
    int min = i;
    for(int j = i+1; j<5; j++) 
      if(a[j]<a[min]) min = j;
    b = a[i];
    a[i] = a[min];
    a[min] = b;
    for(int i=0; i<5; i++){
      printf("%d|", a[i]);
    }
    printf("\n");
  }
  return 0;
}

-------------------------------

결과

1
3
2
5
4
1|3|2|5|4|
1|3|2|5|4|
1|2|3|5|4|
1|2|3|5|4|
1|2|3|4|5|

이처럼 처음엔 최솟값인 1을 찾아 첫 번째에 넣고

두 번째 최솟값인 2를 찾아 1 뒤에 넣고 이를 반복하다보면 정렬이 완성된다.

단순 삽입 정렬

단순 삽입 정렬(straight insertion sort)은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘이다.

5 1 2 3 4 에서 삽입 정렬을 실행하면 1이 5를 밀어내며

1 5 2 3 4 가 되고 이 과정이 반복되며

1 2 5 3 4
...
1 2 3 4 5 로 정렬이 완료된다.

즉 선택한 요소의 왼쪽에서 자기보다 큰값이 있는 동안은 계속 왼쪽으로 이동하는 것이다.

이 과정은 선택한 요소를 임시로 저장해놓고 선택한 요소의 위치에 바로 왼쪽의 요소를 대입하는 과정을 반복하면서 최종 위치에다가 임시로 저장해놓은 요소를 대입하는 식으로 이뤄진다.

#include <stdio.h>

int main() {

  int a[5];
  for(int i=0; i<5; i++){
    scanf("%d", &a[i]);
  }
  for(int i=0; i<5; i++){
    printf("%d|", a[i]);
  }
  printf("\n");

  for(int i=0; i<5; i++){
    int tmp = a[i];
    int j;
    for(j=i; j>0 && a[j-1]>tmp; j--){
      a[j] = a[j-1];
    }
    a[j] = tmp;
    for(int i=0; i<5; i++){
      printf("%d|", a[i]);
    }
    printf("\n");
  }
  return 0;
}

----------------------------------
결과

5
4
3
2
1
5|4|3|2|1|
5|4|3|2|1|
4|5|3|2|1|
3|4|5|2|1|
2|3|4|5|1|
1|2|3|4|5|

5에서 부터 1까지 앞에 자기보다 큰 수가 있으면 밀어낸다.

for(j=i; j>0 && a[j-1]>tmp; j--){
  a[j] = a[j-1];
}

이와 같은 조건식을 통해 자기보다 큰 수가 없을 때 까지 밀어낼 수 있고 j를 안에서 미리 선언함으로써 뒤에서 j를 위치를 저장 용도로 사용할 수 있었다.

단순 정렬의 한계

지금까지 다룬 세 가지 단순 정렬(버블, 선택, 삽입)은 아무리 개선한다하더라도 시간복잡도는 결국 O(n^2)가 된다.

다음 글 부터는 시간 복잡도 자체가 개선된 알고리즘을 다뤄보겠다.