정렬 알고리즘

Selection Sort (선택 정렬)

• 정렬되지 않은 맨 앞 값과 스왑하면서 진행
• 시간 복잡도 : O(n^2)

/** 오름차순 **/

void selectionSort(vector<int>& v) {
    for(int i = 0 ; i < v.size() ; i++) {
        int minIdx = i;
        for(int j = i ; j  < v.size() ; j++) {
            if(v[j] < v[minIdx]) {
                minIdx =  j;
            }
            
        }
        swap(i, minIdx, v);
    }
}

Insertion Sort (삽입 정렬)

• 정렬되지 않은 값을 정렬된 곳 사이에 삽입 하면서 진행
• 시간 복잡도
  최악(역으로 정렬된 경우) - O(n^2)
  최적(이미 정렬되어 있는 경우) - O(n)

/** 오름차순 **/

void insertionSort(vector<int>& v) {
    for(int i = 0 ; i < v.size() ; i++) {
        for(int j = i  ; j > 0 ; j--) {
            if(v[j] < v[j-1]) {
                swap(j, j-1, v);
            } else {
                break;
            }
        }
    }
}

Bubble Sort (버블 정렬)

• 시간 복잡도 : O(n^2)
• 1회 반복 시마다 정렬된 값이 배열의 맨 끝에 저장된다.

/** 오름차순 **/

void bubbleSort(vector<int>& v) {
    for(int i = 0 ; i < v.size() ; i++) {
        for(int j = 0 ; j < v.size() - i - 1; j++) {
            if(v[j] > v[j+1]) {
                swap(j, j+1, v);
            }
        }
    }
}

Merge Sort (병합 정렬)

• 시간 복잡도 : O(nlg(n))
  분할 : lg(n)
  병합 : n

/** 오름차순 **/

vector<int> merge(const vector<int>& v1, const vector<int>& v2) {
    vector<int> merged;

    int idxV1 = 0 , idxV2 = 0;

    while(idxV1 < v1.size() && idxV2 < v2.size()) {
        if (v1[idxV1] < v2[idxV2]) {
            merged.push_back(v1[idxV1++]);
        } else {
            merged.push_back(v2[idxV2++]);
        }
    }

    if(idxV1 != v1.size()) {
        for(int i = idxV1 ; i < v1.size() ; i ++) {
            merged.push_back(v1[i]);
        }

    } else if(idxV2 != v2.size()) {
        for(int i = idxV2 ; i < v2.size() ; i++){
            merged.push_back(v2[i]);
        }
    }

    return merged;
}

// [start, end]
vector<int> mergeSort(int start, int end, const vector<int>& v) {
    if(start == end) return vector<int>{v[start]};


    vector<int> left = mergeSort(start, (start+end)/2, v);
    vector<int> right = mergeSort((start+end)/2 + 1, end, v);

    vector<int> ans = merge(left, right);

    return ans;
}

Quick Sort (퀵 정렬)

• pivot point 기준 왼쪽 작은 값, 오른 쪽 큰 값으로 정렬 진행
• 시간 복잡도
  최악 : O(N^2) 기본 : O(NlgN)