Top 5 most basic sorting algorithms in Data Science with Python Code

Different Sorting Algorithms with Time Complexities

Sorting is an expertise that every software engineer and developer need. Not only for coding interviews but also a broad grasp of programming. The various sorting algorithms are an excellent example of how algorithm design may have a significant impact on programme complexity, performance, and efficiency.

SELECTION SORT

Selection sort is an easy and most basic sorting technique one can imagine. With Selection sort, we divide our input list/array into two parts: a sub-list of things that have already been sorted and a sub-list of objects that need to be sorted. The smallest entry in the unsorted sub-list is found first and placed at the end of the sorted sub-list. As a result, we are always taking the smallest unsorted element and sorting it in the sorted sub-list. This step is repeated until the list is completely sorted. It is not a stable algorithm.

An example of Selection Sort

BUBBLE SORT

Bubble sort is typically taught in basic computer science lectures because it clearly shows how sorting works while remaining simple and straightforward. Bubble sort iterates the list and compares the neighboring element pairs. If they are in the wrong sequence, elements are swapped. The process is repeated until the list is sorted. Since Bubble sort travels over the unsorted section of the list repeatedly, it has a worst-case complexity of O(n²). It is a stable algorithm.

An example of Bubble Sort

INSERTION SORT

Bubble sort and selection sort are both faster, but insertion sort is arguably simpler. It is also how many people sort their cards when they are playing a card game! Insertion sort removes one element from the array with each loop iteration. It then locates the element’s proper location within another sorted array and inserts it there. This process is repeated until no input elements are left. It is a stable algorithm.

An example of Insertion Sort

MERGE SORT

Merge sort is an example of a Divide and Conquer algorithm that is both simple and elegant. It merely employs the two primary steps:

1. Divide the unsorted list into N sublists, with each sublist having 1 unsorted element and N being the number of elements in the original array.
2. Merge, or conquer, two sub-lists at a time to create new sorted sublists until all elements have been fully merged into a single sorted array.

It is a stable algorithm.

An example of Merge Sort

This code is of in-place Merge Sort, which means sorting is done in the provided list. No new memory is used for sorting.

QUICKSORT

Quicksort, like merge sort, is also a divide and conquer algorithm. Although it is a little more complicated, it is significantly faster than merge sort in most standard implementations and rarely reaches its worst-case complexity of O(n2). It consists of three main steps:

1. From the array, we first choose an element, which will be called the pivot.
2. Shift all elements smaller than the pivot to the left, and rest to the right. It is known as partition operation.
3. Repeat the previous two steps for each of the sub-arrays of elements with smaller and larger values than the last pivot.

It is not a stable algorithm.

An example of Quick Sort

This code is of in-place Quick Sort, which means sorting is done in the provided list. No new memory is used for sorting.

All the above codes above are in this GitHub repository. Check out my GitHub and Linkedin profile.