Consider the following approach a An algorithm sorts an arra

Consider the following approach a. An algorithm sorts an array of n elements by finding the smallest and largest elements and then exchanges those elements with the elements in the first and last positions in the array. b. Then the size of the array is reduced by two elements after excluding the two elements that are already in the proper positions, and the process is repeated on the remaining part of the array until the entire array is sorted. 2. Write a code to implement the above algorithm 3. Write a driver program to show the novel sorting algorithm works correctly 4. Have your work reviewed by the TA or the Instructor before departing the lab. If you do not complete this during the lab period you will have to visit the TA during Office hours to demonstrate your work. Homework Assignment: l. Write up the algorithm from the in-class portion in pseudocode and give a proof outline that shows this algorithm correctly sorts the array. Your \"proof\" does not have to be very formal.)

Solution

Hi buddy, please find the below java program.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
//This method sorts the given array
static void sort(int arr[]) {
//Calculating the mid
int mid = arr.length/2;
//This loop iterates mid number of times
for (int j = 0; j < mid; j++) {
//Taking the left and right indices
int left = j;
int right = arr.length - j - 1;
int min = Integer.MAX_VALUE;
int minInd = 0;
int max = Integer.MIN_VALUE;
int maxInd = 0;
//Calculating minimum and maximum valued indices in the left and right range
for (int i = left; i <= right; i++) {
if (arr[i] > max) {
max = arr[i];
maxInd = i;
}
if (arr[i] < min) {
min = arr[i];
minInd = i;
}
}
//Replacing the left and right with min and max indices;
int t = arr[left];
arr[left] = arr[minInd];
arr[minInd] = t;
t = arr[right];
arr[right] = arr[maxInd];
arr[maxInd] = t;
}
}
public static void main(String[] args) throws java.lang.Exception {
int arr[] = {2,1,3,5,7,4,6,8};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}

OUTPUT : [1, 2, 3, 5, 4, 6, 7, 8]

PSEUDOCODE :

LOOP j from 0 to MIDDLE
   LEFT = j;
   RIGHT = LENGTH-j-1;
   LOOP i from LEFT to RIGHT
       MIN = min(MIN,ARR[i]);
       MAX = max(MAX,ARR[i]);
   SWAP(LEFT,MIN);
   SWAP(RIGHT,MAX);
  
PROOF OF CORRECTNESS:
   Array is sorted implies that the left element to an element is always lower than the current element and right element to an element is always greater than the current element.
   A[i]<=A[i+1]<=A[i+2] always holds
   We are finding lowest and highest element in the array and placing them at the left and right ends of the array respectively and repeating the process with array obtained by removing the left and right elements. Since the remaining elements in the array lies between left and right most elements we can assume that the array will be sorted in the end.
  
   Given an array arr[l...r];
   Minimum elemnet be arr[m1] and maximum element be arr[m2];
   So for all the elements arr[i]>=arr[m1] and arr[i]<=arr[m2];
   Replace the minimum element with arr[l] and max element with arr[r];
   Now arr[l] <= arr[i] and arr[r] >= arr[i]; So, arr[l] and arr[r] are in their correct positions in the sorted array.
   Repeat the process the arr[l+1] and arr[r-1]. At the end of the process arr[l+1] and arr[r-1] are in the correct positions in the sorted array.
   So, it is guaranteed that in the end array will be sorted.