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. The insertion sort is an example of a brute force algorithm. A brute force algorithm is one that solves a problem in a simple way by computing every possible step. As you run this algorithm you will see how a item is often moved many times until it finds the right place and then the same thing is done with the next item. It isnt very elegant, it works, but it does a LOT OF WORK and is not very efficient. We will define Brute Force in more detail in CS1304. You can copy this code into the Jeliot tool to understand the output that will be required in your algorithm and the operation of a Brute Force Insertion sort algorithm.

# Insertion sort algorithm

import Prog1Tools.IOTools;

public class InsertionSort{

public static void main(String a[]){

int i;

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

insertion_srt(array, array.length);

System.out.print("Values after the sort:");

for(i = 0; i

System.out.print(array[i]+" ");

System.out.println();

}

public static void insertion_srt(int array[], int n){

int exch=0;

for (int i = 1; i < n; i++){

int j = i;

int B = array[i];

while ((j > 0) && (array[j-1] > B)){

array[j] = array[j-1];

j--;

exch++;

}

array[j] = B;

exch++;

}

System.out.println(exch+" Exchanges during sorting");

}

}

In the preceding code example, you will note that the array to be sorted contains 21 random items, which are sorted by the algorithm, which happens to be an insertion sort. Your assignment will be to create your own sort algorithm that implements one of the following types of sort: shellsort, mergesort, quicksort. Please use the same list of items in your sort that are in the preceding example as follows:

12,9,4,99,120,1,3,10,23,45,75,69,31,88,101,14,29,91,2,0,77

As part of your assignment, you must submit both a description of the assignment and how your algorithm works including an Asymptotic analysis of your algorithm. Your analysis must include the efficiency of your algorithm expressed in Big Oh, Big Omega, or Big Theta notation as appropriate.

Please indicate in your description whether your algorithm implements a shellsort, mergesort, or quicksort. This must include a description of how your selected algorithm functions and why it is more efficient than the insertion sort above.

We will obtain another measure of efficiency by comparing the number of exchanges that were required to complete the sort. For the insertion sort above, the required number of exchanges is 114.You should compare this with the number of exchanges required by your sorting algorithm in your description. Please discuss whether your output was what you expected?