[Algorithm] Sorting algorithm

Sorting Algorithms

• Given a set of records, the output is to the non-decreasing order(numerical order or lexicographical order) of records.
• The output is a permutation of the input.
• https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

• Sorting has been commonly used as the pre-processed method for searching and matching.
  • Sorting is also used as the basic solution for many other complex problem.
  • In most organization, more than 25% of computing time is spent on sorting.
• No best algorithm for any situation: initial ordering and size of list.
  • That why we need to know several techniques.
  • The analysis of lower bound is good for understanding basic skill for algorithm analysis.
• Comparison sort vs Non-comparison sort
  • Comparative sorting algorithm determines the order of two element through a comparison operator.
  • Comparison sorting algorithms:
    • Selection sort, Bubble sort, Insertion sort, Quick sort and so on.
  • Non-comparison sorting algorithms:
    • Radix sort, Bucket sort, Counting sort
  • Non-comparison sort is also called a linear sorting method.
• Internal sort vs External sort
  • Internal sorting technique is for the case where the list is small enough to sort entirely in main memory.
    • Minimizing the number of comparisons.
    • Heap sort
  • External sorting technique is used when the list is too big to fit into main memory (e.g., disk and SSD)
    • The alignment of the entire data is done in the auxiliary memory. 
    • Minimizing the number of I/O accesses.
    • Balanced sort, Cascade Sort, Polyphase Sort
• Stability of Sorting Algorithms
  • Stable sorting algorithms maintain the relative order of records with equal keys.
  • The initial order of records with eqaul keys does not changed.