단순 선택 정렬

단순 선택 정렬이란?

단순 선택 정렬 알고리즘은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘입니다.

동작 과정

1. 0 ~ n - 1요소 중에서 가장 작은 요소 탐색 후 0번 Index의 요소와 Swap
2. 1 ~ n - 1요소 중 가장 작은 요소 탐색 수 1번 Index 요소와 Swap
3. 해당 과정을 n - 2 ~ n - 1까지 반복 후 정렬 종료

해당 과정을 간단하게 표현하자면 다음과 같습니다.

아직 정렬되지 않은 부분에서 가장 작은 키의 값 (a[min])을 선택 후 정렬 되지 않은 부분의 가장 앞에 있는 요소와 교환 후 다음 반복문 진행

해당 방식은 자료가 역순 정렬인 상태일때 가장 적합한 정렬입니다.

해당 정렬은 따로 정리할 것은 없으니 코드를 적어놓도록 하겠습니다.

장단점

장점

1. 코드가 직관적, 구현 간단

2. 비교 횟수는 많으나 교환 횟수는 상당히 적다.

단점

1. 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 될 때 최악의 처리 속도

코드

void swap(int[] a, int idx1, int idx2) {
  int temp = a[idx1]; a[idx1] = a[idx2]; a[idx2] = a[idx1];
}

void selectionSort(int[] a, int n) {
  for(int i = 0; i < n - 1; i++) {
    int min = i;          // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록한다.
    for(int j = i + 1; j < n; j++) {
      if (a[j] < a[min])
        min = j;
    }
    // 미정렬 요소 중 가장 작은 요소 i번째 인덱스 요소와 위치 바꿔주기
    swap(a, i, min);
  }

시간 복잡도

단순 삽입 정렬

단순 삽입 정렬이란?

단순 삽입 정렬(Straight Insertion Sort)은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘이다. 단순 선택 정렬과 비슷해보이지만 단순 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다릅니다.

동작 과정

1. i = 1 ~ n -1 까지 반복문을 실행
2. 정렬된 부분과 정렬되지 않은 부분을 구분해 가면서 정렬되지 않은 부분의 가장 앞쪽 요소가 정렬된 부분의 알맞은 위치에 배치되도록 진행
3. 해당 과정을 n - 1 번 수행

해당 정렬도 코드로 남겨놓겠습니다.

장단점

장점

1. 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라집니다.

단점

1. 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아집니다.

코드

void insertionSort(int[] a, int n) {
  for(int i = 1; i < n; i++) {
    int j;
    int tmp = a[i];
    // i가 1씩 증가하면서 요소 값을 하나 선택하고 앞에 정렬 되어 있는 부분과 비교 하면서 위치 찾아주는 정렬 방식
    for(j = i; j > 0 && a[j - 1] > tmp; j--)
      a[j] = a[j - 1];
    // for문의 경우 조건식에 맞았을 경우 for문 안의 코드를 실행 후 증감식을 실행 후 다시 조건문을 확인한다.
    // 따라서, 아래와 같이 코드를 해줘야 바뀌는 것임.
    a[j] = tmp;
  }
}

시간 복잡도

결국 두 정렬 다 시간 복잡도는 $O(n^2)$로 좋지 않은 효율을 보여줍니다.