The Four Sorting Algorithms You Need To Know

When it comes to Computer Science, there are four main algorithms that you need to have in your arsenal. Bubble sort, selections sort, merge sort, and quickSort. Adding just these four algorithms to your collection of knowledge will certainly make you a better and more efficient programmer.

1. Bubble Sort:

Description: Start at the beginning of the list and swap the first two elements if the first is greater than the second. Then, go to the next pair, making continuous sweeps of the list and so on until the list is sorted.

Runtime: O(n²) average and worst case. Memory: O(1)

Python code:

2. Selection Sort:

Description: Find the smallest element using a linear scan and move it to the front (swapping it with the front element). Then, find the second smallest and move it tot he second position in the list, using once again a linear scan. Continue to do this until the list is sorted.

Runtime: O(n²) average and worst case, Memory: O(1)

Python code:

3. Merge Sort:

Description: Merge sort uses the divide and conquer method and is a recursive algorithm. Although it is more difficult to implement than other algorithms, it is very time efficient. It divides the list in half, sorts each of those halves, and then merges them back together. Each half has the same sorting algorithm applied to it. This splitting into halves continues until you are just merging two single element lists.

Runtime: O(n log(n)) average and worst case. Space complexity O(n).

Python code:

4. Quicksort:

Description: Pick a random element as a pivot point and partition the list around this element. All numbers that are less than the pivot element go to the left of the pivot point and all numbers that are greater than the pivot element go to the right of the pivot point. Recursively repeat the partitioning of the list and its sub-lists until the list is sorted. For this program, the initial leftIndex == 0 and the initial rightIndex == len(lst)-1.

Time complexity: O(n log(n)) average and O(n²) worst. Memory: O(log(n)).

Python code:

Conclusion: And there you have it, the four sorting algorithms that you need to know in order to become a better programmer!