단순 선택 정렬, 단순 삽입 정렬, 이진 삽입 정렬

단순 선택 정렬

---

 단순 선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다. 오름차순을 예를 들어 설명하자면 '정렬되지 않은 열에서 가장 작은 값을 찾아 정렬되지 않은 열에 첫 번째 요소와 교환'하는 것이다. 시간 복잡도는 O(n^2)이다.
 

// 기존 배열
// 정렬된 수 : 없읍
// 정렬되지 않은 수: 전부
[6,4,8,3,1,9,7]
// 가장 작은 수 1을 첫 번째 요소 6과 변경한다.

// 정렬된 수 : 1
// 정렬되지 않은 수: 4,8,3,6,9,7
[1,4,8,3,6,9,7]
// 정렬된 수 1을 제외한 수 중 가장 작은 수 3을 4와 변경한다.

// 정렬된 수 : 1,3
// 정렬되지 않은 수: 8,4,6,9,7
[1,3,8,4,6,9,7]

 

static void selectionSort(int[] a, int n) {
    for (int i = 0; i < n - 1; i++) {
        // 정렬 되지 않은 열에서 가장 작은 값의 인덱스
        int min = i;
        // 정렬 되지 않은 열에서 가장 작은 값을 찾는다
        for (int j = i + 1; j < n - 1; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        // 가장 작은 값과 정렬 되지 않은 열에 첫번째 요소와 변경 한다
        swap(a, i, min);
    }
}

 
 

단순 삽입 정렬

---

 단순 삽입 정렬은 선택한 요소를 알맞은 위치에 삽입하여 정렬하는 알고리즘이다. 오름차순을 예를 들어 설명하자면 '정렬되지 않은 열에 첫 번째 요소를 정렬된 열의 알맞은 위치를 찾은 후 수들을 오른쪽으로 밀어내고 값을 넣는것'이다. 때문에 삽입 전에 배열에는 같은 값이 존재하는 순간들이 있다. 시간 복잡도는 O(n^2)이다. 

static void insertionSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            // 정렬 되지 않은 요소 중 첫 번째
            int key = a[i];
            // 정렬 된 열에 마지막 요소
            int j = i - 1;
            // 이전 요소들과 비교하면서 적절한 위치 찾기
            // 이전 요소가 key보다 크다면 오른쪽으로 값을 복사한다.
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }

            // 찾은 위치에 현재 요소 삽입
            a[j + 1] = key;
        }
    }

 

이진 삽입 정렬

---

 단순 삽입정렬에서 삽입할 위치를 찾을 때 이진 검색을 사용하면 더 빨리 찾을 수 있다.
 

static void binaryInsertionSort(int[] a) {
    int n = a.length();
    
    for (int i = 1; i < n; i++) {
        int value = a[i];
        int leftIdx = 0;                // 검색 범위 맨앞의 인덱스
        int rightIdx = i - 1;           // 　 〃 　맨끝의 인덱스
        int centerIdx;                  // 　 〃 　중앙의 인덱스
        int position;                   // 삽입하는 위치의 인덱스

        do {
            centerIdx = (leftIdx + rightIdx) / 2;
            if (a[centerIdx] == value) {
                break;
            } else if (a[centerIdx] < value)
                leftIdx = centerIdx + 1;
            else {
                rightIdx = centerIdx - 1;
            }
        } while (leftIdx <= rightIdx);

        // leftIdx가 righIdx보다 큰 경우는 삽입하려는 값이 현재 검색 범위의 모든 값보다 작다는 뜻이다.
        position = (leftIdx <= rightIdx) ?
                centerIdx + 1 : rightIdx + 1;

        for (int j = i; j > position; j--) {
            a[j] = a[j - 1];
        }
        a[position] = value;
    }
}