8
$\begingroup$

Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is correct ? Please let me know if there is any error, I will correct it.

Insertion Sort:

  • Average Case / Worst Case : $\Theta(n^2)$ ; happens when input is already sorted in descending order
  • Best Case : $\Theta(n)$ ; when input is already sorted
  • No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(n)$ in best case
  • No. of swaps : $\Theta(n^2)$ in worst/average case & $0$ in Best case

Selection Sort:

  • Average Case / Worst Case / Best Case: $\Theta(n^2)$
  • No. of comparisons : $\Theta(n^2)$
  • No. of swaps : $\Theta(n)$ in worst/average case & $0$ in best case At most the algorithm requires N swaps, once you swap an element into place, you never touch it again.

Merge Sort :

  • Average Case / Worst Case / Best case : $\Theta(nlgn)$ ; doesn't matter at all whether the input is sorted or not
  • No. of comparisons : $\Theta(n+m)$ in worst case & $\Theta(n)$ in best case ; assuming we are merging two array of size n & m where $n<m$
  • No. of swaps : No swaps ! [but requires extra memory, not in-place sort]

Quick Sort:

  • Worst Case : $\Theta(n^2)$ ; happens input is already sorted
  • Best Case : $\Theta(nlogn)$ ; when pivot divides array in exactly half
  • No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(nlogn)$ in best case
  • No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Bubble Sort:

  • Worst Case : $\Theta(n^2)$
  • Best Case : $\Theta(n)$ ; on already sorted
  • No. of comparisons : $\Theta(n^2)$ in worst case & best case
  • No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Linear Search:

  • Worst Case : $\Theta(n)$ ; search key not present or last element
  • Best Case : $\Theta(1)$ ; first element
  • No. of comparisons : $\Theta(n)$ in worst case & $1$ in best case

Binary Search:

  • Worst case/Average case : $\Theta(logn)$
  • Best Case : $\Theta(1)$ ; when key is middle element
  • No. of comparisons : $\Theta(logn)$ in worst/average case & $1$ in best case

  1. I have considered only basic searching & sorting algorithms.
  2. It is assumed above that sorting algorithms produce output in ascending order
  3. Sources : The awesome CLRS and this Wiki
$\endgroup$
  • $\begingroup$ For discussing the merits of this (kind of) question, please join us in chat. $\endgroup$ – Raphael Apr 3 '13 at 14:12
  • 1
    $\begingroup$ This is not a question so is off-topic. $\endgroup$ – David Richerby Feb 8 '14 at 9:25
  • $\begingroup$ I voted to close too. This is perhaps challenging to salvage too because the "question" is rather broad (what are the basic search and sorting algorithms, exactly?) $\endgroup$ – Juho Feb 8 '14 at 9:32
-2
$\begingroup$

For general algorithm of bubble sort worst case comparisons are $\Theta(n^2)$ But for special case algorithm where in you add a flag to indicate that there has been a swap in previous pass. If there were no swaps then we come out of the loop since array is already sorted. In this case comparisons are $n$ not 0.

For Quick sort you have mentioned that worst case swaps are $n^2$. Well worst case scenario for quick sort is when all elements are in sorted order thus there won't be any swaps so it should be zero.

$\endgroup$
  • 1
    $\begingroup$ I don't understand your answer. Detecting "no swaps" in bubble sort certainly makes it faster but, if the input is in the opposite order to the output, you still need $\Theta(n^2)$ swaps, even with "no swap" detection. Quicksort normally runs in time $O(n\log n)$ so the best case cannot be $n^2$ swaps. $\endgroup$ – David Richerby Feb 8 '14 at 9:32
  • $\begingroup$ Thanks for Editing my comment, i am new to SE. Well i should have been more clear on this. i just edited my comment above. I was trying to say that best case comparisons cannot be 0 in case of Bubble sort it has to n. when array is sorted and you are using flag to indicate swap in previous pass. if there is no swap in previous pass then array is already sorted so no need to run further for first pass we are making n comparisons. For Quick sort i am talking about Comparisons and swaps not time complexity, in case of worse case all elements are sorted so no need to swaps are needed. $\endgroup$ – Nikhil Mahajan Feb 8 '14 at 10:30
  • $\begingroup$ In the normal case, quicksort runs in time $O(n\log n)$. Therefore, the best case is also $O(n\log n)$ time steps (it might be faster but $O(-)$ gives only an upper bound). In $O(n\log n)$ steps, you cannot do anything $n^2$ times -- comparisons, swaps, or anything else. You can't use more than $O(n\log n)$ memory, either. The best case for any complexity measure at all cannot be more than $O(n\log n)$. $\endgroup$ – David Richerby Feb 8 '14 at 14:46
  • $\begingroup$ You are correct i edited my answer for Quick sort. $\endgroup$ – Nikhil Mahajan Feb 9 '14 at 7:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.