[ Algorithm ] Insertion sort, Bubble sort, Selection sort?

Insertion sort 이란?

       배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 비분과 비교하여, 위치를 찾아 삽입함으로써, 정렬을 완성합니다.

 

      시간복잡도 (Time Complexity)

            - best case : O(n)

            - worst case : O(n^2)

      * It does little work if the list is nearly sorted

Insertion sort 동작

       1. 배열 내에서, 2번째 위치의 값을 임시로 저장합니다.

       2. 임시로 저장한 값 이전에 위치한 원소들과 비교하여, 값을 변경합니다.

       3. 위의 1 ~ 2번의 과정을 계속해서 시행합니다.

Insertion sort code with C/C++

void insert(element e, element a[], int i) {

    a[0] = e;
    while (e.key < a[i].key) {
    	a[i+1] = a[i];
        i--;
    }
    a[i+1] = e;
}

void insertionSort(element a[], int n) {

    int j;
    for (j = 2; j <= n; j++) {
    	element temp = a[j];
        insert(temp, a, j-1);
    }
}

Bubble sort 이란?

       배열 내 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않는다면, 자리를 교환하며 정렬하는 알고리즘이다.

 

      시간복잡도 (Time Complexity)

            - common case : O(n^2)

Bubble sort 동작

       1. 버블 정렬은 배열 내 첫 번째 자료와 두 번째 자료를 비교하고, 두 번째 자료와 세 번째 자료를 비교하는 방식으로

           이러한 방식으로, n-1 번째 자료와 n번째 자료와 비교하여, 교환을 진행하며, 자료를 정렬합니다.

 

       2. 1의 방식을 1회 수행하고 난 후, 가장 큰 자료가 맨 뒤로 이동하고, 2회전에서는 배열 내 마지막 자료는 정렬에서 제외되고,

           수행된다. 이러한 방식으로, n회전을 수행할 때마다, 정렬에서 제외되는 데이터가 하나씩 증가합니다.

Bubble sort code with C/C++

void bubbleSort(element a[], int n) {

    element tmp;
    int i, j;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-1-i; j++) {
            if (a[j+1] < a[j[]) {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

Selection sort 이란?

       Bubble sort와 유사한 방식으로, 배열 내 현재 위치를 제외하고의 이후의 위치에서 최소값을 찾아 변경하는 방식이다.

 

      시간복잡도 (Time Complexity)

            - common case : O(n^2)

Selection sort 동작

       1. 배열 내 현재 위치를 제외하고 이후의 위치에서 최소값을 찾습니다.

       2. 배열 내 현재 위치와 최소값의 위치와 변경합니다.

       3. 이후, 현재 위치의 값을 한 칸씩 옮기면서, 위의 1 ~ 2 과정을 반복수행합니다.

Selection sort code with C/C++

void selectionSort(int a[], int n) {
    int i, j, min, temp;
    
    for (i = 0; i < n-1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[min])
                min = j;
        }
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

Author's GitHub

https://github.com/kalelpark