Table of Contents

Description

• Sorting algorithms are used to take an array or list of elements (numbers or letters), and sort them into a desired order, usually from lowest to highest.
• There are two basic sorting algorithms. These are slow and rarely used.

  • Selection Sort: Go through the array, “select” the smallest number, then swap it to the next unsorted spot in the array and repeat.

      ![SelectionSort.gif](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/91a35782-53a6-4698-9665-ea3cac498643/SelectionSort.gif>)
    

  • Bubble Sort: Go through the array, compare each pair of elements, and swap the smaller one before the larger one (if necessary). Go through the array again until there are no more swaps made.

      ![BubbleSort.gif](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/2f86d596-4c7d-4541-838c-7d0183a57703/BubbleSort.gif>)
    

    • The smaller elements will “bubble up” to the start of the array.
• There are three commonly used efficient sorting algorithms:
  • Quick Sort: fastest
  • Merge Sort: most consistent
  • Radix Sort: special sort for integers

Quick Sort

• Quick sort is the main sorting algorithm people use.

• Quick sort’s strength is that its average case is very fast.

• It works by assigning a pivot point, then partitioning the array, so that all numbers below the pivot are on the left side, and all numbers above it are on the right side. Then you repeat the process on the left and right sides of the partition, until the entire thing is sorted.

• Properties

  • Quick sort is an unstable sort. If two elements are equal, they won’t always appear in their original order in the sorted array.

• General process

    ![QuickSort.gif](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/478ae3d5-3254-416c-bff4-6236f46c1746/QuickSort.gif>)
  

  1. Choose a partition (or part of the array) to work on.
     • Start with the entire array.
  2. Select the midpoint of the partition. This is your pivot.
  3. Traverse the array from the left, until you find a number greater than the pivot, i.e. a number that should be on the right of the pivot.
  4. Traverse the array from the right, until you find a number less than the pivot.
  5. Swap the two numbers.
  6. Keep traversing and swapping, until the pointers cross each other.
  7. Return the location of one of the pointers. This is your partition point.
     • Everything left of it will be smaller. Everything right will be greater.
  8. Recursively repeat the entire process with the left and right halfs of each partition.
     • Stop when the partitions are size 1.
  9. The array is now fully sorted.

• Implementation: Quicksort is implemented as a recursive divide-and-conquer algorithm.

    ![QuickSortCode.jpg](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/6f0435b9-04a5-4123-8c67-a58bc4342f59/QuickSortCode.jpg>)
  

  • Take in an array (line 2)
  • Select the midpoint as your pivot (12).
  • Traverse the array from the left, until you find an element greater than the pivot (15).
  • Traverse from the right, until you find an element less than the pivot (18).
  • Swap the elements and increment both pointers (20-24).
  • Repeat until the pointers cross !(left <= right)
    • When they cross, don’t swap and end the partitioning loop.
    • Then, return the location of the pointer going from left to right. This is the partition point.
  • Recursively repeat the partitioning on the left side of the array (from the first element to the partition point), until the partition is 1 element long (3-5)
  • Recursively repeat on the right side of the array (6-8).
  • The array is now sorted.

• Usage

  • In most cases, quick sort should be your go-to sorting algorithm.

Merge Sort

• Merge sort sorts an array by first splitting it into pieces, then sorting the pieces while remerging them.

• Merge sort’s strength is that its worst case is consistently fast.

• General process

    ![MergeSort.gif](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/29809182-0db1-4772-a49b-b2a42f63cb7c/MergeSort.gif>)
  

  1. Recursively split the array in half, until you get single-element subarrays
  2. Take two subarrays and merge them:
     1. Compare the first number in each. Find the lowest of the two.
     2. Copy the lowest of the two into the first slot of the merged array.
     3. Move to the next element in the subarray you just copied from. Repeat the comparisons until one subarray has been fully copied.
     4. Copy the rest of the other subarray. .
  3. Go to the next two subarrays and repeat, until the entire array has been reassembled.

• Implementation

  • Merge sort is implemented recursively.

  • Part 1: Split the array into pieces.

      ![MergeSort1.jpg](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d68c5eeb-3d40-4a5c-a257-790416c90193/MergeSort1.jpg>)
      
      - Take an array, `A`
      - Get the size of the array, `n`
      - **End the recursion if the array only has 1 element**. Otherwise:
          - Find the **midpoint**, `n/2`
          - **Create two new empty arrays**, `left` and `right`, to hold the left and right halves of A.
          - Loop through `A` and **copy each element** to the `left` or `right` arrays.
      - **Recursively recall the function** on the left and right halves of the array. This will repeatedly split up the array until you get pieces of 1.
      - Once you get pieces of 1, start **merging them back together.**
    

    • Part 2: Re-merge and sort the pieces.

        ![MergeSort2.jpg](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/996f1ba7-6b4e-4b9d-b563-c6cfe6cf9ea8/MergeSort2.jpg>)
      

      • Take two of the recursively split pieces , left and right, and the original full-sized array, A.
      • Loop through the left and right subarrays, until one of them is fully traversed.
        • Compare the current element (starting at 0) in both arrays.
        • Copy the smaller number to the current position on the original array.
        • Move to the next spot in the original array and the subarray you copied from.
        • Stop when one subarray is fully traversed.
      • Loop through the other subarray (that wasn’t fully traversed). Copy each element to the original array.

    • When the pieces have been fully re-merged, they will also be fully sorted.

• Usage

  • Use merge sort if you need a stable sort, i.e. if two elements are equal, they’ll appear in their original order.
  • Use merge sort if you need the rare worst-case scenario to also be sorted quickly.