casyup.me@outlook.com

0%

other/sort

Posted on

source link

Sort

Bubble Sort

Bubble is the most common algorithm to sort an array. It based on the idea of repeatedly comparing adjacent element and then swapping their value if exist in the wrong order 

1
2
3
4
5
6
7
8
void bubbleSort(vector<int> &nums) {
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[i] > nums[j])
                swap(nums[i], nums[j]);
        }
    }
}

Selection sort

The selection sort is based on finding the minimum or maximum in an unsorted array and putting it to a sorted array

1
2
3
4
5
6
7
8
9
10
void selectionSort(vector<int> &nums) {
    for (int i = 0; i < nums.size(); ++i) {
        int min = i;
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[min] > nums[j])
                min = j;
        }
        swap(nums[i], nums[min]);
    }
}

Insertion sort

From left to right, find each element’s correct position

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertSort(vector<int> &nums) {
    for (int i = 1; i < nums.size(); ++i) {
        int v = nums[i];
        int j = i;
        while(j > 0) {
            nums[j] = nums[j - 1];
            if (nums[j] <= v)
                break;
            --j;                            
        }
        nums[j] = v;
    }
}

Merge sort

Merge sort is a divide-and-conquer algorithm based on repeatedly breaking down an array to two sub-array and then merge them

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
void merge(vector<int> &nums, int b, int e) {
    int m = (b + e) / 2;
    int q = m + 1, p = b;
    vector<int> v;
    for (int i = b; i <= e; ++i) {
        if (p > m)
            v.push_back(nums[q++]);
        else if (q > e)
            v.push_back(nums[p++]);
        else if (nums[q] > nums[p])
            v.push_back(nums[p++]);
        else
            v.push_back(nums[q++]);              
    }

    for (auto val : v)
        nums[b++] = val;
}

void mergeSort(vector<int> &nums, int b, int e) {
    if (b >= e) return;

    mergeSort(nums, b, (e + b) / 2);
    mergeSort(nums, (e + b) / 2 + 1, e);
    merge(nums, b, e);
}

Quick sort

Quick sort is also a divide-and-conquer algorithm. But it reduces the space complexity and removes the use of auxiliary array that is used in merger sort
One of the most important factors to influence performance is the pivot.
I chose the pivot from the middle, front, and back of the array. Sometimes will improve performance

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
int partion(vector<int> &nums, int b, int e) {
    int p = e;
    int m = (b + e) / 2;
    if (nums[b] > nums[m])
        swap(nums[b], nums[m]);
    if (nums[b] > nums[e])
        swap(nums[b], nums[e]);
    if (nums[m] > nums[e])
        swap(nums[m], nums[e]);

    int piv = nums[m];
    swap(nums[e--], nums[m]);
    while (b < e) {
        while (b < e && nums[b] < piv)
            ++b;
        while (b < e && nums[e] >= piv)
            --e;
        if (b >= e) break;

        swap(nums[b], nums[e]);
    }
    swap(nums[p], nums[b]);

    return b;
}

void quickSort(vector<int> &nums, int b, int e) {
    if (b >= e) return;

    int p = partion(nums, b, e);
    quickSort(nums, b, p - 1);
    quickSort(nums, p + 1, e);
}

Heap sort

Heap sort uses a structure called heap to sort the array. Heap is a complete binary tree.
left sub-tree index = 2 * root index + 1
right sub-tree index = 2 * root index + 2

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
void heapify(vector<int> &nums, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = l + 1;

    if (l < n && nums[l] > nums[largest])
        largest = l;

    if (r < n && nums[r] > nums[largest])
        largest = r;

    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

void heapSort(vector<int> &nums) {                
    for (int i = nums.size() / 2 - 1; i >= 0; --i)
        heapify(nums, nums.size(), i);

    for (int i = nums.size() - 1; i >= 0; --i) {
        swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}