Skip to content

Sorting

Jump to bottom
Avinash Kumar edited this page Nov 8, 2018 · 8 revisions

Comparison Based Sorting

  • Insertion Sort

    • In place i.e. no extra space needed
    • for(i from 1 to n) { Take A[i] and put it in the correct place in A[0] to A[i-1] }
    • O(n^2)
    • Stable sort

  • Selection Sort

    • In place
    • for(i=0; i<n; i++) { Find the minimum from A[i] to A[n-1] and swap it with A[i]. }
    • O(n^2)
    • Stable Sort

  • QuickSort

    • In place

    • Not stable sort

    • QuickSort(A, first, last)
      {
      if(first<last)
      {
      split_point = split(A, first, last); // A[last] reaches its correct place that is the split point in split() function
      QuickSort(A, first, split_point-1);
      QuickSort(A, split_point + 1, last);
      }
      }

    • Any pair of numbers in the array gets compared at most once during quick-sort. Hence, worst case becomes O(n^2). But in average case, it is O(nlogn).

    • To have average case runtimes, we should choose better pivots. eg: median of 3,5 etc. OR random element as pivot.

    • To have less procedure call overhead, we can use insertion sort etc. when the size of array becomes less than a threshold.

  • MergeSort

    • Not in place. Requires array
    • O(nLogn)
    • Stable Sort

  • HeapSort

    • O(nLogn)
    • A heap can be created from a random array in O(n) time
    • Not stable sort
    • But note that if you just want first k elements, then that can be gotten in (kLog n) time. In normal sorting case, it would take you nLogn because you have to sort the full array. In Heapsort, you just heapify the array (O(n)) and then next biggest element can be output in Logn time.

Best Case that can be achieved by Comparison based sorting

  • Any comparison based sorting method can be represented as a binary decision tree where each node is comparison between two indices. We go left if first index is lower than second and right otherwise. As for n elements, there can be n! permutations, one of which represents the actual sorted array, the number of leaves in this tree is n!. The depth of the tree is the minimum number of comparisons needed in worst case. The smallest depth of a tree with n! nodes is (log n!) which is theta(n log n). So, with comparison based sorting at least theta(n log n) comparisons must be made. Therefore, heapsort and mergesort are asymptotically optimal. However, it must be noted that these algorithms may make more comparisons than necessary. Eg: To sort 5 elements, MergeSort uses 8 comparisons, when only 7 will do.

Other Sorting Algorithms

  • Counting Sort -

    • Works when we are given the range of the numbers in the array.
    • Requires an extra space of the size of the range. So, it is worth only when k is smaller than n. Otherwise the space requirement can be too much.
    • Is stable sort when iterating on the array from right to left
    • O(n+k)

  • Bucket Sort -

    • Again a range is required
    • You divide the range into buckets and put elements inside the buckets. Sort elements within a bucket and then just combine the buckets. This is done when the range is quite big and the elements are expected to be dispersed almost uniformally. This is not a good idea if the distribution of elements is skewed as we may get O(n^2) complexity.
    • O(n + summation(s(i)^2)) where s(i) is the number of elements in the ith bucket.

  • Radix Sort

    • Useful in sorting data having various fields like date. It can also be used to sort numbers.
    • We start sorting from the least significant field and then move on to more significant fields.
    • The sorting algorithm used should be stable. Suppose we are sorting 101, 420 and 462. After, ones and tens digits, the order is 101, 420 and 464. Now, when we reach the hundredth digit, if we don't use stable sort, the order can become 101, 464 and 420.
    • Example, if we use radix sort for numbers, we can use counting sort on each place of digit i.e O(10 + n) and if there are d digits, the total complexity is O(d*(10+n)).

  • External Sort

    • Used when there isn't enough space in memory.
    • Replacement Selection is an optimization that can be implemented on external sort.

Questions:

1. Counting the number of inversions in a list of numbers OR Find the number of intersections of line.
Ans. Do mergeSort and during the process, record all instances where the numbers in the right array is smaller than the number in the left array. In principle, we can use any sorting algorithm to count inversions. Mergesort works particularly nicely.

Clone this wiki locally