Homework answers / question archive / Develop a sorting algorithm

Develop a sorting algorithm

Computer Science

Share With

---

Develop a sorting algorithm. My 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 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");

}

}

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. Practice assignment will be to create my 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?

Further, as part of your assignment, you must include the code of your algorithm. All of these elements of this assignment must be completed and posted to the assignment for Unit 6 by the end of the week for unit 6.

After posting your completed assignment, you must review the work of at least three of your peers. As part of your review, you must copy and paste your peer's code into the Jeliot tool and execute it. If the code does not function properly you should make suggestions on how to correct the problems (if possible). If the efficiency of the algorithm can be improved you should make these suggestions. You should coordinate with your fellow student and follow up on any corrections they make by re-running the code and providing additional feedback. In this assignment each sort routine will be using the same set of unsorted integers. You should compare the metrics of your sort including the number of comparisons and the number of exchanges made as one measure of the efficiency of the sort. Keep in mind that asymptotic analysis can provide us with insight into the efficiency of an algorithm in the worst case, best case and in some situations in the average case. However, we also know that the input of the algorithm has a significant impact on the actual experienced efficiency of an algorithm. As part of your review and discussion of peers work, compare actual efficiency to what was expected from the asymptotic analysis and discuss if the experienced results differ from the expectation of the performance of the algorithm that is based upon the asymptotic analysis and actual experienced performance.

As you review your own algorithm and those of your peers, you should be looking for the following characteristics that our text outlined as being requirements of a 'good' algorithm.

• It must provide the correct output based upon the input
• It must be composed of concrete steps
• There can be NO ambiguity of the flow of the algorithm
• The algorithm must have a finite number of steps that is determinable
• The algorithm must terminate or complete

If either your algorithm or the algorithms of your peers that you are reviewing do not exhibit these characteristics, you should collaboratively determine why the algorithm does not exhibit these characteristics and offer suggestions to correct the algorithm such that it does exhibit these characteristics.