Hey, I ran Bubble Sort, Merge Sort, and Quick Sort under the following inputs: L
ID: 3841205 • Letter: H
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.
Also if you can please explain why that stack overflow happens it would be much appreciated.
Explanation / Answer
For graphs, you have size of list and time for each algorithm. Using python or some tool as simple as excel,etc you need to draw plot for each algo between time and size of list.
Along with this, for each size of list, plot another graph between time and theoritical upper limits of the algorithms. For example upper bound of quick sort is O(n^2), etc.
Python has a awesome library matplotlib for such graphs.
As for the stack overflow, better answer would be by having a look at code. But I can make some guesses as, there might be while loop, which could be going into infinite loop because say variables changed are different from variable in while loop condition.
Or recursion in quicksort is not changing parameter before next call, etc These could be leading to infinte recursion and thus stack overflow.