Java algorithms to be included in your analysis are: Selection Sort, Insertion S
ID: 644939 • Letter: J
Question
Java algorithms to be included in your analysis are: Selection Sort, Insertion Sort, Merge Sort, Quick Sort. You will run and time the algorithms under the following inputs:
List of 100 numbers drawn from 0--9.
List of 100 numbers drawn from 0--99.
List of 100 numbers drawn from 0--999.
List of 1000 numbers drawn from 0--99.
List of 1000 numbers drawn from 0--999.
List of 1000 numbers drawn from 0--9999.
List of 10000 numbers drawn from 0--999.
List of 10000 numbers drawn from 0--9999.
List of 10000 numbers drawn from 0--99999.
List of 100000 numbers drawn from 0--9999.
List of 100000 numbers drawn from 0--99999.
List of 100000 numbers drawn from 0--999999.
code so far:
import java.util.Random;
public class SortingAlgorithms {
/**
* @param args
*/
public static void main(String[] args) {
int[] list = new int[10000000];
Random rand = new Random();
for (int i = 0; i < list.length; ++i) {
list[i] = rand.nextInt(1000000);
}
long initTime = System.currentTimeMillis();
quickSort(list);
long finalTime = System.currentTimeMillis();
System.out.println(finalTime - initTime);
// System.out.println(Arrays.toString(quickSort(new int[] { 621, 306, 173, 937,
// 345, 42, 450 })));
}
public static int[] countingSort(int[] numbers) {
int[] counter = new int[1000000];
int[] result = new int[numbers.length];
for (int i = 0; i < numbers.length; ++i) {
++counter[numbers[i]];
}
for (int i = 1; i < counter.length; ++i) {
counter[i] += counter[i - 1];
}
for (int i = 0; i < result.length; ++i) {
result[--counter[numbers[i]]] = numbers[i];
}
return result;
}
public static int[] radixSort(int[] numbers, int radix) {
int[] result = numbers;
for (int pos = 1; pos <= radix; ++pos) {
result = modCountingSort(result, pos);
}
return result;
}
private static int getDigit(int number, int pos) {
int pow = (int)Math.pow(10, pos);
int rem = number % pow;
return rem / (pow / 10);
}
public static int[] modCountingSort(int[] numbers, int pos) {
int[] counter = new int[10];
int[] result = new int[numbers.length];
for (int i = 0; i < numbers.length; ++i) {
++counter[getDigit(numbers[i], pos)];
}
for (int i = 1; i < counter.length; ++i) {
counter[i] += counter[i - 1];
}
for (int i = result.length-1; i >= 0; --i) {
result[--counter[getDigit(numbers[i], pos)]] = numbers[i];
}
return result;
}
public static int[] quickSort(int[] numbers) {
quickSortHelper(numbers, 0, numbers.length - 1);
return numbers;
}
private static void quickSortHelper(int[] numbers, int init, int last) {
if ((last - init) < 1 || (last < 0)) {
return;
}
int pivotIndex = partitionList(numbers, init, last);
quickSortHelper(numbers, init, pivotIndex - 1);
quickSortHelper(numbers, pivotIndex + 1, last);
}
private static int partitionList(int[] numbers, int init, int last) {
int lastAssignedPos = init;
for (int i = init; i < last; ++i) {
if (numbers[i] < numbers[last]) {
swap(numbers, lastAssignedPos, i);
++lastAssignedPos;
}
}
swap(numbers, last, lastAssignedPos);
return lastAssignedPos;
}
public static int[] mergeSort(int[] numbers) {
return mergeSortHelper(numbers, 0, numbers.length - 1);
}
private static int[] mergeSortHelper(int[] numbers, int init, int last) {
if ((last - init) == 0) {
return new int[] { numbers[last] };
}
int mid = (last + init) / 2;
int[] subList1 = mergeSortHelper(numbers, init, mid);
int[] subList2 = mergeSortHelper(numbers, mid + 1, last);
return merge(subList1, subList2);
}
private static int[] merge(int[] subList1, int[] subList2) {
int[] result = new int[subList1.length + subList2.length];
int sub1First = 0;
int sub2First = 0;
for (int i = 0; i < result.length; ++i) {
if (sub1First == subList1.length) {
result[i] = subList2[sub2First++];
} else if (sub2First == subList2.length) {
result[i] = subList1[sub1First++];
} else if (subList1[sub1First] <= subList2[sub2First]) {
result[i] = subList1[sub1First++];
} else {
result[i] = subList2[sub2First++];
}
}
return result;
}
public static int[] bubbleSort(int[] numbers) {
boolean swapped = false;
do {
swapped = false;
for (int i = 0; i < (numbers.length - 1); ++i) {
if (numbers[i] > numbers[i + 1]) {
swap(numbers, i, i + 1);
swapped = true;
}
}
} while (swapped);
return numbers;
}
public static int[] selectionSort(int[] numbers) {
for (int i = 0; i < numbers.length - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < numbers.length; ++j) {
if (numbers[j] < numbers[minIndex])
minIndex = j;
}
swap(numbers, minIndex, i);
}
return numbers;
}
public static int[] insertionSort(int[] numbers) {
for (int i = 1; i < numbers.length; ++i) {
for (int j = i; j > 0; --j) {
if (numbers[j] < numbers[j - 1]) {
swap(numbers, j, j - 1);
} else {
break;
}
}
}
return numbers;
}
private static void swap(int[] numbers, int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
public static int[] recInsertSort(int[] list) {
return recSortHelper(0, list);
}
private static int[] insert(int init, int[] list) {
for (int i = init; i < list.length - 1; ++i) {
if (list[i] > list[i + 1]) {
swap(list, i, i + 1);
} else {
break;
}
}
return list;
}
private static int[] recSortHelper(int init, int[] list) {
if (init == (list.length - 1)) {
return list;
} else {
return insert(init, recSortHelper(init + 1, list));
}
}
}
Explanation / Answer
import java.util.Random;
public class SortingAlgorithms {
/*method to fill the list with random numbers*/
public void fillList(int[] list,int max){
Random rand = new Random();
for (int i = 0; i < list.length; ++i) {
list[i] = rand.nextInt(max);
}
}
/*method to perform selection sort*/
public void selectionSort(int[] list){
for (int i = 0; i < list.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < list.length; j++)
if (list[j] < list[index])
index = j;
int smallerNumber = list[index];
list[index] = list[i];
list[i] = smallerNumber;
}
}
/*method to perform insertion sort*/
public void insertionSort(int[] list){
int n = list.length;
for (int j = 1; j < n; j++) {
int key = list[j];
int i = j-1;
while ( (i > -1) && ( list [i] > key ) ) {
list [i+1] = list [i];
i--;
}
list[i+1] = key;
}
}
/*method to perform merge sort*/
public void mergeSort(int[] list,int low,int high){
int N = high - low;
if (N <= 1)
return;
int mid = low + N/2;
// recursively sort the array
mergeSort(list, low, mid);
mergeSort(list, mid, high);
// merge the two sorted sub arrays
int[] temp = new int[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid)
temp[k] = list[j++];
else if (j == high)
temp[k] = list[i++];
else if (list[j]<list[i])
temp[k] = list[j++];
else
temp[k] = list[i++];
}
for (int k = 0; k < N; k++)
list[low + k] = temp[k];
}
/*method to perform quick sort*/
public void quickSort(int[] list,int low,int high){
int i = low, j = high;
int temp;
int pivot = list[(low + high) / 2];
/** partition the list**/
while (i <= j)
{
while (list[i] < pivot)
i++;
while (list[j] > pivot)
j--;
if (i <= j)
{
/** swap the elements**/
temp = list[i];
list[i] = list[j];
list[j] = temp;
i++;
j--;
}
}
/** recursively sort the lower half **/
if (low < j)
quickSort(list, low, j);
/** recursively sort the upper half **/
if (i < high)
quickSort(list, i, high);
}
public static void main(String[] args) {
//declare the lists
int[] list1=new int[100];
int[] list2=new int[100];
int[] list3=new int[100];
int[] list4=new int[1000];
int[] list5=new int[1000];
int[] list6=new int[1000];
int[] list7=new int[10000];
int[] list8=new int[10000];
int[] list9=new int[10000];
int[] list10=new int[10000];
int[] list11=new int[10000];
int[] list12=new int[10000];
//create a list consisting of all the lists
int[][] list={list1,list2,list3,list4,list5,list6,list7,list8,list9,list10,list11,list12};
long initTime,finalTime; //variable to hold the start and end time
SortingAlgorithms sa=new SortingAlgorithms(); //create an instance of class SortingAlgorithms
/*fill all the lists with random numbers*/
sa.fillList(list1,9); //fill list with random numbers from 0--9
sa.fillList(list2,99); //fill list with random numbers from 0--99
sa.fillList(list3,999); //fill list with random numbers from 0--999
sa.fillList(list4,99); //fill list with random numbers from 0--99
sa.fillList(list5,999); //fill list with random numbers from 0--999
sa.fillList(list6,9999); //fill list with random numbers from 0--9999
sa.fillList(list7,999); //fill list with random numbers from 0--999
sa.fillList(list8,9999); //fill list with random numbers from 0--9999
sa.fillList(list9,99999); //fill list with random numbers from 0--99999
sa.fillList(list10,9999); //fill list with random numbers from 0--9999
sa.fillList(list11,99999); //fill list with random numbers from 0--99999
sa.fillList(list12,999999); //fill list with random numbers from 0--999999
int i=1;
for(int[] l:list){ //take each list and perform selection sort, insertion sort, merge sort and quick sort with it
int[] temp=new int[l.length]; //create a temp list
System.arraycopy(l, 0, temp, 0, l.length); //copy the list into a temp list so that the original list does not get sorted and can be used again to perform a different sort with it
initTime = System.currentTimeMillis(); //record the system time before the sort
sa.selectionSort(temp); //perform selection sort
finalTime = System.currentTimeMillis(); //record the system time after the sort
System.out.println("Time taken to perform selection sort on list "+i+": "+(finalTime-initTime)+" ms"); //display the time taken to perform the sort
System.arraycopy(l, 0, temp, 0, l.length); //copy the list into a temp list so that the original list does not get sorted and can be used again to perform a different sort with it
initTime = System.currentTimeMillis(); //record the system time before the sort
sa.insertionSort(temp); //perform insertion sort
finalTime = System.currentTimeMillis(); //record the system time after the sort
System.out.println("Time taken to perform insertion sort on list "+i+": "+(finalTime-initTime)+" ms"); //display the time taken to perform the sort
System.arraycopy(l, 0, temp, 0, l.length); //copy the list into a temp list so that the original list does not get sorted and can be used again to perform a different sort with it
initTime = System.currentTimeMillis(); //record the system time before the sort
sa.mergeSort(temp,0,temp.length); //perform merge sort
finalTime = System.currentTimeMillis(); //record the system time after the sort
System.out.println("Time taken to perform merge sort on list "+i+": "+(finalTime-initTime)+" ms"); //display the time taken to perform the sort
System.arraycopy(l, 0, temp, 0, l.length); //copy the list into a temp list so that the original list does not get sorted and can be used again to perform a different sort with it
initTime = System.currentTimeMillis(); //record the system time before the sort
sa.quickSort(temp,0,temp.length-1); //perform quick sort
finalTime = System.currentTimeMillis(); //record the system time after the sort
System.out.println("Time taken to perform quick sort on list "+i+": "+(finalTime-initTime)+" ms"); //display the time taken to perform the sort
i++;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.