MORE SORTING

This week was all about sorting algorithms. Specifically quick sort and the variations there in. I've been working in web development for a while so I've seen this video (https://www.youtube.com/watch?v=kPRA0W1kECg&t=68s) and have always kind of known that quick sort was the defacto sorting algorithm for speed and memory efficiency.

After this week I can actually explain why (lol)

Key points

1. Memory Efficiency

The quick sort algorithm is memory efficient because it is able to sort itself in place. Basically just swapping the positions of the numbers in array as needed. Relative to merge sort which requires additional memory overhead to perform the merge operation.

2. Time Efficiency

While the worst case is still O(n^2) (like bubble sort), the average efficiency ends up being O (n log n) which is significantly faster than other sorting algorithms especially linear ones like insertion sort and bubble sort.

HoWEVerrrrrr

The caveat is that even the best case scenario, quick sort is still O (n log n) which is slightly slower than O(n) like bubble/insertion sort. Why? Well it's because quick sort will still divide and conquer and wont know that the array is already sorted until it's finished the partitioning process. While insertion sort will just do a quick check n times to validate that an array is already sorted.


Anyways, interesting stuff. Glad I finally understand quick sort!