Java algorithms to be included in your analysis are: Selection Sort, Insertion S
ID: 644944 • 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
Program Code:
import java.util.Random;
public class SortingAlgorithms
{
//generate list of integers as static
static int[][] list = new int[12][];
static int[] list1=new int[100];
static int[] list2=new int[100];
static int[] list3=new int[100];
static int[] list4=new int[1000];
static int[] list5=new int[1000];
static int[] list6=new int[1000];
static int[] list7=new int[10000];
static int[] list8=new int[10000];
static int[] list9=new int[10000];
static int[] list10=new int[100000];
static int[] list11=new int[100000];
static int[] list12=new int[100000];
//main function
public static void main(String[] args)
{
//create a string of array that holds the names of the sort
String algorithm[]={"Quick sort", "Merge Sort", "Selection Sort", "Insertion Sort","Bubble Sort"};
//call the display method to inform that which is hold which type of
//numbers
displayList();
//generate random numbers into the respective lists
generatelist();
//assign all the list's into the list of 2-D array
list[0]=list1;
list[1]=list2;
list[2]=list3;
list[3]=list4;
list[4]=list5;
list[5]=list6;
list[6]=list7;
list[7]=list8;
list[8]=list9;
list[9]=list10;
list[10]=list11;
list[11]=list12;
//print the respective resultant run time of each list by calling
//each sorting algorithm.
System.out.println();
System.out.println("**************************************************");
System.out.println();
System.out.println("The run time in nana seconds by the "+algorithm[0]+" for the below list are: ");
for(int i=0;i<list.length;i++)
{
System.out.println("The time taken for the list "+(i+1)+" is: ");
quickSortTimingForAllList(list[i]);
}
System.out.println();
System.out.println("**************************************************");
System.out.println();
System.out.println("The run time by the "+algorithm[1]+" for the below list are: ");
for(int i=0;i<list.length;i++)
{
System.out.println("The time taken for the list "+(i+1)+" is: ");
MergeSortTimingForAllList(list[i]);
}
System.out.println();
System.out.println("**************************************************");
System.out.println();
System.out.println("The run time by the "+algorithm[2]+" for the below list are: ");
for(int i=0;i<list.length;i++)
{
System.out.println("The time taken for the list "+(i+1)+" is: ");
SelectionSortTimingForAllList(list[i]);
}
System.out.println();
System.out.println("**************************************************");
System.out.println();
System.out.println("The run time by the "+algorithm[3]+" for the below list are: ");
for(int i=0;i<list.length;i++)
{
System.out.println("The time taken for the list "+(i+1)+" is: ");
InsertionSortTimingForAllList(list[i]);
}
System.out.println();
System.out.println("**************************************************");
System.out.println();
System.out.println("The run time by the "+algorithm[4]+" for the below list are: ");
for(int i=0;i<list.length;i++)
{
System.out.println("The time taken for the list "+(i+1)+" is: ");
BubbleSortTimingForAllList(list[i]);
}
System.out.println();
System.out.println("**************************************************");
System.out.println();
}
//generatelist will generate the random numbers with in the
//given range
public static void generatelist()
{
list1 = generateRandomNumbers(100, 9);
list2 = generateRandomNumbers(100, 99);
list3 = generateRandomNumbers(100, 999);
list4 = generateRandomNumbers(1000, 99);
list5 = generateRandomNumbers(1000, 999);
list6 = generateRandomNumbers(1000, 9999);
list7 = generateRandomNumbers(10000, 999);
list8 = generateRandomNumbers(10000, 9999);
list9 = generateRandomNumbers(10000, 99999);
list10 = generateRandomNumbers(100000, 9999);
list11 = generateRandomNumbers(100000, 99999);
list12 = generateRandomNumbers(100000, 999999);
}
//displayList will display the menu
public static void displayList()
{
System.out.println("1. List of 100 numbers drawn from 0--9.");
System.out.println("2. List of 100 numbers drawn from 0--99.");
System.out.println("3. List of 100 numbers drawn from 0--999.");
System.out.println("4. List of 1000 numbers drawn from 0--99.");
System.out.println("5. List of 1000 numbers drawn from 0--999.");
System.out.println("6. List of 1000 numbers drawn from 0--9999.");
System.out.println("7. List of 10000 numbers drawn from 0--999.");
System.out.println("8. List of 10000 numbers drawn from 0--9999.");
System.out.println("8. List of 10000 numbers drawn from 0--99999.");
System.out.println("10. List of 100000 numbers drawn from 0--9999.");
System.out.println("11. List of 100000 numbers drawn from 0--99999.");
System.out.println("12. List of 100000 numbers drawn from 0--999999.");
}
//quickSortTimingForAllList method will contain a list
//depending on the the quickSort method is called and the respective
//list run time is calculated
public static void quickSortTimingForAllList(int[] list)
{
long initTime = System.nanoTime();
quickSort(list);
long finalTime = System.nanoTime();
System.out.println(finalTime - initTime);
}
//MergeSortTimingForAllList method will contain a list
//depending on the the mergeSort method is called and the respective
//list run time is calculated
public static void MergeSortTimingForAllList(int[] list)
{
long initTime = System.nanoTime();
mergeSort(list);
long finalTime = System.nanoTime();
System.out.println(finalTime - initTime);
}
//BubbleSortTimingForAllList method will contain a list
//depending on the the bubbleSort method is called and the respective
//list run time is calculated
public static void BubbleSortTimingForAllList(int[] list)
{
long initTime = System.nanoTime();
bubbleSort(list);
long finalTime = System.nanoTime();
System.out.println(finalTime - initTime);
}
//SelectionSortTimingForAllList method will contain a list
//depending on the the selectionSort method is called and the respective
//list run time is calculated
public static void SelectionSortTimingForAllList(int[] list)
{
long initTime = System.nanoTime();
selectionSort(list);
long finalTime = System.nanoTime();
System.out.println(finalTime - initTime);
}
//InsertionSortTimingForAllList method will contain a list
//depending on the the insertionSort method is called and the respective
//list run time is calculated
public static void InsertionSortTimingForAllList(int[] list)
{
long initTime = System.nanoTime();
insertionSort(list);
long finalTime = System.nanoTime();
System.out.println(finalTime - initTime);
}
//generateRandomNumbers method will generate the random numbers
//of the given range into the respective size of lists
public static int[] generateRandomNumbers(int length, int range)
{
int[] randNums=new int[length];
Random rand = new Random();
for (int i = 0; i < length; ++i)
{
randNums[i] = rand.nextInt(range);
}
return randNums;
}
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));
}
}
}
Sample Output:
1. List of 100 numbers drawn from 0--9.
2. List of 100 numbers drawn from 0--99.
3. List of 100 numbers drawn from 0--999.
4. List of 1000 numbers drawn from 0--99.
5. List of 1000 numbers drawn from 0--999.
6. List of 1000 numbers drawn from 0--9999.
7. List of 10000 numbers drawn from 0--999.
8. List of 10000 numbers drawn from 0--9999.
8. List of 10000 numbers drawn from 0--99999.
10. List of 100000 numbers drawn from 0--9999.
11. List of 100000 numbers drawn from 0--99999.
12. List of 100000 numbers drawn from 0--999999.
**************************************************
The run time in nana seconds by the Quick sort for the below list are:
The time taken for the list 1 is:
44856
The time taken for the list 2 is:
80003
The time taken for the list 3 is:
11382
The time taken for the list 4 is:
132557
The time taken for the list 5 is:
80003
The time taken for the list 6 is:
66613
The time taken for the list 7 is:
838527
The time taken for the list 8 is:
885726
The time taken for the list 9 is:
890747
The time taken for the list 10 is:
10725110
The time taken for the list 11 is:
10716072
The time taken for the list 12 is:
10867375
**************************************************
The run time by the Merge Sort for the below list are:
The time taken for the list 1 is:
65275
The time taken for the list 2 is:
52889
The time taken for the list 3 is:
63266
The time taken for the list 4 is:
790659
The time taken for the list 5 is:
671826
The time taken for the list 6 is:
103770
The time taken for the list 7 is:
1056778
The time taken for the list 8 is:
2989239
The time taken for the list 9 is:
943636
The time taken for the list 10 is:
12250525
The time taken for the list 11 is:
11411999
The time taken for the list 12 is:
10960098
**************************************************
The run time by the Selection Sort for the below list are:
The time taken for the list 1 is:
100422
The time taken for the list 2 is:
384283
The time taken for the list 3 is:
9038
The time taken for the list 4 is:
878696
The time taken for the list 5 is:
823798
The time taken for the list 6 is:
823799
The time taken for the list 7 is:
83932352
The time taken for the list 8 is:
82963946
The time taken for the list 9 is:
83576857
The time taken for the list 10 is:
8626737056
The time taken for the list 11 is:
8402425937
The time taken for the list 12 is:
8483621445
**************************************************
The run time by the Insertion Sort for the below list are:
The time taken for the list 1 is:
5690
The time taken for the list 2 is:
3682
The time taken for the list 3 is:
3682
The time taken for the list 4 is:
30461
The time taken for the list 5 is:
40169
The time taken for the list 6 is:
29792
The time taken for the list 7 is:
296915
The time taken for the list 8 is:
26110
The time taken for the list 9 is:
26445
The time taken for the list 10 is:
247039
The time taken for the list 11 is:
246704
The time taken for the list 12 is:
246370
**************************************************
The run time by the Bubble Sort for the below list are:
The time taken for the list 1 is:
4352
The time taken for the list 2 is:
3013
The time taken for the list 3 is:
3347
The time taken for the list 4 is:
24101
The time taken for the list 5 is:
23767
The time taken for the list 6 is:
28119
The time taken for the list 7 is:
228293
The time taken for the list 8 is:
22762
The time taken for the list 9 is:
23098
The time taken for the list 10 is:
207205
The time taken for the list 11 is:
206870
The time taken for the list 12 is:
202519
**************************************************
Note:
The added and modified code is highlighted in bold letters.
The sorting functions are called for the required sorting algorithms only.
If required you can add the other sorting algorithms also.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.