Hi, I need help with this. Write three programs that performs various sort proce
ID: 3690569 • Letter: H
Question
Hi, I need help with this.
Write three programs that performs various sort processes on an array of 1000 records and an array of 10000 records. There are plenty of records (over 10900) to work with. Load the records in the arrays as per the program requirements (1000 element and 10,000 element). Each record has three data members: a string, a 4-digit integer, and a 7-digit integer. Use either a struct to maintain the arrays of records. Use this data file (http://www.mediafire.com/download/1of48k4s5v6um62/data.txt). Base the sorts on the 4-digit integer.
For each sorting program results provide descriptions that are detailed for anyone to understand. For example
Insertion sort -> Array Size = 10000
# of comparisons=10000
# of item movements = 1685
(Program 1) Sort two arrays of records of (1000 elements and 10,000 elements, respectively) as follows.
a. Use insertion sort to sort the arrays. Print the number of comparisons and the number of item movements.
b. Use Shellsort to sort the array using the function shellSort given in this lesson. Print the number of comparisons and the number of item movements.
(Program 2) Sort an array of 10,000 records using quicksort as follows:
a. Sort the array using pivot as the middle element of the array.
b. Sort the array using pivot as the median of the first, last, and middle elements of the array.
c. Sort the array using pivot as the middle element of the array. However, when the size of any sublist reduces to less than 20, sort the sublist using insertion sort.
d. Sort the array using pivot as the median of the first, last, and middle elements of the array. When the size of any sublist reduces to less than 20, sort the sublist using insertion sort.
e. Calculate and print the CPU time for each of the preceding four steps.
(Program 3) Sort an array of 10,000 records using heapsort
a. Save the code in a notepad text file as heapsort.txt
Use this program as a guide to write the programs above (insertionSort_example.txt - http://www.mediafire.com/download/xsn030ibab3l5iu/insertionSort_example.txt)
Explanation / Answer
package com.java2novice.sorting;
public class MyQuickSort {
private int array[];
private int length;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
MyQuickSort sorter = new MyQuickSort();
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.