ANONYMOUS wrote:
> Hi,
>
> How do you want us to prove the different sorts: Insertion,Merge and Quick. Do we
need
> to prove them mathematically?
I am not aware of anywhere in the unit content where you are asked to prove all these,
but it is good to be interested.
Note that while analysing the worst case complexity is easy enough for all three
algorithms, the expected complexity of quicksort is very challenging to prove and I
believe is beyond the scope of this unit.
As an example, the below is a way of deriving the worst case complexity of insertion
sort:
The worst case for insertion sort is a backwards list.
In this case, we will take each element, and have to shuffle every element before it
over one by one.
As such, to put the element at index i into its appropriate spot, we will have to move
i elements.
Moving each element is O(1), so moving them all takes O(i).
We have to do this for all 0 <= i < N, so we get 0 + 1 + 2 + ... + (N  1).
There are a number of different proofs that 0 + 1 + 2 + ... + (N  1) = N * (N  1) /
2.
This expands to (1/2) (N^2  N).
We can ignore the constant factor, and the N term will be dominated by N^2, so we find
that this is O(N^2), as expected.
Some hints/notes for further proofs:
Insertion sort expected case: Similar to above, but we expect to only have to move some
of the elements each time. On average, how many do we expect to move? Does this change
the complexity by more than a constant factor?
Merge sort: Are the expected and worst cases for merge sort going to be different?
Merge sort is a recursive algorithm so consider analysing it by defining a recursive
time function T(N) for how long it takes to sort N elements?
Quick sort: The worst case for quick sort is similar to that of insertion sort. If our
pivot is either the minimum or maximum element in the array, then we will only end up
removing the pivot from our array each time, which only sorts one element at a time,
like insertion sort.
The results you should be looking for:
Algorithm Worst Case Expected Case
Insertion O(N^2) O(N^2)
Merge O(N log N) O(N log N)
Quick O(N^2) O(N log N)
