Homework answers / question archive / Develop a sorting algorithm

Develop a sorting algorithm

Computer Science

Share With

---

Develop a sorting algorithm. am implementation of a the shellsort, mergesort, or quicksor. use an array of integers of at least 20 different items. The items in the list must be in a random order. sort the list using the sorting algorithm 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 isn't 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 <array.length; 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");

}

}

, mergesort, quicksort. Please use the same list of items in your sort that are in the preceding example as follows:Please indicate in your description whether your algorithm implements a shellsort, mergesort, or quicksort. This must include a

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

 

Asymptotic analysis of your algorithm. algorithm expressed in Big Oh, Big Omega, or Big Theta notation .

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.

• Jeliot tool and execute it.