삽입 정렬 insertion Sort

 

 선택정렬은 주어진 리스트에서 최솟값을 찾아 첫 번째 위치에 놓고 나머지 리스트에서 최솟값을 찾아 두 번째 위치에 놓으며 이 과정을 리스트의 끝까지 반복한다. 선택정렬은 직관적이고 구현하기 쉽지만, 시간 복잡도는 \(O(n^2)\) 로 리스트의 길이가 길어질수록 성능이 떨어진다는 것을 의미한다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void selectionSort(int numbers[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < size; j++) {
            if (numbers[j] < numbers[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum element with the first element
        int temp = numbers[minIndex];
        numbers[minIndex] = numbers[i];
        numbers[i] = temp;
    }
}

int main() {
    int numbers[] = {4, 3, 7, 1, 2, 5};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    selectionSort(numbers, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}

 삽입정렬 (Insertion Sort) 은 리스트의 요소를 하나씩 꺼내어 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식이다. 두 번째 요소부터 시작하여, 현재 요소를 그보다 앞에 있는 요소들과 비교하여 현재 요소가 비교 대상 요소보다 작으면, 비교 대상 요소를 한 칸 뒤로 이동시킨다. 이 과정을 반복하여, 현재 요소를 적절한 위치에 삽입한다. 삽입정렬은 평균 및 최악의 경우 시간 복잡도는 \(O(n^2)\)이지만, 리스트가 이미 어느 정도 정렬되어 있는 경우에는 \(O(n)\)에 가까운 성능을 보이다. 따라서 삽입정렬은 이미 정렬된 리스트에 대해 매우 효율적이다.
 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void insertionSort(int numbers[]) {
    for (int i = 1; i < 6; i++) {
        int currentValue = numbers[i];
        int j;
        for (j = i - 1; j >= 0 && numbers[j] > currentValue; j--) {
            numbers[j + 1] = numbers[j];
        }
        numbers[j + 1] = currentValue;
    }
}

int main() {
    int numbers[] = {6, 4, 5, 1, 2, 7};
    insertionSort(numbers);
    for (int i = 0; i < 6; i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}

 

 

 

 따라서 선택정렬은 공간을 오름차순으로 선택하여 매번 최소값을 찾아 순서대로 정렬하는 것이고 삽입정렬은 두번 째 요소부터 꺼내어 앞 요소들과 모두 비교하는 것이다. 삽입정렬은 어느정도 정렬이 된 리스트에서 유리하다.