Sorting

Sorting

Insertion Sort

• Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time
• Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain

Merge Sort

• Merge sort is a divide and conquer algorithm
• Conceptually, a merge sort works as follows:
  • Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted)
  • Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list

Quick Sort

• Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined
• On average, the algorithm takes O(n log n) comparisons to sort n items
  • In the worst case, it makes O(n2) comparisons, though this behavior is rare
• Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. The steps are:
  • Pick an element, called a pivot, from the array
  • Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  • Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub- array of elements with greater values

Videos

• Insertion Sort in 2 Minutes
• Merge Sort in 3 Minutes
• Quick Sort in 4 Minutes