Question

which sorting method works fastest:
1.randomized array
2.nearly sorted array
3.reversed
4.array with duplicates
*(assume that it is a large array with like 100,000 numbers)

Answer 1

nearly sorted

Answer 2

no, i think u misunderstood my question. basically i need to do it 4 diff ways and seee hich one is the best for diff methods

these are my answers:
ranomized:best is: mergesort
reverse:bubblesort
nearly sorted:bubblesort
duplicates: selectionsort

Answer 3

what u wanna know?

Answer 4

if my choices are correct/make sense/
like for a randomized array, it is sorted fastest using mergesort
reverse is fastest with bubble...

Answer 5

isnt reverse better with insertion sort?

Answer 6

oh, ya, but thats not one of my choices.. i have buble sort,mege, selection

Answer 7

use merge here because bubble sort will take more steps

Answer 8

Of your choices, merge sort is by far the best.
Quicksort is probably the other major alternative to have a look at.

A cool one for arrays with only a small range of possible numbers is counting sort:
http://en.wikipedia.org/wiki/Counting_sort

Answer 9

Merge sort and Randomised Quicksort have running times of O(n lg n).
Bubble sort and Selection sort is O(n^2)
Now O(n lg n) is faster than O( n^2), for a large enough n.

Hence, Merge sort and Quicksort beats Bubble and Selection sort.

Also, Counting sort has linear running time O(n). So, that's even better that O(n lg n), but it's complex and a little hard to understand.

Answer 10

http://www.sorting-algorithms.com/

Answer 11

the url above tells me

randomized -> merge sort
revese -> shell sort
nearly sorted->insertion sort
duplicates -> quick sort, but insertion works quite good as well.