Identifying this form of sorting algorithm and calculating its time complexity

Question

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)

This is just a really slow insertion sort, so O(n^2). Worst case is an array that starts out in reverse order, e.g. int array[] = {9,8,7,6,5,4,3,2,1}; Every time i reaches the end of the sorted section of the array, the algorithm needs to carry the next number all the way back to the beginning of the array. That's the way insertion sort works, but insertion sort does it faster. Then the algorithm wastes a whole bunch of time going forward to find the end of the sorted section. Insertion sort keeps track of where the end of the sorted section is, and just jumps there. — user3386109
– user3386109, Commented Dec 18, 2021 at 2:52
Use the array I suggested. Put a printf("%d\n", i); at the top of the loop. Post the results here. — user3386109
– user3386109, Commented Dec 18, 2021 at 3:01
I already did. i increments until it reaches the end of the sorted section. Then it decrements until it reaches the beginning of the array. — user3386109
– user3386109, Commented Dec 18, 2021 at 3:06
Imagine the algorithm has progressed until the array is [6,7,8,9,5,4,3,2,1] and i=3 and array[i] is the 9. Now the code compares 9 and 5, swaps them, and decrements i. So now array[i] is 8. Compare 8 and 5, swap them, and decrement i. The algorithm has to keep doing that until i is 0 because the 5 has to go at the beginning of the sorted section. — user3386109
– user3386109, Commented Dec 18, 2021 at 3:24
Dennis Ritchie had a great idea when he decided that *(a+i) is to be written as a[i] — Déjà vu
– Déjà vu, Commented Dec 18, 2021 at 3:39

Marcus P · Accepted Answer · 2021-12-18 03:29:15Z

3

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²)

edited Dec 18, 2021 at 3:29

answered Dec 18, 2021 at 2:30

Marcus P

662 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

mindoverflow Over a year ago

The code works as intended. Either way, we are able to circumvent this issue by adding only decrementing if i != 0.

Marcus P Over a year ago

I showed another case. The point is: you need to assert the subarray from index 0 until i is sorted.

mindoverflow Over a year ago

Hey thanks for going over the code. As I had mentioned, does this problem still persist if I only decrement if i != 0?

mindoverflow Over a year ago

Yes now that 20, 30, 10 is used, I see a segmentation error. I don't clearly understand it yet.

mindoverflow Over a year ago

Ah nevermind that array length parameter has to be changed.

|

Collectives™ on Stack Overflow

Identifying this form of sorting algorithm and calculating its time complexity

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related