(Simple questions about sorting algorithms) Hey, I\'m working on a project where
ID: 3840328 • Letter: #
Question
(Simple questions about sorting algorithms)
Hey, I'm working on a project where I have to run Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Counting Sort, and Radix Sort under the following inputs:
List of 1000 numbers drawn from 0--9.
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 1000 numbers drawn from 0--99999.
List of 1000 numbers drawn from 0--999999.
List of 10000 numbers drawn from 0--9.
List of 10000 numbers drawn from 0--99.
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 10000 numbers drawn from 0--999999.
List of 100000 numbers drawn from 0--9.
List of 100000 numbers drawn from 0--99.
List of 100000 numbers drawn from 0--999.
List of 100000 numbers drawn from 0--9999.
List of 100000 numbers drawn from 0--99999.
List of 100000 numbers drawn from 0--999999.
List of 1000000 numbers drawn from 0--9.
List of 1000000 numbers drawn from 0--99.
List of 1000000 numbers drawn from 0--999.
List of 1000000 numbers drawn from 0--9999.
List of 1000000 numbers drawn from 0--99999.
List of 1000000 numbers drawn from 0--999999.
I have already completed collecting the data for the first 5 algorithms using this method:
(example for first input of BubbleSort)
public static void main(String[] args) {
int[] list = new int[1000];
Random rand = new Random();
for (int i = 0; i < list.length; ++i) {
list[i] = rand.nextInt(10);
}
long initTime = System.currentTimeMillis();
bubbleSort(list);
long finalTime = System.currentTimeMillis();
System.out.println(finalTime - initTime);
}
I believe this method works fine for the first 5 algorithms. However, I run into confusion using this version of CountingSort:
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;
}
And using this version of RadixSort:
public static int[] radixSort(int[] numbers, int radix) {
int[] result = numbers;
for (int pos = 1; pos <= radix; ++pos) {
result = modCountingSort(result, pos);
}
return result;
}
My question is, when I'm collecting the data for counting sort, should I test every condition keeping:
int[] counter = new int[1000000]
Or should I change the value to reflect the size of the list I'm testing?
Also when collecting data for RadixSort, what is the proper int value to feed the method? (as it takes (list, int value)) Is it the size of the list that belongs there?
Lastly can you provide a few example graphs for
-Time against size of the list, for each value upper-bound.
-Time against value upper-bound, for each list size.
I'm not asking you to complete every graph I need, just provide examples which I can use to complete it myself. Thank you!
Explanation / Answer
Instead of checking condition with a static value int[1000000], it is always better to pass the size of the list you are going to test.
For this, you directly pass the size of the list or you can also declare a variable and initialize it with the size of the list and you can pass it.
In Radix sort, we need to pass the array length value in the place of int value according to your syntax. That means we need to find the length/size of the array you are going to pass and store that in a variable and pass as a parameter to Radix sort.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.