CODEWITHSUNDEEP
algorithmsortingdata-structures
flash
flash

Reputation: 1519

number of comparisons needed to sort n values?

I am working on revised selection sort algorithm so that on each pass it finds both the largest and smallest values in the unsorted portion of the array. The sort then moves each of these values into its correct location by swapping array entries.

My question is - How many comparisons are necessary to sort n values?

In normal selection sort it is O(n) comparisons so I am not sure what will be in this case?

Upvotes: 2

Views: 1658

Answers (2)

virmis_007
virmis_007

Reputation: 173

In your version of selection sort, first you would have to choose two elements as the minimum and maximum, and all of the remaining elements in the unsorted array can get compared with both of them in the worst case.

Let's say if k elements are remaining in the unsorted array, and assuming you pick up first two elements and accordingly assign them to minimum and maximum (1 comparison), then iterate over the rest of k-2 elements, each of which can result in 2 comparisons.

So, total comparisons for this iteration will be = 1 + 2*(k-2) = 2*k - 3 comparisons.

Here k will take values as n, n-2, n-4, ... since in every iteration two elements get into their correct position. The summation will result in approximately O(n^2) comparisons.

Upvotes: 0

MBo
MBo

Reputation: 80232

Normal selection sort requires O(n^2) comparisons.

At every run it makes K comparisons where K is n-1, n-2, n-3...1, and sum of this arithmetic progression is (n*(n-1)/2)

Your approach (if you are using optimized min/max choice scheme) use 3/2*K comparisons per run, where run length K is n, n-2, n-4...1

Sum of arithmetic progression with a(1)=1, a(n/2)=n, d=2 together with 3/2 multiplier is

 3/2 * 1/2 * (n+1) * n/2 = 3/8 * n*(n+1) = O(n^2)

So complexity remains quadratic (and factor is very close to standard)

Upvotes: 2

Related Questions