Consider an array A(1... n] which is originally unsorted. One method to sort the
ID: 670907 • Letter: C
Question
Consider an array A(1... n] which is originally unsorted. One method to sort the array is as follows: First find the larges key in the unsorted portion of the array (initially the entire array s unsorted) and swap this with the last position in the unsorted section. This last position is now considered part of the sorted portion. The procedure is repeated until the entire array is sorted. Write an algorithm to sort A as outlined above (in pseudo-code, no i/o. just the single function to do the sorting). How many comparisons will be made in the Average case Worse case Best caseExplanation / Answer
PseudoCode for Sorting
void SortingAlgo(int array[1...n],int n)
for i=n-1 to 0
int lastIndex=i;
for j=i to 0
if(array[j]>array[lastIndex])
lastIndex=j;
//swap the two values
int temp = array[i];
array[i] = array[lastIndex];
array[lastIndex] = temp;
//end For
//end For
A Program in c++
void SortingAlgo(int array[], nsize)
{
for(int i = n- 1; i >= 0; i--)
{
int lastIndex = i;
for(int j = i; j >= 0; j--)
{
if(array[j] > array[lastIndex])
lastIndex = j;
}
int temp = array[i];
array[i] = array[lastIndex];
array[lastIndex] = temp;
}
}
For each case, i.e. Best, Average and WOrst, we shall have complexity of O(n^2) as, in every case we are searchiing the array for maximum value,even if the array is sorted.
The number of comparsions can be easily estimated. If we look at the algorithm, then for each element, we are having a total of n-1 comparisons and atleast one exchange(when it is larger than other elements). So for n elements, there are a total of n-1 exhancges. And for each 'n' element, there are n-1 comparisons, so on adding this..
(n-1)+(n-2)+(n-3)..+..+..+2+1=n(n-1)/2 comparisons, and n-1 exchanges!
So, for each case, best,average or worst, the number of comparsions are n(n-1)/2.