CODEWITHSUNDEEP
sortingbig-o
ebeth
ebeth

Reputation: 163

Big Theta Notation and Selection Sort

What would be the best-case and worst-case complexity in Big-Theta (T) notation of the selection sort algorithm when the array grows by repeatedly appending a 19?

For instance:

[ 19, 13, 7, 19, 12, 16, 19 ],
[ 19, 13, 7, 19, 12, 16, 19, 19 ],
[ 19, 13, 7, 19, 12, 16, 19, 19, 19 ]

Et cetera. n is used to represent the length of the array.

So we're adding the same number to the end of the array, but this number also happens to be the largest number so it would stay at the end of the array. Does this mean that it really doesn't have any affect on the efficiency? I'm very confused.

Upvotes: 1

Views: 5090

Answers (2)

Soner from The Ottoman Empire
Soner from The Ottoman Empire

Reputation: 20911

Ascending order,

  1. Find the minimum value in the list
  2. Swap it with the value in the first position
  3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

So, we have to examine the rest of all elements rain or shine to obtain the minimum by checking, even if same elements are there, up to the last element. 

A - an array containing the list of numbers
numItems - the number of numbers in the list

for i = 0 to numItems - 1
    for  j = i+1 to numItems               
        if A[i] > A[j]
            // Swap the entries
            Temp = A[i]
            A[i] = A[j]
            A[j] = Temp          
        End If    
    Next j
Next i

As you can see the above pseudo-code, both loops iterate up to end of their limits without any condition. So it gives θ(n²). However, O(n) average, θ(n) worst and θ(1) best cases for swap circumstance.

enter image description here

Upvotes: 1

andy256
andy256

Reputation: 2881

No, it has no effect on the efficiency.

In selection sort, the performance is N^2 because of the nested loops. Even though the elements at the end do not need to be swapped, the loops will still compare them.

So, to answer your exact question: since the best case, worst case, and average case performance are all N^2, and there is no effect on efficiency, there is no change in the performance.

Upvotes: 0

Related Questions