Data structure and algorithm review (1) sorting algorithm

This article will introduce common sorting algorithms (implemented in C++)

1. Bubble sort

Divides an array into ordered (left) and unordered (right) regions. The ordered region is empty at initialization and the unordered region contains all the elements of the array

Start with the last element of the unordered region each time and bubble forward to the first location of the unordered region to make it orderly

template<typename E>
void swap(E A[], int i, int j) {
    E temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

template<typename E>
void bubbleSort(E A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = n - 1; j > i; j--) {
            if (A[j] < A[j - 1]) {
                swap(A, j, j - 1); }}}}Copy the code

2. Selection sort

template<typename E>
void swap(E A[], int i, int j) {
    E temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

template<typename E>
void selectionSort(E A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i; j <= n - 1; j++) {
            if (A[j] < A[minIdx]) minIdx = j;
        }
        swap(A, i, minIdx); }}Copy the code

3. Insert sort

An array is divided into ordered (left) and unordered (right) regions, with the ordered containing the first element and the unordered containing the rest of the array at initialization

Each time, swap the first element in the unordered region all the way forward to the appropriate position in the ordered region, so that it becomes ordered

template<typename E>
void swap(E A[], int i, int j) {
    E temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

template<typename E>
void insertionSort(E A[], int n) {
    for (int i = 1; i < n; i++) {
		for (int j = i; j > 0; j--) {
            if (A[j] < A[j - 1]) {
                swap(A, j, j - 1); }}}}Copy the code

4. Merge sort

template<typename E>
void mergeSort(E A[], E T[], int l, int r) {
    if (l == r) return;
    int m = (l + r) / 2;
    mergeSort<E>(A, T, l, m);
    mergeSort<E>(A, T, m + 1, r);
    // merge
    for (int k = l; k <= r; k++) T[k] = A[k];
    int i = l, j = m + 1;
    for (int c = l; c <= r; c++) {
        if (i > m) A[c] = T[j++];
        else if (j > r) A[c] = T[i++];
        else if (T[i] < T[j]) A[c] = T[i++];
        elseA[c] = T[j++]; }}Copy the code

template<typename E>
void mergeSort(E A[], E T[], int l, int r) {
    if (l == r) return;
    int m = (l + r) / 2;
    mergeSort<E>(A, T, l, m);
    mergeSort<E>(A, T, m + 1, r);
    // merge
    for (int k = l; k <= m; k++) T[k] = A[k];
    for (int k = 1; k <= r - m; k++) T[r - k + 1] = A[k + m];
    int i = l, j = r;
    for (int c = l; c <= r; c++) {
        if (T[i] < T[j]) A[c] = T[i++];
        elseA[c] = T[j--]; }}Copy the code

5. Quicksort

Recursively, each time in the array to select a baseline, according to the baseline array divided into two, and then the two arrays sorted separately, splice two arrays

template<typename E>
void swap(E A[], int i, int j) {
    E temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

template<typename E>
void quickSort(E A[], int l, int r) {
    if (r <= l) return;
    // find pivot
    int pivotIndex = (l + r) / 2;
    E pivot = A[pivotIndex];
    // put pivot at last
    swap(A, pivotIndex, r);
    // partition
    int i = l - 1;
    int j = r;
    do {
        while (A[++i] < pivot) {}
        while (i < j && pivot < A[--j]) {}
        swap(A, i, j);
    } while (i < j);
    // put pivot in place
    swap(A, r, i);
    // recursive
    quickSort(A, l, i - 1);
    quickSort(A, i + 1, r);
}
Copy the code

Optimization: Use stacks instead of recursion

template<typename E>
void swap(E A[], int i, int j) {
    E temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

template<typename E>
void quickSort(E A[], int l, int r) {
    int stack[200];
    int top = - 1;
    stack[++top] = l;
    stack[++top] = r;
    while (top > 0) {
        // pop the stack
        r = stack[top--];
        l = stack[top--];
        // find pivot
        int pivotIndex = (l + r) / 2;
        E pivot = A[pivotIndex];
        // put pivot at last
        swap(A, pivotIndex, r);
        // partition
        int i = l - 1;
        int j = r;
        do {
            while (A[++i] < pivot) {}
            while (i < j && pivot < A[--j]) {}
            swap(A, i, j);
        } while (i < j);
        // undo the last swap
        swap(A, i, j);
        // put pivot in place
        swap(A, r, i);
        // load up stack
        if (i - 1 > l) {
            stack[++top] = l;
            stack[++top] = i - 1;
        }
        if (r > i + 1) {
            stack[++top] = i + 1; stack[++top] = r; }}}Copy the code

6, test,

#include <iostream>
#include <time.h>
using namespace std;

int main(a) {
    const int num = 1000;
    const int minVal = 0;
    const int maxVal = 1000;
    int* arr = new int[num];
    for (int i = 0; i < num; i++)
        arr[i] = rand() % (maxVal - minVal + 1) + minVal;
    
    int* a4b = new int[num];
    int* a4s = new int[num];
    int* a4i = new int[num];
    int* a4m = new int[num];
    int* a4q = new int[num];

    int* t = new int[num];

    for (int i = 0; i < num; i++) a4b[i] = arr[i];
    for (int i = 0; i < num; i++) a4s[i] = arr[i];
    for (int i = 0; i < num; i++) a4i[i] = arr[i];
    for (int i = 0; i < num; i++) a4m[i] = arr[i];
    for (int i = 0; i < num; i++) a4q[i] = arr[i];

    clock_t start, end;

    start = clock(a);bubbleSort(a4b, num);
    end = clock(a); cout <<"bubbleSort: "< < (double)(end-start)/CLOCKS_PER_SEC << endl;
    
    start = clock(a);selectionSort(a4s, num);
    end = clock(a); cout <<"selectionSort: "< < (double)(end-start)/CLOCKS_PER_SEC << endl;

    start = clock(a);insertionSort(a4i, num);
    end = clock(a); cout <<"insertionSort: "< < (double)(end-start)/CLOCKS_PER_SEC << endl;

    start = clock(a);mergeSort(a4m, t, 0, num - 1);
    end = clock(a); cout <<"mergeSort: "< < (double)(end-start)/CLOCKS_PER_SEC << endl;

    start = clock(a);quickSort(a4q, 0, num - 1);
    end = clock(a); cout <<"quickSort: "< < (double)(end-start)/CLOCKS_PER_SEC << endl;

    return 0;
}
Copy the code