While experimenting with sorting, I came up with a sort that seems to resemble some sort of insertion sort.

The difference would be that upon a swap, I'm not having to compare elements (worst-case) from element index up to index 0.

It also resembles something akin to a divide-and-conquer sorting algorithm in that it emulates a sorted sector and an unsorted one within the same array.

How I look at it is that initially I'll assign the current element as the first element. Then I'll compare the current element to the next one. If current is greater, I swap the elements. Then I decrement so as to keep current index same.

Otherwise, I increment to advance current index.

This means my current will always be the most updated reference value. The other values that were compared are always lesser and sorted.

Please refer to the code:

#include<stdio.h>

void printArray(int *a, int l)
{
    int i = 1;
    printf("[%d", a[0]);
    while(i < l)
    {
        printf(", %d", a[i]);
          i;
    }
    printf("]\n");
}

void whatSort(int *a, int l)
{
    int i = 0;
    int temp;

    while(i < (l - 1))
    {
        if(*(a   i) > *(a   i   1))
        {
            temp = *(a   i);
            *(a   i) = *(a   i   1);
            *(a   i   1) = temp;
            --i;
        }
        else
        {
              i;
        }
    }
}

int main(void)
{
    //int array[] = {42, 18, 74, 2, 35, 92, 37, 25};
    int array[] = {6, 5, 3, 1, 8, 7, 2, 4};
    printArray(array, 8);
    whatSort(array, 8);
    printArray(array, 8);
    return 0;
}

I'm pretty sure this sort of sort (pun intended) already exists, but I'm unable to find out the name. Would be great to know what it's called. Nevertheless, I would like assistance in calculating the runtime complexity of the piece of code for this sort only. This is what I've come up with. Any help would be much appreciated.

For this particular case, it is assumed that each operation takes 1 time unit.

Declaration
Assignment
Declaration

Loop condition will run l - 1 times:
    Comparison
    Subtraction

Loop inside code will run l - 2 times:
    IF statement:
        Dereference
            Addition
        Comparison
        Dereference
            Addition
            Addition
    Assignment
    Dereference
        Addition
    Dereference
        Addition
    Assignment
    Dereference
        Addition
        Addition
    Dereference
        Addition
        Addition
    Assignment
    Decrement

    OR

    ELSE statement:
        Increment

Ultimately, I'm coming up with O(n) where:

Worst case = 3   [2 * (l - 1)]   [6 * (l - 2)]   [14 * (l - 2)]
    O(22n - 39)
    O(n)
Best case = 3   [2 * (l - 1)]   [6 * (l - 2)]   (l - 2)
    O(9n - 13)
    O(n)

CodePudding user response：

Sorry, but there are no sorting algorithms better than O(n log n), unless you put some restrictions to the input.

Currently this code does not work.

For example, if the first element is greater then the second (which is the case in your example), then i is decremented. Initially i=0, so now i=-1. The loop restarts, and you try to access a[-1], and Segmentation fault occurs. The error is

Then I decrement so as to keep current index same.

That`s not what happens, the index is decremented, as you said, so the value is not kept.

This is the ouput

EDIT:

Even if this case is corrected, the following is not true

Loop inside code will run l - 2 times:

The algorithm always tries to get (i 1)-th element to the correct position, bringing it at worst to the first position.

When index == 0, you make at most one swap. When index == 1, you make at most two swaps. When index == 2, you make at most three swaps.

This happens until you reach the end of the array. So, 1x2x3x...x(n-1), which is O(n²)