Question

Hey, I ran Bubble Sort, Merge Sort, and Quick 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.

These were my results:

BubbleSort:

[1000]

0-9: 9 ms

0-99: 9 ms

0-999: 9 ms

0-9999: 9 ms

0-99999: 9 ms

0-999999: 9 ms

[10000]

0-9: 156 ms

0-99: 167 ms

0-999: 171 ms

0-9999: 171 ms

0-99999: 173 ms

0-999999: 171 ms

[100000]

0-9: 15967 ms

0-99: 17079 ms

0-999: 17172 ms

0-9999: 17173 ms

0-99999: 17220 ms

0-999999: 17175 ms

[1000000]

0-9: 1664472 ms

0-99: 1740240 ms

0-999: 1759920 ms

0-9999: 1758476 ms

0-99999: 1770420 ms

0-999999: 1761082 ms

MergeSort:

[1000]

0-9: 1 ms

0-99: 1 ms

0-999: 1 ms

0-9999: 1 ms

0-99999: 1 ms

0-999999: 1 ms

[10000]

0-9: 3 ms

0-99: 3 ms

0-999: 3 ms

0-9999: 3 ms

0-99999: 3 ms

0-999999: 3 ms

[100000]

0-9: 17 ms

0-99: 19 ms

0-999: 19 ms

0-9999: 20 ms

0-99999: 21 ms

0-999999: 21 ms

[1000000]

0-9: 128 ms

0-99: 140 ms

0-999: 150 ms

0-9999: 157 ms

0-99999: 167 ms

0-999999: 167 ms

QuickSort:

[1000]

0-9: 1 ms

0-99: 1 ms

0-999: 1 ms

0-9999: 1 ms

0-99999: 1 ms

0-999999: 1 ms

[10000]

0-9: 11 ms

0-99: 5 ms

0-999: 3 ms

0-9999: 3 ms

0-99999: 2 ms

0-999999: 2 ms

[100000]

0-9: 372 ms

0-99: 49 ms

0-999: 17 ms

0-9999: 13 ms

0-99999: 13 ms

0-999999: 13 ms

[1000000]

0-9: Here I get a Stack Overflow, can you please explain why this happens?

0-99: 4190 ms

0-999: 450 ms

0-9999: 118 ms

0-99999: 95 ms

0-999999: 95 ms

My question is, how would I make graphs using this data for:

-Time against size of the list, for each value upper-bound.

-Time against value upper-bound, for each list size.

How many graphs would this total out to?

Also if you can please explain why that stack overflow happens it would be much appreciated.

Here is the source code for QuickSort:

   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;
   }

Answer 1

To make graph for "Time against size of the list, for each value upper-bound", you first figure out all the upper bounds, in this case its 0-9, 0-99, 0-999, 0-9999, 0-99999 and 0-999999, that is 6 upper bounds:

For each of these upper bounds you will have 1 graph, to plot each of this graph you will pick up each of the upper bound and start plotting graph with time in y-axis and list size in x- axis

Example, for all 0-9 results for bubble sort, you have this data:

DATA SIZE	TIME TAKEN(ms)
1000	9
10000	156
100000	15967
1000000	1664472

Using this you can lot a graph for data size(x-axis) against time(y-axis)

You will repeat this for all 6 upper bouds. ANd for all 3 sorting algorithms.

You willl thus have 6*3 = 18 such graphs.

To make graphs for "Time against value upper-bound, for each list size", you first figure out different list sizes, which is 4(1000,10000,100000,1000000) in your case.

For each of thse data sizes you can plot a graph for upper bound in x-axis against time in y-axis.

Example for data size 1000 and bubble sord you have this data:

Upper Bound	Time Taken(ms)
0-9	9
0-99	9
0-999	9
0-9999	9
0-99999	9
0-999999	9

Using this you can lot a graph for upper bound(x-axis) against time(y-axis)

You will repeat this for all 4 upper bouds. And for all 3 sorting algorithms.

You willl thus have 4*3 = 12 such graphs.

You will have a total of 18 + 12 = 30 such graphs.

---------------------------------------------------------------------------------------------------------------------------------

Now for you question on stack overflow. You have a stack overflow when there are too many one function calls for the processor, more function calls than what the memory can handle.

In your case you have a stack overflow, because the data size here is 1000000 and the spread of elements is not so great, you only have to choose from 0 to 9. Basically even if you have a uniform spread every element will appear 100000 times, which means at some point a sub-array of length 100000 will partition at the first element and you will end up having 100000 open quickSortHelper function calls, which is probably too much for you processor to handle. And hence the stack overflow.