정렬 알고리즘 정리

안정 정렬

버블 정렬

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

Time Complexity O(n^2)

삽입 정렬

for(int i=1; i<n; i++) {
    int j = i-1;
    while(j >= 0 && arr[j] > arr[j-1]) {
        swap(arr[j], arr[j-1]);
        j--;
    }
}

Time Complexity Worst O(n^2) Best O(n) 비교 연산은 많지만, swap연산은 적다. 정렬된 데이터일 경우 효율적

합병 정렬

void merge(int start, int mid, int end) {
    int left = start;
    int right = mid + 1;
    vector <int> temp;
    while(left <= start && right <= end) {
        if(arr[left] > arr[right]) temp.push_back(arr[right++]);
        else temp.push_back(arr[left++]);
    }

    while(left <= start) temp.push_back(arr[left++]);
    while(right <= end) temp.push_back(arr[right++]);

    int cnt = 0;
    for(int idx = start; idx<=end; i++) {
        arr[idx] = temp[cnt++];
    }
}

void mergeSort(int left, int right) {
    if(left < right) {
        int mid = (left + right) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);
    }
}

Time Complexity O(logn)

---

UNSTABLE

선택 정렬

for(int i=0; i<n; i++) {
    int target = i;
    for(int j=i+1; j<n; j++) {
        if(arr[target] > arr[j]) target = j;
    }
    swap(arr[target], arr[i]);
}

Time Complexity O(n^2)

퀵 정렬

int partition(int left, int right) {
    int pivot = left;
    int low = left + 1;
    int high = right;

    while(low <= high) {
        while(low <= right && ans[pivot] >= ans[low]) low++;
        while(high > left && ans[pivot] <= ans[high]) high--;

        if(low > high) swap(ans[pivot], ans[high]);
        else swap(ans[low], ans[high]);
    }

    return high;

}
int quickSort(int left, int right) {
    if(left < right) {
        int p = partition(left, right);
        quickSort(left, p-1);
        quickSort(p+1, right);
    }
}

Time Complexity Best O(logn) Worst O(n^2) 역순 정렬일 때는 n^2의 시간복잡도를 가진다. 이를 해결하기 위해서는 피봇을 랜덤이나 가운데 값으로 고르면 된다.