[Sorting] 1. Insertion Sort (삽입 정렬) / Bubble Sort (버블 정렬)

1. Insertion Sort

Space-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다.

Time-Complexity = O(n^2)

원리

n개의 원소를 가진 배열을 정렬할 때, i번째를 정렬할 순서라고 가정하면, 0부터 i-1까지의 원소들은 정렬되어있다는 가정하에, i번째 원소와 i-1번째 원소부터 0번째 원소까지 비교하면서 i번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서(i+1)의 원소와 비교하면서 정렬해준다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복해준다.

c code>

//Insertion Sort
void insertion_sort(int * arr, int size) {
    int temp;
    int j;
    
    for(int i = 1; i < size; i++) {
        temp = arr[i];
        for(j = i - 1; j >= 0; j--) {
            if( temp < arr[j] ) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = temp;
    }
}

Bubble Sort

Space-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다.

Time-Complexity = O(n^2)

원리

인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 가장 큰 값을 배열의 맨 끝에다 이동시키면서 n 번을 두 번 반복하게 된다. 

//bubble sort
void bubble_sort(int * arr, int size) {
    for(int j = 0; j < size - 1; j++) {
        for(int i = 0; i < (size - j) - 1; i++) {
            if(arr[i] > arr[i + 1]) {
                swapValue(&arr[i], &arr[i + 1]);
            }
        }
    }
}
 
//util - swap
void swapValue(int * a, int * b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

1. end