O(n²) sorting

Sort
Algorithm T(n) S(n) Data Limit
Bubble O(n^2) n X
Selection O(n^2) n X
Merge O(nlgn) 2n X
Quick O(nlgn) n X
Heap O(nlgn) 2n X
Counting O(n+k) n+k O
Raidx O(d(n+k)) n+k O
  • n : 데이터 개수, k : 데이터 범위, d : 데이터의 자릿수
  • T(n) : 시간 복잡도, S(n) : 공간 복잡도
  • 위의 표만 보고 퀵이 제일 좋고, counting이 radix보다 좋다고 판단하면 안된다. 다상황에 따라 유리한 경우가 다름

 

버블 정렬

인접한 두 항을 비교하여 swap 하는 방식

한번 돌 때 마다 최대값이 뒤로 감

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

#define N 6

int data[N] = { 40, 6, 1, 9, 3, 5 };

void main(){
    for (int i = 1; i < N; ++i){
        for (int j = 1; j < N - i + 1; ++j){
            if (data[j - 1] > data[j])
                swap(j - 1, j);
        }
    }
}

 

선택 정렬

한번 돌 때 마다 최솟값을 찾아 가장 앞에 넣어주는 방법을 N번 반복

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

#define N 6

int data[N] = { 40, 6, 1, 9, 3, 5 };

void main(){
    int v;
    for (int i = 0; i < N; ++i){
        v = i;
        for (int j = i; j < N ; ++j){
            if (data[v] > data[j])
                v = j;
        }
        swap(i, v);
    }
}

 

 

You may also like...