Best/Worst case for sorting algorithms

[gronkite]

I have a homework task where I need to determine which sorting algorithms are implemented in a .jar file provided by my teacher. Obviously I need to design my own tests to do this, so I was doing a bit of research on best/worst case scenarios but what I found was a bit unclear. EDIT: We are supposed to determine the time complexity of each function call.

Basically my question is, is there a standard best/worst case for sorting algorithms? We are using vectors as the item that needs to be sorted, so I was thinking a vector where all elements are the same would be the worst case scenario, and that a vector filled with randomly generated numbers would be the average scenario, and the best case scenario would be on an already sorted vector, but I would appreciate any input from more experienced coders.

And if you think there is anything else I need to consider, by all means tell me :)

[stultuske]

worst case ... if the Vector contains object instances of different types.

[gronkite]

We're only testing integer vectors

[JamesCherrill]

I would try all the same, already sorted, and already sorted but in the opposite order (which will be the worst case for some algorithms)

[WDrago]

I found the information and animations on this site quite useful: sorting-algorithms.com

Of course, you should have a pretty good understanding of how each algorithm works before trying to figure out which one is which in your .jar file.

Good luck,
-Bill

[somjit{}]

is there a standard best/worst case for sorting algorithms?

there are hundreds of sorting algorithms out there... some of them have different variations of themselves as well. they all have their own standard best/worst case complexity.

example : considering two classic algorithms : quicksort and mergesort, quicksort has time complexity higher than mergesort (both in the region of NlogN ), but generally a standard quicksort algorithm works faster than mergesort .. why? because mergesort requires more space in the form of an auxillary array in its algorithm, so for huge data structures , moving values from one array to another eats up the time complexity advantage it had over quicksort.

notice i say generally , because the original quicksort can go and run in quadratic time in presence of duplicate keys, but this error was eventually solved by implementing random shuffle at the begining , and then using a 3 way partioning method to keep the duplicates grouped in order.

so I was thinking a vector where all elements are the same would be the worst case scenario, and that a vector filled with randomly generated numbers would be the average scenario, and the best case scenario would be on an already sorted vector,

mergesort is an optimal sorting algorithm , meaning that its upper and lower bounds are both in the region of NlogN.. so it doesnt matter how the data is arranged to mergesort , it will take more or less equal time anyways.

also , if the data is partially sorted , insertion sort will give a running time proportional to N ( ie linear ) instead of NLogN from mergesort

[gronkite]

I have one final question, is it possible for merge sort to give a stack overflow error? I ran two tests with vectors of length 100000. The algorithm I tested was the second fasest overall and usually as fast as the absolute fastest which I identified to be quicksort.

Anyway, the two tests I ran were for an already sorted vector and a vector sorted in reverse order, both times I received a stack overflow error. So I am guessing that this is merge sort. Please correct me if I am wrong.

EDIT: sorry, one final question. How does bubble sort perform on an already sorted list? I know that this is the best case for insertion sort, but is it the same for bubble sort?

[JamesCherrill]

You normally get a stack overflow when a method or methods are called in a non-terminating recursion. It's unlikely that an ordinary correct program will nest calls so deep that you run out of memory, but if you're sure the code is OK you can allocate more memory for the VM.

I belive a bubble sort on an already sorted list will terminate after exactly one pass, which must be the best case.

[somjit{}]

I belive a bubble sort on an already sorted list will terminate after exactly one pass, which must be the best case.

insertion sort too :) in fact , for a partially sorted array , insertion sort runs in linear time. which is the best case for any compare based sorting model.