Sorting technique C

Question

I am into programming from past 7-8 months and I generally use selection sort whenever I want to sort arrays or structures. So I got idea and implemented it. selection sort find max OR min value in each loop and place it at one of the border (depends on max or min) and make it out of scope. So I thought why not find max AND min in each loop and move them to borders (min-left and max-right) and reduce the scope from both side by value 1. It would have half of previous time complexity i guess. Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    int *a;
    int n;
    scanf("%d", &n);
    a = malloc (n * sizeof (int));

    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int start = 0, end = n;

    int temp;
    while (start < end){
        int max_index;
        int min_index;

        int max_num = INT_MIN, min_num = INT_MAX;

        for (int i = start; start != end && i < end; i++){
            if (a[i] > max_num){
                max_num = a[i];
                max_index = i;
            }
            if (a[i] < min_num)  {
                min_num = a[i];
                min_index = i;
            }
        }

        if ((max_index == start && min_index == end - 1) || (max_index == end - 1 && min_index == start)){  
            temp = a[end - 1];      //if max and min numbers are at border they will swap two times resulting in same location
            a[end - 1] = a[max_index];
            a[max_index] = temp;
        } else {
            temp = a[end - 1];
            a[end - 1] = a[max_index];
            a[max_index] = temp;

            temp = a[start];
            a[start] = a[min_index];
            a[min_index] = temp;
        }

        start++;
        end--;
    }
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
}

I tested it with 600 int values, Here is the Output. It seems to work fine. Is it better than selection sort or just same. I guess qsort would be be superior to both in terms of speed and efficiency. I looked for it on google and didn't found similar code to this which make me wonder, Is this efficient enough or should I stick with selection sort and qsort.

Answer 1

Your algorithm implements a variant of selection sort called Cocktail Sort or Shaker Sort. It is not significantly faster than selection sort because it uses a similar amount of comparisons, thus has a time complexity of O(N²) just like selection sort.

There are problems in your implementation:

• Your code does not compile on some platforms because you forgot to include the header file <limits.h> where INT_MIN and INT_MAX are defined.

• Your implementation has undefined behavior if the data set contains only the value MIN_INT or MAX_INT because you would then fail to find the smallest or largest element of the slice and min_index and/or max_index would have indeterminate values thus leading to undefined behavior when dereferencing a[max_index] or a[min_index].

• You swap the values if (max_index == end - 1 && min_index == start), causing an incorrect result: the values should be left alone in this case.

• Another special case must be handled explicitly: if min_index == end - 1 then you must swap the min value first as it would be moved when you set the max value in place.

Here is a modified version:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    int status = 0;
    int *a;
    for (int n = 1; n < 100000; n += n / 3 + 1) {
        a = malloc(n * sizeof(int));
        for (int i = 0; i < n; i++)
            a[i] = rand();
        clock_t t = clock();
        for (int start = 0, end = n - 1; start < end; start++, end--) {
            int max_index = start;
            int min_index = start;
            int max_num = a[max_index];
            int min_num = a[min_index];
            int temp;

            for (int i = start + 1; i <= end; i++) {
                if (max_num < a[i])
                    max_num = a[max_index = i];
                if (min_num > a[i])
                    min_num = a[min_index = i];
            }
            if (min_index == end) {
                if (max_index == start) {
                    /* single swap needed */
                    temp = a[end];
                    a[end] = a[start];
                    a[start] = temp;
                    continue;
                }
                /* first swap the smallest value at the first position */
                temp = a[start];
                a[start] = a[min_index];
                a[min_index] = temp;
                /* then swap the largest value at the last position */
                temp = a[end];
                a[end] = a[max_index];
                a[max_index] = temp;
            } else {
                /* first swap the largest value at the last position */
                temp = a[end];
                a[end] = a[max_index];
                a[max_index] = temp;
                /* then swap the smallest value at the first position */
                temp = a[start];
                a[start] = a[min_index];
                a[min_index] = temp;
            }
        }
        t = clock() - t;
        for (int i = 1; i < n; i++) {
            if (a[i-1] > a[i]) {
                printf("sorting error n=%d, a[%d] = %d > %d = a[%d]\n",
                       n, i-1, a[i-1], a[i], i);
                status = 1;
                break;
            }
        }
        free(a);
        printf("n=%d: %.3fms\n", n, t * 1000.0 / CLOCKS_PER_SEC);
    }
    return status;
}

Answer 2

It would have half of previous time complexity i guess.

O(0.5 * n^2) is still O(n^2). A good qsort() is expected O(n* ln(n)).

Is this efficient enough or should I stick with selection sort and qsort.

Tough to beat decades of many programmers experience.

Keep in mind qsort() does not have to use the quick sort algorithm. A good qsort() may use a combination of algorithms.