algorithm/everysort.cpp at master · phanthaiduong22/algorithm · GitHub

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>

using namespace std;

void selectionsort(vector<int> &a){
    int n = a.size();
    for(int i = 0;i<n; ++i){
        int min_idx = i;
        for(int j = i;j<n; ++j){
            if(a[min_idx] > a[j])
                min_idx = j;
        }
        swap(a[min_idx], a[i]);
    }
}

void bubblesort(vector<int> &a){
    int n = a.size(); //swap(a[j], a[j + 1])
    for(int i = 0;i<n; ++i){
        int swapped = 0;
        for(int j = 0;j<n - i - 1; ++j){
            if(a[j] > a[j + 1]){
                swap(a[j], a[j + 1]);
                swapped = 1;
            }
        }
        if(swapped == 0)
            return;
    }
}

void insertionsort(vector<int> & a){
    int n = a.size();
    for(int i = 1;i<n; ++i){
        int v = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] > v){
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = v;
    }
}

void quicksort(vector<int>&a, int left, int right){
    int left_arrow, right_arrow, pivot;
    left_arrow = left;
    right_arrow = right;
    pivot = a[(right + left) / 2];
    do{
        while(a[left_arrow] < pivot)
            left_arrow++;
        while(a[right_arrow] > pivot)
            right_arrow--;
        if(left_arrow <right_arrow){
            swap(a[left_arrow], a[right_arrow]);
            left_arrow++;
            right_arrow--;
        }
    }while(left_arrow<=right_arrow);
    if(left < right_arrow)
        quicksort(a, left, right_arrow);
    if(left_arrow < right);
        quicksort(a, left_arrow, right);
}

void mergesort(vector<int> &a, int l, int r){
    if(l>=r)
        return;
    int m = (r + l) / 2;
    mergesort(a, l, m);
    mergesort(a, m + 1, r);
    int *temp = new int [r - l + 1];
    int i = l, j = m + 1, k = 0;

    // a[l...mid] a[mid + 1...r]

    while(i<=m && j <= r){
        if(a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    while(i<=m)
        temp[k++] = a[i++];
    while(j<=r)
        temp[k++] = a[j++];

    k = 0;
    for(int i = l; i<=r; ++i){
        a[i] = temp[k++];
    }

    delete[] temp;
}

int main(){
    vector<int> a = { 3, 2, 4, 5, 1, 6, 7};
    mergesort(a, 0, a.size() - 1);
    for(int i : a)
        cout<<i<<" ";
}