This is the 23rd day of my participation in the August More Text Challenge

Sorting Algorithms

Your favorite kinds of sorting algorithms, in C language implementation.

The algorithm we are going to implement follows this interface:

// sort sort the first n elements of array A
typedef void (*sort)(int A[], int n);
Copy the code

Direct insertion sort

Walk through, find the right place forward, move back element by element to make room, insert.

Complexity:

Time O (n2) to O (n ^ 2) O (n2)
Space is O (1) O (1) O (1)

void
insert_sort(int A[], int n)
{
    for (int i = 0; i < n; ++i) {
        int curr = A[i];

        int j = i - 1;
        while (j >= 0 && curr < A[j]) {
            A[j + 1] = A[j];
            --j;
        }

        A[j + 1] = curr; }}Copy the code

Binary insertion sort

I’m just going to go straight in and find the right place and use a binary search there.

Complexity:

Good time: O (nlog ⁡ (n)) O (n \ log (n)) O (nlog (n)), a bad O (n2) to O (n ^ 2) O (n2), average O (n2) to O (n ^ 2) O (n2)
Space is O (1) O (1) O (1)

void
binary_insert_sort(int A[], int n)
{
    for (int i = 0; i < n; ++i) {
        int curr = A[i];

        // Binary search
        int l = 0, r = i - 1;
        while (r >= 0 && l < i && l <= r) {
            int m = (l + r) / 2;
            if (curr < A[m]) {
                r = m - 1;
            } else {
                l = m + 1; }}/ / move backward
        for (int j = i - 1; j >= l; --j) {
            A[j + 1] = A[j];
        }
        / / insertA[l] = curr; }}Copy the code

The Shell sort

Descending increment (GAP) sorting algorithm (unstable). It is sorted in several rounds, and each round adjusts the insertion in the gap sequence.

The space complexity is O(1)O(1)O(1) and the time complexity depends on the step sequence.

void
shell_sort(int A[], int n)
{
    int gap;
    foreach_gaps(gap, n, {
        // Insert sort:
        for (int i = gap; i < n; i++) {
            int curr = A[i];
            int j = i - gap;
            for (; j >= 0&& A[j] > curr; j -= gap) { A[j + gap] = A[j]; } A[j + gap] = curr; }}); }Copy the code

The foreach_GAPS walk through the increments and place the step size value into the gap. Multiple sequences of step sizes can be selected (note that the last step of step size must be 1) :

Shell step sequence: N /2in/2^in/2i, worst-case time complexity O(n2)O(n^2)O(n2)

#define for_shell_gap(gap, n, f)                                               \
    for (gap = n >> 1; gap > 0; gap >>= 1)                                     \
        f
Copy the code

Papernov-stasevich step size sequence: 2K −12^ K-12K −1, worst-case time complexity O(N32)O(n^{\ FRAc {3}{2}})O(n23)

// papernov_stasevich_start find the max n s.t. (2^k+1) < n
// return 2^k+1
static inline int
ps_start(int n)
{
    int k = 1, nn = n - 1;
    while (nn > 0&& nn ! =1) {
        nn >>= 1;
        k <<= 1;
    }
    return k + 1;
}

// 2^k+1, ... 65, 33, 17, 9, 5, 3, 1
static inline int
ps_next(int gap)
{
    switch (gap) {
        case 1:
            return - 1; // to stop
        case 3:
            return 1;
        default:
            return ((gap - 1) > >1) + 1; }}#define for_papernov_stasevich_gap(gap, n, f)                                  \
    for (gap = ps_start(n); gap > 0; gap = ps_next(gap))                       \
        f;

Copy the code

There are many other steps, and this Papernov-Stasevich is not the best. The details are on Wikipedia.

Bubble sort

Form a sequence from back to front (I =n-1… 1) : Each time from 0 to I-1, the last one is larger than the previous one is swapped: bubble.

Time complexity: worst O(n2)O(n^2)O(n2), best O(n)O(n)O(n)
Space complexity: O(1)O(1)O(1)

void
bubble_sort(int A[], int n)
{
    for (int i = n - 1; i > 0; i--) {
        int swap_flag = 0;

        for (int j = 0; j < i; j++) {
            if (A[j] > A[j + 1]) {
                swap(A, j, j + 1);
                swap_flag = 1; }}if(! swap_flag) {// This round did not swap, already orderly, early end
            return; }}}Copy the code

Swap is easy to implement:

// swap the subscripts I and j of array A
static inline void
swap(int A[], int i, int j)
{
    if(i ! = j) {// left iji, right jij
        A[i] ^= A[j];
        A[j] ^= A[i];
        A[i] ^= A[j];
    }
    
    // Make sure to judge I! = j,
    // The same memory address will explode with xor swap (all zeros) :
    // x = x ^ x -> x = 0
    // x = x ^ x -> x = 0
    // x = x ^ x -> x = 0
}
Copy the code

Quick sort

Quick sort on A[l…r] (closed interval) :

Pick an axis, and place the one less than the axis in the sequence to the left and the one greater than the axis to the right
And then we do two subsequences on the left and right of the axis, recursively.

Complexity:

Best time complexity: O (nlog ⁡ (n)) O (n \ log (n)) O (nlog (n)), the worst O (n2) to O (n ^ 2) O (n2), average O (nlog ⁡ (n)) O (n \ log (n)) O (nlog (n))
O(log(n))O(log(n))O(log(n))

void
quick_sort(int A[], int l, int r)
{
    if (l < r) {
        int p = partition(A, l, r);
        quick_sort(A, l, p - 1);
        quick_sort(A, p + 1, r); }}// quick_sort_all performs A quicksort on the entire sequence A of length N
void
quick_sort_all(int A[], int n)
{
    return quick_sort(A, 0, n - 1);
}
Copy the code

Partition does quicksort switching:

Let’s take the first elementA[l]For the shaft
What is less than the axis in the sequence is placed to the left of the axis, and what is greater than the axis is placed to the right
Returns the index of the axis

Partition_place: partition_swap: partition_swap: partition_place: partition_swap: partition_place: partition_swap: partition_place: partition_swap: partition_place: partition_swap: partition_place: partition_swap

int
partition_place(int A[], int l, int r)
{
    int pv = A[l];
    while (l < r) {
        while (r > l && A[r] > pv)
            --r;
        if (l < r)
            A[l++] = A[r];
        while (l < r && A[l] < pv)
            ++l;
        if (l < r)
            A[r--] = A[l];
    }
    A[l] = pv;

    return l;
}
Copy the code

int
partition_swap(int A[], int l, int r)
{
    int p = l;

    for (int i = l; i < r; i++) {
        if (A[i] <= A[r]) {
            swap(A, p, i);
            p++;
        }
    }
    swap(A, p, r);

    return p;
}
Copy the code

Selection sort

For each position I, from subscripts 0 to n, select the smallest in A[I…n] (closed interval).

Time complexity O(n2)O(n^2)O(n2)
Space complexity O(1)O(1)O(1)

void
select_sort(int A[], int n)
{
    for (int i = 0; i < n; i++) {
        int smallest = i;
        for (int j = i + 1; j < n; j++) {
            if(A[j] < A[smallest]) { smallest = j; } } swap(A, i, smallest); }}Copy the code

Heap sort

Make the sequence into a large root heap (one whose root nodes are larger than the page), then go out of the root node one by one and rearrange the heap.

Time complexity O(nlog⁡(n))O(n \log(n))O(nlog(n))
Space complexity O(1)O(1)O(1)

void
heap_sort(int A[], int n)
{
    / / set up the heap
    int heap_size = n;
    for (int i = n / 2 - 1; i >= 0; i--) {
        sift(A, i, n - 1);
    }
    // Adjust the heap to exit the root node
    for (int i = n - 1; i >= 0; i--) {
        swap(A, 0, i);
        sift(A, 0, i - 1); }}// sift to create a heap
void
sift(int A[], int l, int r)
{
    int i = l, j = 2 * i + 1;
    int root = A[l];

    while (j <= r) {
        if (j + 1 <= r && A[j] < A[j + 1])
            ++j;
        if (A[j] > root) {
            A[i] = A[j];
            i = j;
            j = 2 * i + 1;
        } else {
            break;
        }
    }

    A[i] = root;
}
Copy the code

It’s easier to understand with maxHeapify from CLRS:

void
heap_sort(int A[], int n)
{
    / / set up the heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        max_heapify(A, i, n - 1);
    }

    // Go to the root node and adjust the heap
    for (int i = n - 1; i >= 0; i--) {
        swap(A, 0, i);
        max_heapify(A, 0, i - 1); }}// max_heapify builds the adjustment function for the large root heap
void
max_heapify(int A[], int i, int n)
{
    // l, r are the children of root i
    int l = (i << 1) + 1;
    int r = l + 1;

    // max = max_idx(A[root], A[l], A[r])
    int max = i;
    if (l <= n && A[l] > A[max])
        max = l;
    if (r <= n && A[r] > A[max])
        max = r;

    // Change the root and continue to adjust backwards
    if (max != i) {
        swap(A, i, max);
        max_heapify(A, max, n);
    }
}
Copy the code

Merge sort

Recursively sort the left and right halves, and then merge

Time complexity O(nlog⁡(n))O(n \log(n))O(nlog(n))
Space complexity O(n)O(n)O(n)

void
merge_sort(int A[], int l, int r)
{
    if (l >= r)
        return;

    int m = (l + r) / 2;
    merge_sort(A, l, m);
    merge_sort(A, m + 1, r);
    merge(A, l, m, r);
}

// merge_sort_all performs merge sort on the entire sequence A of length N
void
merge_sort_all(int A[], int n)
{
    merge_sort(A, 0, n - 1);
}
Copy the code

17. To merge the sorted parts of an array, A[l: m+1] and A[m: r+1], in ascending order:

Back up the array first
The smaller of the left and right halves is placed in the original array
Complete the merge

You need auxiliary arrays, space complexity O(n)O(n)O(n)

void
merge(int A[], int l, int m, int r)
{
    const int INF = 1 << 30;

    // Back up the left and right slices:

    // b = A[l: m+1] + [INF]
    int n1 = (m - l + 1) + 1;
    int* b = malloc(sizeof(int) * n1);
    for (int i = 0, j = l; j <= m; i++, j++) {
        b[i] = A[j];
    }
    b[n1 - 1] = INF;

    // c = A[m: r+1] + [INF]
    int n2 = (r - m) + 1;
    int* c = malloc(sizeof(int) * n2);
    for (int i = 0, j = m + 1; j <= r; i++, j++) {
        c[i] = A[j];
    }
    c[n2 - 1] = INF;

    // Select the smaller pieces from the left and right slices and assemble the sorted array:
    int i = 0, j = 0;
    for (int k = l; k <= r; k++) {
        if (b[i] <= c[j]) {
            A[k] = b[i++];
        } else { // c[i] < b[i]A[k] = c[j++]; }}}Copy the code

The complete code

The complete code is integrated in this GIST:

Gist.github.com/cdfmlr/07b9…

reference

CLRS, 3e
Juejin. Cn/post / 699717…
The day of attendance
king
There are so many others, forget.

That’s about it. I don’t have a passion for sorting algorithms or anything, and I didn’t want to write this article. Algorithm test cases are also written single, so it is not guaranteed to be correct, such as fallacy, but also hope to forgive.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

A variety of sorting algorithm, C language to achieve

Sorting Algorithms

Direct insertion sort

Binary insertion sort

The Shell sort

Bubble sort

Quick sort

Selection sort

Heap sort

Merge sort

The complete code

reference

A variety of sorting algorithm, C language to achieve

Sorting Algorithms

Direct insertion sort

Binary insertion sort

The Shell sort

Bubble sort

Quick sort

Selection sort

Heap sort

Merge sort

The complete code

reference

Related Posts

Make a Valentine’s Day confession in Python

Spring Cloud Alibaba(04) — Seata handles distributed transactions

Python OpenCV Edge Filter Retention (EPF)