Question

Exercises a - b refer to the recursive algorithm SelectionSort

(a.) In one part of algorithm SelectionSort, the index of the maximum item in a list must be found. This requires comparisons between list elements. In an n-element (unsorted) list, how many such comparisons are needed in the worst case to find the maximum element? How many such comparisons are needed in the average case?

(b.) Defining the basic operation as the comparison of list elements and ignoring the amount of work required to exchange list elements, write a recurrence relation for the amount of work done by selection sort on an n-element list.

Answer 1

Here is the solution to above problem . Please read the explanation for more information

a) In the selectionSort algorithm the number of comaparision for both worst and average case is O(n²) like bubble sort all elements are compared in the selection Sort in each iteration maximum value is found and is Swapper only once to it's correct location. Hence the total number of swaps is O(n) and comparision is O(n²)

b) In the selection Sort Recurrence relation is T(N) = T(N-1) + N where N-1 is the next recursive call and N is the time taken in each function call

PSUEDOCODE

SelectionSort(Array,Size,Index)
{
// Return when starting and size are same
if (Index == Size)
return;
  
//Find the minimum index value using function
int pivot = FindMinimumValueIndex(Array,Index,Size-1);
  
//Swap the values
if (pivot!= Index)
{
   temp=Array[pivot];
   Array[Index]=Array[pivot];
   Array[pivot]=temp;
   }
  
// Recursive Call
SelectionSort(Array,Size,Index+1);
}