Sorting-O

Level 1

Find the big-O running time of a sorting program that does the following:

It takes in a list of integers.
It iterates once through the list to find the largest element, and moves that element to the end.
It repeatedly finds the largest element in the unsorted portion by iterating once through, and moves that element to the end of the unsorted portion.

At the end, the list is sorted low to high.

(Also, try implementing this program in your language of choice.)

O(1)

O(n)

O\big(n^2\big)

O(n\log n)

9 solutions

Ben Frankel
Jan 23, 2014

For a list of integers that is $n$ items long:

The program does one operation (comparison of two numbers) per item in the list. This adds $n$ operations. Next, it iterates over the remaining integers. This adds $n - 1$ operations. By the end, the total amount of operations is $n + (n-1) + (n-2) + ... + 3 + 2 + 1$ , and this can be expressed in closed form as $n + ... + 2 + 1 = \frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n$ .

When finding the big-O running time of a program, we must only consider the asymptotic behavior of its running time, so we can ignore the addition of "slower" terms, and we can ignore coefficients. This leaves us with,

$O \Big( \frac{1}{2}n^2 - \frac{1}{2}n \Big) = O(n^2 - n) = \boxed{O(n^2)}$

The total number of operations should be (n(n+1))/2, right?

Jiayun Zhao - 3 years, 9 months ago

@Jiayun Zhao , I believe you are right. The total count is $\frac{n(n+1)}{2}$ , not $\frac{n(n-1)}{2}$ , but the final answer is still $O(n^2)$ .

Dan George - 3 years, 4 months ago

if there is n item then total number of comparison is (n-1),so series starts with (n-1)and total count = ((n-1)n)/2, right?

Deepak Gupta - 3 years, 2 months ago

Darshana Wagh
May 9, 2017

int [] arr = new int []{1,4,3,2};

for(int j=0; j< arr.Length; j++)
{
    // find larget element
    int maxIndex = 0;
    for(int i=0; i<arr.Length - j; i++)
    {
        if(arr[i] > arr[maxIndex])
        {
            maxIndex = i;
        }           
    }       
    // move to the last
    var temp = arr[arr.Length -1 - j];
    arr[arr.Length -1 - j] = arr[maxIndex];
    arr[maxIndex] = temp;
    // sort remaining list
}

for(int i=0; i< arr.Length; i++)
{
Console.WriteLine(arr[i]);
}

Eddie The Head
Jan 23, 2014

This is simply selection sort.... http://en.wikipedia.org/wiki/Selection_sort

Yes, it is ( I didn't say that above because then people could easily look it up).

I wanted to find an algorithm I could easily explain without catering to any language.

Daniel Chiu - 7 years, 4 months ago

Dave Omri
Jul 19, 2018

For Python lovers

listNum = [9,9,5,6,3,2,7,10,11,12]
maxNum = 0
windowSize = len(listNum)
while windowSize != 0:
    for i in range(windowSize):
        if listNum[i] > listNum[maxNum]:
            maxNum = i
        if i == windowSize-1:
            listNum[i], listNum[maxNum] = listNum[maxNum], listNum[i]
        else: pass
    handsOff = 0
    maxNum = 0
    windowSize -= 1
print(listNum)

Edoardo Nosotti
Dec 9, 2017

import random

items = [random.randint(0,100) for i in range(10)]

print(items)

sorting_range = len(items)

while sorting_range > 0:
    current_max_idx = -1
    for i in range(sorting_range):
        if current_max_idx == -1 or items[i] > items[current_max_idx]:
            current_max_idx = i
    sorting_range = sorting_range - 1
    swap = items[sorting_range]
    items[sorting_range] = items[current_max_idx]
    items[current_max_idx] = swap

print(items)

Anmol Bilal
Dec 21, 2020

The algorithm will have nested loop (2 loops; one inside the other) and the complexity of two nested loops is n2.

Jack Hocking
May 13, 2019

list will have to be iterated through once per element, therefore, the list will be iterated through n*n times

Djordje Krstivojevic
May 31, 2018

Ernesto Reig
Nov 16, 2017

loop an array of N element around N times makes NxN complexity

Sorting-O

9 solutions

0 pending reports