rvkhunLab

Write about System Hacking

0%

Sorting

Posted on In
  • 정렬 비교

Bubble Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubble_sort(vector<int> &vec){

    for (int i=0; i<vec.size()-1;i++){
        for(int j=1; j<vec.size()-i; j++){
            
            if(vec[j-1] > vec[j]){
                int tmp = vec[j-1];
                vec[j-1] = vec[j];
                vec[j] = tmp;
            }
        }
    }
}

bubble-sort-001

  • 시간 복잡도 : n(n-1)/2 => O(N^2)
  • 공간 복잡도 : O(N)
  • Stable sort.

Selection Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selection_sort(vector<int> &vec){
    int min = 0;

    for(int i=0; i<vec.size()-1;i++){   
        min = i;

        for (int j=i+1; j<vec.size();j++){
            if(vec[j] < vec[min]){
                min = j;
            }
        }
        int tmp = vec[i];
        vec[i] = vec[min];
        vec[min] = tmp;
    }
}

selection-sort-001

  • 시간 복잡도 : n(n-1)/2 => O(N^2)
  • 공간 복잡도 : O(N)
  • Unstable sort.

Insertion Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void insertion_sort(vector<int> &vec){

    for(int i=1;i<vec.size();i++){
        int prev = i-1;
        int tmp = vec[i];

        for(prev;prev>=0;prev--){
            if(vec[prev] > tmp)
                vec[prev+1] = vec[prev];
            else
                break;
        }
        vec[prev+1] = tmp;
    }
}

insertion-sort-001

  • 시간 복잡도 : best case = O(N), worst case = O(N^2)
  • 공간 복잡도 : O(N)
  • Stable sort.

Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
template <typename T>
vector<T> merge(vector<T>& arr1, vector<T>& arr2){

    vector<T> merged;

    auto iter1 = arr1.begin();
    auto iter2 = arr2.begin();

    while(iter1 != arr1.end() && iter2 != arr2.end()){

        if (*iter1 < *iter2){
            merged.emplace_back(*iter1);
            iter1++;
        }
        else{
            merged.emplace_back(*iter2);
            iter2++;
        }
    }
    if(iter1 != arr1.end()){
        for(;iter1 != arr1.end(); iter1++)
            merged.emplace_back(*iter1);
    }
    else{
        for(;iter2 != arr2.end();iter2++)
            merged.emplace_back(*iter2);
    }

    return merged;

}

template <typename T>
vector<T> merge_sort(vector<T> arr){

    if (arr.size() > 1){
        auto mid = size_t(arr.size()/2);
        auto left_half = merge_sort<T>(vector<T>(arr.begin(),arr.begin()+mid));
        auto right_half = merge_sort<T>(vector<T>(arr.begin()+mid, arr.end()));

        return merge<T>(left_half,right_half);
    }
    return arr;

}

618px-Merge_sort_algorithm_diagram svg

  • LinkedList의 정렬에 효과적.
  • 시간 복잡도 : O(NlogN)
  • Stable sort

Quick Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
template <typename T>
auto partition(typename vector<T>::iterator begin, typename vector<T>::iterator end){

    auto pivot_val = *begin;
    auto left_iter = begin + 1;
    auto right_iter = end;

    while(true){
        while(*left_iter <= pivot_val && distance(left_iter,right_iter) > 0)
            left_iter++;
    
        while(*right_iter > pivot_val && distance(left_iter,right_iter) > 0)
            right_iter--;

        if(left_iter == right_iter)
            break;
        else
            iter_swap(left_iter,right_iter);        

    }   

    if(pivot_val > *right_iter)
        iter_swap(begin,right_iter);

    return right_iter;


}

template<typename T>
void quick_sort(typename vector<T>::iterator begin, typename vector<T>::iterator last){

    if(distance(begin,last) >= 1){

        auto partition_iter = partition<T> (begin, last);

        quick_sort<T>(begin, partition_iter - 1);
        quick_sort<T>(partition_iter,last);

    }

}

quick-sort-001

  • 시간복잡도 : O(Nlog2N)
  • 공간복잡도 : O(N)
  • Unstable sort

참고

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html