Time complexity for a sorting algorithm

Question

I came across the following question while I was doing some exercise:

A sorting algorithm starts from start of the list, scan until two succeeding items that are in the wrong order are found. Swap those items and go back to the beginning. The algorithm ends when the end of the list is reached.

What is the worst-case running time for a list of size n?

I feel that it is similar with bubble sort, but probably worse that that because it doesn't finish the whole pass of scanning the list. But I can't figure out how to calculate its time complexity. I am not sure if the code I came up below for this algorithm is correct. Many thanks for your help!

for (int i=0, i<n , i++){//n is the size of the array
     if (array[i]>array[i+1]){
          swap (array[i], array[i+1]);
          i=0;
     }
}

I am pretty sure it's not insertion sort. Insertion sort is when you pick up an item and insert it to the right location. — stillAFanOfTheSimpsons
– stillAFanOfTheSimpsons, Commented Nov 8, 2014 at 11:40

Raul Guiu · Accepted Answer · 2014-11-08 13:02:41Z

2

The number of comparisons for the worst case (I wont prove the worst case is n, n-1, ... 1 but I assume it is) is a tetrahedral number.

Why?

imagine a sequence

n, n-1, .... 1

so for 1, will be swap when everything before is already on place. So the number of comparisons when is in the last place will be n-1 before is swapped to the second last place. From the second last place it will have to do n - 2 comparisons. Following this logic, and extending to the previous numbers we have for different n:

In other words, for position n i will need to move one number down (1), from position n - 1 I will need to move 2, (1 & 2), from n-2 (1, 2 & 3). Assuming 1,2,3... n is the valid order and they start as n,...3, 2,1.

n = 3 -> 2 + 1 * 2 = 4 
n = 4 -> 3 + 2 * 2 + 3= 10 
n = 5 -> 4 + 3 * 2 + 2 * 3 + 4 = 20 
n = 6 -> 5 + 4 * 2 + 3 * 3 * 2 * 4 + 5 = 35
n = 7 -> 6 + 5 * 2 + 4 * 3 + 3 * 4 + 2 * 5 + 6 = 56 
n = 8 -> 7 + 6 * 2 + 5 * 3 + 4 * 4 + 3 * 5 + 2 * 6 + 7= 84

And this sequence is the tetrahedral numbers.

The formula for the n-th tetrahedral number is represented by the 3rd rising factorial of n divided by the factorial of 3

And as a binomial coeficient:

binomial coeficient

So, it seems that it is O(n^3)

answered Nov 8, 2014 at 13:02

Raul Guiu

2,41423 silver badges39 bronze badges

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

2 Comments

stillAFanOfTheSimpsons Over a year ago

Thank you！Could you explain a bit more what does n = 4 -> 3 + 2 * 2 + 3= 10 stand for? 3 is the number of steps that n (when n = 4) needs to move to its correct position? But why 2*2 +3?

Raul Guiu Over a year ago

Positions p1, p2, p3 and p4, elements in starting position 4, 3, 2, 1. 1 will be swapped from position p4 to position p3 when everything before it are ordered. So this causes 3 comparisons, 2 and 1 will be at one point at position p3 (2 at the beginning and 1 after one swap), that means that to move 2 and 1 from position p3 to position p2 we have 2 * 2 comparisons. 3, 2 and 1 will be moved from p2 to p1 that is one comparison each, 3 * 1. So 3 + 2 * 2 + 3 * 1

Abhishek Bansal · Accepted Answer · 2014-11-08 11:48:01Z

1

This is a bad form of insertion sort. In insertion sort, the complexity of insertion is linear in the length of the array, here it is quadratic. Hence the worst case time complexity of this algorithm is IMO O(n^3).

If the initial array was 4, 3, 2, 1, then the steps of the algorithm would be:

Note that each step in this sequence has a linear time complexity because to get the position of the earliest 'inversion' you scan the entire array from the beginning.

answered Nov 8, 2014 at 11:48

Abhishek Bansal

12.7k4 gold badges34 silver badges46 bronze badges

2 Comments

stillAFanOfTheSimpsons Over a year ago

Could you elaborate on why it's quadratic?

Abhishek Bansal Over a year ago

@stillAFanOfTheSimpsons If you look at the sequence, to insert 1 in its correct position, we require 3 steps (seemingly linear). However each step requires us to scan the entire array from the beginning to first find the swapping position. Hence the total complexity of insertion is quadratic here.

MBo · Accepted Answer · 2014-11-08 20:18:50Z

1

An array may contain O(n^2) inversions. Every run corrects only one inversion and executes O(n) steps (comparisons). So overall time complexity is O(n^3).
The worst case - backward-sorted array with N*(N-1)/2 inversions, exact runtime analysis has already been done by Raul Guiu.

answered Nov 8, 2014 at 20:18

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Comments

M. Page · Accepted Answer · 2014-11-08 11:41:05Z

0

What you descibe is a bubble sort: http://en.wikipedia.org/wiki/Bubble_sort Bubble sort has worst-case and average complexity both О(n2)

answered Nov 8, 2014 at 11:41

M. Page

2,8342 gold badges23 silver badges35 bronze badges

3 Comments

stillAFanOfTheSimpsons Over a year ago

I don't think so. Bubble is to compare every two succeeding items in a pass, but this one goes back to the beginning once it finishes one swap.

M. Page Over a year ago

Yes it is, but the given code is incorrect: it misses an outer iteration, hence О(n2)

smttsp Over a year ago

This is not bubble sort.

smttsp · Accepted Answer · 2014-11-08 12:14:00Z

0

First, this algorithm looks like bubble-sort but slower than that.

Second, this algorithm is doing some non-sense operations, i.e Swap those items and go back to the beginning. For example your initial array is as follows,

10 11 12 13 14 15 16 17 18 19 9

You will iterate till the end, when you see 9, swap it with 18 then go to the beginning of the array and start comparing if(arr[0] < arr[1]) but you already know that it is smaller.

The worst case running time of this is O(n^3). The pseudo code will be something like this:

for i = 0:n-1
    if(arr[i] > arr[i+1]){
        swap(arr[i], arr[i+1])
        i = 0;
    }

answered Nov 8, 2014 at 12:14

smttsp

4,2013 gold badges38 silver badges66 bronze badges

2 Comments

stillAFanOfTheSimpsons Over a year ago

Thanks. I understand the logic how the algorithm works, but I still don't get why the complexity is O(n^3)... Could you explain it a bit more?

smttsp Over a year ago

As you see in my code, to put the last element to first positions, I iterate n^2 times. Assume, this array is reverse order, for each element it was going to do O(n^2) comparison, so it is O(n^3) in the worst case. Number of operation should be n^3/4 or n^3/6, i didnt think of it deeply

Py-Coder · Accepted Answer · 2016-11-20 04:28:17Z

-1

Now Compare both your Code and Bubble sort because it seems to be..

Your code It will give Max O(n^3)

Bubble sort

void bubbleSort(int arr[])
{
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
            {
                // swap temp and arr[i]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

It will give in worst case O(n^2) and even if array is sorted.

answered Nov 20, 2016 at 4:28

Py-Coder

2,2921 gold badge26 silver badges30 bronze badges

Collectives™ on Stack Overflow

Time complexity for a sorting algorithm

6 Answers 6

2 Comments

2 Comments

Comments

3 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

2 Comments

Comments

3 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related