In my boredom today I decided to see if I could improve on a basic bubble sort without (knowingly) copying prior work. I know there have been many attempts to do so, and my approach seems closest to the cocktail shaker sort, but that doesn't seem to quite match.

In the below code it scans forward, but as soon as a swap is necessitated, it scans backwards until it finds a sorted pair, then picks up where it left off to scanning forward.

Consider sorting an input array [1 4 2 0 8]:

1. [1 4] is sorted. No swap needed.
2. [4 2] is not sorted. Swap to [2 4]. Begin scanning backward.
3. [1 2] is sorted. Continue forward.
4. [4 0] is not sorted. Swap to [0 4]. Begin scanning backward.
5. [2 0] is not sorted. Swap to [0 2].
6. [1 0] is not sorted. Swap to [0 1]. Reach beginning of array. Continue forward.
7. [4 8] is sorted. No swap needed.
8. End of array.

1 4 2 0 8
1 4 2 0 8
1 2 4 0 8
1 2 0 4 8
1 0 2 4 8
0 1 2 4 8

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void sort(int *arr, size_t n) {
    for (size_t i = 0; i < n - 1; i  ) {
        if (arr[i] > arr[i 1]) {
            swap(&arr[i], &arr[i 1]);
            
            for (size_t j = i; j > 0 && arr[j-1] > arr[j]; j--) {
                swap(&arr[j-1], &arr[j]);
            }           
        }
    }
}

Have I unwittingly copied something that didn't come up in my research, and if so, does it have a name?

CodePudding user response：

This is insertion sort.

In your implementation there are two places where swap is called. The first one is really a first case of the one that is in the loop. If you would change the loop variable of the outer loop so that it runs from 1 to n-1 instead of 0 to n-2 (same number of iterations), then this separate swap can be dropped, as it will be done in the first iteration of the inner loop:

void sort(int *arr, size_t n) {
    for (size_t i = 1; i < n; i  ) { // i is one more than in your version
        for (size_t j = i; j > 0 && arr[j-1] > arr[j]; j--) {
            swap(&arr[j-1], &arr[j]);
        }
    }
}

And now compare this with the (first) pseudo code that Wikipedia gives for insertion sort:

Pseudocode of the complete algorithm follows, where the arrays are zero-based:

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i   1
end while

It has exactly the same logic.

It is nice when you come to a certain algorithm by working it out for yourself before finding out it is actually an established algorithm. I bet you'll now never forget what insertion sort is.

You may want to read the rest of the Wikipedia article as it points out some improvements to this.