Develop a sorting algorithm. Your sorting algorithm may only be an implementation of a the shellsort, mergesort, or quicksort. Your algorithm must use an array of integers of at least 20 different items. The items in the list must be in a random order. You algorithm must sort the list using the sorting algorithm that you have chosen and keep track of the number of exchanges that are required to sort the list. This value along with the contents of the sorted list must be displayed as output to the algorithm to the console.

The following algorithm implements a sorting algorithm that meets the requirements of this assignment with the exception of the fact that it sorts the list using an insertion sort.

import java.util.*; public class QuickSortAlgorithm {

private int arr[ ] private int len; public static int c = 0;

public void sort(int[ ] inArr) {

if (inArr == null || inArr.length == 0) {

return;

}

this.arr = inArr;

len = inArr.length;

qSort(0, len - 1); // call qSort with lower and upper index

}

private void qSort(int bottomIdx, int topIdx) {

int b = bottomIdx;

int t = topIdx;

// determine the pivot point as the middle index

int pvt = arr[bottomIdx+(topIdx-bottomIdx)/2]; // pick pivot value from center

// divide into two arrays using pivot point

while (b <= t) { // find number in left that is greater than the

// value in the pivot position and find number in right

// that is less than pivot value. When two values are

// found, switch the number with each other.

while (arr[b] < pvt) {

b++; // when index less than pivot point, increment by b

}

while (arr[t] > pvt) {

t--; // when index is greater than pivot point, drecrement by 1

}

if (b <= t) {

exchElements(b, t); // if b <= t, increment or decrement index

b++;

t--;

}

}

// call qSort() recursively using current value of t

if (bottomIdx < t){

qSort(bottomIdx, t);

}

// call qSort() recursively using current value of b

if (b < topIdx){

qSort(b, topIdx);

}

}

// function to swap the two values

private void exchElements(int b, int t) {

// Increment exchange count when values are not equal & exchange values

if (b != t) {

System.out.println(" Exch values: " + arr[b] + " and " + arr[t]);

c++;

int temp = arr[b];

arr[b] = arr[t];

arr[t] = temp;

}

}

public static void main(String a[]){

QuickSortAlgorithm sorter = new QuickSortAlgorithm();

// Unsorted Input

int[ ] input = {12,9,4,99,120,1,3,10,23,45,75,69,31,88,101,14,29,91,2,0,77};

// Sorted Inut

// int[ ] input = {0,1,2,3,4,9,10,12,14,23,29,31,45,69,75,77,88,91,99,101,120};

// Reverse Sorted input

// int[ ] input = {120,101,99,91,88,77,75,69,45,31,29,23,14,12,10,9,4,3,2,1,0};

System.out.println(" >> Quick Sort Input <<");

for(int i = 0; i < input.length; i++){

System.out.print(input[i]);

System.out.print(" ");

}

System.out.println(" ");

// Sort Input file

sorter.sort(input);

// Display sorted results

System.out.println(" >> Quick Sort Sorted output <<");

for(int i = 0; i < input.length; i++){

System.out.print(input[i]);

System.out.print(" ");

}

System.out.println( " Value Exchange occurred " + c + " times");

}

}