Basic Sorting Algorithms

버블 정렬(Bubble Sort)

void optimizedBubbleSort(int a[], int n){
    for (int i = 0; i < n-1; ++i) {
        for (int j = 0; j < n-1-i; ++j)
            if (n[j] > n[j+1]) swap(n[j], n[j+1]);
    }
}

크거나 작은 수를 배열의 뒤쪽으로 밀면서 정렬한다. 시간 복잡도는 O(N^2)이다.

 

 

삽입 정렬(Insertion Sort)

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; ++i) {
        int current = a[i];
        int prev = i - 1;
        
        while (0 <= prev && a[prev] > current) {
            a[prev + 1] = a[prev];
            --prev;
        }
        a[prev + 1] = current;
    }
}

배열을 정렬된 값들, 정렬되지 않은 값들의 영역으로 분리하여 앞으로 끌고오며 값을 당겨온다.

시간 복잡도는 O(N^2)이다. 또한 stable sort이다.

 

 

선택 정렬(Selection Sort)

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

버블 정렬과 더불어 가장 기본적인 정렬이고 버블 정렬과 다르게 정렬된 값을 앞에서부터 채워나간다.

시간 복잡도는 O(N^2)이다.

 

 

계수 정렬(Counting Sort)

void countingSort(int a[], int n) {
    int largest = -1; // 오름차순, 내림차순과 값의 범위에 따라 결정
    
    for (int i = 0; i < n; ++i)
        largest = max(largest, a[i]);
    
    vector<int> freq(largest+1, 0);
    
    for (int i = 0; i < n; ++i) {
        freq[a[i]]++;
    }
        
    int j = 0;
    for (int i = 0; i <= largest; ++i) {
        while (freq[i]-- > 0) {
            a[j] = i;
            ++j;
        }
    }
}

정렬될 값의 범위(Range)가 넓지 않고 범위를 알고 있을 때 유용하게 사용할 수 있다.

범위를 정확히 알지 못하더라도 최대값을 구해서 벡터를 사용하면 된다.

시간 복잡도는 O(Range + N)이다.