Question

Consider an array A[1...n] which is originally unsorted. One method to sort the array is as follows: First find the largest 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. (a) Write an algorithm to sort A as outlined above (in pseudo-code, no i/o, just the single function to do the sorting).

Answer 1

Find the code for the above question below, read the comments provided in the code for better understanding. If found helpful please do upvote this.
Please refer to the screenshot of the code to understand the indentation of the code.

Part A

Algorithm

1. Run a first loop which loop through all the lements from 1 till n-1 , let ie be i
2. Run anotther loop inside it which runs from 1 till n-i-1 , let it be j
3. Now compare the element at jth index with element at j+1 index , if it is greater then swap the, else continue the loop
4. That's all after the loop ends , the array will be sorted,

Code

void Sort(int arr[], int n)
{
for (int i = 1; i <= n-1; i++)
  
for (int j = 1; j <= n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
  

Screenshot of code

void Sort(int arr[], int n) { for (int i = 1; i <= n-1; i++) for (int j = 1; j <= n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); } }

Part B

1. Average Case -> n(n-1) comparisons are done
2. Worst case -> n(n-1) comparisons are done
3. Best Case -> n(n-1) comaprisons are done

This is becasue everytime both loops need to be exceuted and all elements need to checked