Understanding The Top 10 Classic Sorting Algorithms In Python (With Animated Demos)

Source:Big Data DT

This article is approximately 5200 words, and it is recommended to read in 10minutes

Sorting algorithms are one of the most fundamental algorithms in “Data Structures and Algorithms”.This article introduces 10 common internal sorting algorithms and how to implement them in Python.

Sorting algorithms can be divided into internal sorting and external sorting. Internal sorting sorts data records in memory, while external sorting is used when the data is too large to fit into memory at once, requiring access to external storage during sorting.Common internal sorting algorithms include: Insertion Sort, Shell Sort, Selection Sort, Bubble Sort, Merge Sort, Quick Sort, Heap Sort, Counting Sort, etc.A summary diagram:About Time Complexity:

• Quadratic (O(n²)) sorting: Various simple sorts such as direct insertion, direct selection, and bubble sort;
• Linear logarithmic (O(nlog2n)) sorting: Quick sort, heap sort, and merge sort;
• Shell Sort: O(n^(1+§)) sorting, where § is a constant between 0 and 1;
• Linear (O(n)) sorting: Counting sort, as well as bucket and bin sort.

About Stability:

• The order of two equal keys after sorting remains the same as before sorting.

• Stable sorting algorithms: Bubble sort, insertion sort, merge sort, and counting sort.

• Unstable sorting algorithms: Selection sort, quick sort, shell sort, heap sort.

Terminology:

• n: Data size.

• k: The number of “buckets”.

• In-place: Uses constant memory, does not require extra memory.

• Out-place: Requires extra memory.

01 Bubble SortBubble Sort is also a simple and intuitive sorting algorithm. It repeatedly visits the sequence to be sorted, comparing two elements at a time, and if they are in the wrong order, it swaps them. This process is repeated until no more swaps are needed, meaning the sequence is sorted. The name of this algorithm comes from the fact that smaller elements “bubble” up to the top of the sequence through swapping.As one of the simplest sorting algorithms, bubble sort feels like the word “Abandon” appearing at the first position in a word list, always familiar. Bubble sort also has an optimization where a flag is set; if no elements were swapped during a pass through the sequence, it proves that the sequence is already sorted. However, this improvement does not significantly enhance performance.

1. Algorithm Steps

1. Compare adjacent elements. If the first is larger than the second, swap them.
2. Do the same for each pair of adjacent elements from the first pair to the last pair. After this step, the last element will be the largest.
3. Repeat the above steps for all elements except the last one.
4. Continue repeating the above steps for fewer and fewer elements until no pairs need to be compared.

2. Animated Demo3. Python Code

def bubbleSort(arr):    for i in range(1, len(arr)):        for j in range(0, len(arr)-i):            if arr[j] > arr[j+1]:                arr[j], arr[j + 1] = arr[j + 1], arr[j]    return arr

02 Selection SortSelection Sort is a simple and intuitive sorting algorithm, with a time complexity of O(n²) regardless of the input data. Therefore, it is best used when the data size is small. The only advantage may be that it does not require extra memory space.

1. Algorithm Steps

1. First, find the minimum (or maximum) element in the unsorted sequence and place it at the starting position of the sorted sequence.
2. Then continue to find the minimum (or maximum) element from the remaining unsorted elements and place it at the end of the sorted sequence.
3. Repeat the second step until all elements are sorted.

2. Animated Demo3. Python Code

def selectionSort(arr):    for i in range(len(arr) - 1):        # Record the index of the minimum number        minIndex = i        for j in range(i + 1, len(arr)):            if arr[j] < arr[minIndex]:                minIndex = j        # If i is not the minimum, swap i with the minimum        if i != minIndex:            arr[i], arr[minIndex] = arr[minIndex], arr[i]    return arr

03 Insertion SortAlthough the code implementation of Insertion Sort is not as simple and brute-force as Bubble Sort and Selection Sort, its principle is arguably the easiest to understand, as anyone who has played cards should be able to grasp it instantly. Insertion Sort is a simple and intuitive sorting algorithm that works by building an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence to find the appropriate position and insert it.Like Bubble Sort, Insertion Sort also has an optimization algorithm called Binary Insertion.

1. Algorithm Steps

1. Consider the first element of the sequence to be sorted as an ordered sequence, and treat the rest as the unsorted sequence.
2. Scan the unsorted sequence from the beginning to the end, inserting each scanned element into the appropriate position in the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, it is inserted after the equal element.)

2. Animated Demo3. Python Code

def insertionSort(arr):    for i in range(len(arr)):        preIndex = i-1        current = arr[i]        while preIndex >= 0 and arr[preIndex] > current:            arr[preIndex+1] = arr[preIndex]            preIndex-=1        arr[preIndex+1] = current    return arr

04 Shell SortShell Sort, also known as the diminishing increment sort algorithm, is a more efficient improved version of Insertion Sort. However, Shell Sort is an unstable sorting algorithm.Shell Sort improves upon Insertion Sort based on the following two properties:

• Insertion Sort is efficient for data that is almost sorted, achieving linear sorting efficiency;
• However, Insertion Sort is generally inefficient because it can only move data one position at a time.

The basic idea of Shell Sort is: first, divide the entire sequence of records to be sorted into several subsequences, each of which is sorted by direct insertion. When the records in the entire sequence are “basically ordered”, direct insertion sorting is applied to all records sequentially.

1. Algorithm Steps

1. Select an increment sequence t1, t2, …, tk, where ti > tj, tk = 1;
2. Sort the sequence k times according to the number of increment sequences k;
3. In each sorting pass, based on the corresponding increment ti, divide the sequence to be sorted into several sub-sequences of length m, and perform direct insertion sort on each sub-table. When the increment factor is 1, the entire sequence is treated as one table, and the length of the table is the length of the entire sequence.

2. Python Code

def shellSort(arr):    import math    gap=1    while(gap < len(arr)/3):        gap = gap*3+1    while gap > 0:        for i in range(gap,len(arr)):            temp = arr[i]            j = i-gap            while j >=0 and arr[j] > temp:                arr[j+gap]=arr[j]                j-=gap            arr[j+gap] = temp        gap = math.floor(gap/3)    return arr

05 Merge SortMerge Sort is an efficient sorting algorithm based on the merge operation. This algorithm is a very typical application of the divide and conquer method.As a typical application of the divide and conquer idea, Merge Sort can be implemented in two ways:

• Top-down recursion (all recursive methods can be rewritten using iteration, leading to the second method);
• Bottom-up iteration.

Like Selection Sort, Merge Sort’s performance is not affected by the input data, but it performs much better than Selection Sort because it always has a time complexity of O(nlogn). The trade-off is that it requires extra memory space.

1. Algorithm Steps

1. Allocate space equal to the sum of the sizes of the two already sorted sequences, which will be used to store the merged sequence;
2. Set two pointers, initially positioned at the starting positions of the two already sorted sequences;
3. Compare the elements pointed to by the two pointers, choose the smaller element to place into the merge space, and move the pointer to the next position;
4. Repeat step 3 until one pointer reaches the end of the sequence;
5. Copy all remaining elements from the other sequence directly to the end of the merged sequence.

2. Animated Demo3. Python Code

def mergeSort(arr):    import math    if(len(arr)<2):        return arr    middle = math.floor(len(arr)/2)    left, right = arr[0:middle], arr[middle:]    return merge(mergeSort(left), mergeSort(right))
def merge(left,right):    result = []    while left and right:        if left[0] <= right[0]:            result.append(left.pop(0));        else:            result.append(right.pop(0));    while left:        result.append(left.pop(0));    while right:        result.append(right.pop(0));    return result

06 Quick SortQuick Sort is a sorting algorithm developed by Tony Hoare. On average, sorting n items takes O(nlogn) comparisons. In the worst case, it requires O(n²) comparisons, but this situation is rare. In fact, Quick Sort is usually significantly faster than other O(nlogn) algorithms because its inner loop can be efficiently implemented on most architectures.Quick Sort uses the divide and conquer strategy to split a list into two sub-lists.Quick Sort is a classic application of the divide and conquer idea in sorting algorithms. Essentially, Quick Sort can be seen as a recursive divide and conquer method based on Bubble Sort.The name Quick Sort is straightforward because it immediately conveys its purpose: to be fast and efficient! It is one of the fastest sorting algorithms for handling large datasets.Although the worst-case time complexity reaches O(n²), it still excels in most cases compared to sorting algorithms with an average time complexity of O(n logn). The reason for this remains unclear. Fortunately, my OCD kicked in, and after researching extensively, I finally found a satisfying answer in “Algorithm Art and Competitive Programming”:

The worst-case runtime of Quick Sort is O(n²), such as when sorting an already sorted array. However, its amortized expected time is O(nlogn), and the constant factor implied in the O(nlogn) notation is much smaller than that of Merge Sort, which is always O(nlogn). Therefore, for the vast majority of weakly ordered random sequences, Quick Sort is always superior to Merge Sort.

1. Algorithm Steps

1. Pick an element from the list, called the “pivot”;
2. Rearrange the list so that all elements less than the pivot are placed before it, and all elements greater than the pivot are placed after it (equal elements can go either side). After this partitioning, the pivot is in its final position. This is called the partition operation;
3. Recursively sort the sub-lists of elements less than and greater than the pivot.

The base case for recursion is when the size of the list is zero or one, meaning it is already sorted. Although the algorithm continues to recurse, it will eventually terminate because in each iteration, it will place at least one element in its final position.2. Animated Demo3. Python Code

def quickSort(arr, left=None, right=None):    left = 0 if not isinstance(left,(int, float)) else left    right = len(arr)-1 if not isinstance(right,(int, float)) else right    if left < right:        partitionIndex = partition(arr, left, right)        quickSort(arr, left, partitionIndex-1)        quickSort(arr, partitionIndex+1, right)    return arr

def partition(arr, left, right):    pivot = left    index = pivot+1    i = index    while  i <= right:        if arr[i] < arr[pivot]:            swap(arr, i, index)            index+=1        i+=1    swap(arr,pivot,index-1)    return index-1
def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]

07 Heap SortHeap Sort is a sorting algorithm that uses the heap data structure. A heap is a nearly complete binary tree structure that satisfies the heap property: the key value or index of child nodes is always less than (or greater than) its parent node. Heap Sort can be seen as a selection sort that utilizes the concept of a heap. It is divided into two methods:

• Max Heap: Each node’s value is greater than or equal to its children’s values, used for ascending order in heap sort;
• Min Heap: Each node’s value is less than or equal to its children’s values, used for descending order in heap sort.

The average time complexity of Heap Sort is O(nlogn).

1. Algorithm Steps

1. Create a heap H[0……n-1];
2. Swap the root of the heap (maximum value) with the tail of the heap;
3. Reduce the size of the heap by 1 and call shift_down(0) to adjust the new top data of the array to the appropriate position;
4. Repeat step 2 until the size of the heap is 1.

2. Animated Demo3. Python Code

def buildMaxHeap(arr):    import math    for i in range(math.floor(len(arr)/2),-1,-1):        heapify(arr,i)
def heapify(arr, i):    left = 2*i+1    right = 2*i+2    largest = i    if left < arrLen and arr[left] > arr[largest]:        largest = left    if right < arrLen and arr[right] > arr[largest]:        largest = right    if largest != i:        swap(arr, i, largest)        heapify(arr, largest)

def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):    global arrLen    arrLen = len(arr)    buildMaxHeap(arr)    for i in range(len(arr)-1,0,-1):        swap(arr,0,i)        arrLen -=1        heapify(arr, 0)    return arr

08 Counting SortCounting Sort’s core idea is to transform the input data values into keys stored in extra allocated array space. As a linear time complexity sorting algorithm, Counting Sort requires that the input data must be integers with a defined range.1. Animated Demo2. Python Code

def countingSort(arr, maxValue):    bucketLen = maxValue+1    bucket = [0]*bucketLen    sortedIndex =0    arrLen = len(arr)    for i in range(arrLen):        if not bucket[arr[i]]:            bucket[arr[i]]=0        bucket[arr[i]]+=1    for j in range(bucketLen):        while bucket[j]>0:            arr[sortedIndex] = j            sortedIndex+=1            bucket[j]-=1    return arr

09 Bucket SortBucket Sort is an upgraded version of Counting Sort. It relies on the mapping relationship of functions; the key to its efficiency lies in the determination of this mapping function. To make Bucket Sort more efficient, we need to achieve two points:

1. Increase the number of buckets as much as possible when there is sufficient extra space.
2. Ensure that the mapping function can evenly distribute the N input data into K buckets.

Additionally, the choice of comparison sorting algorithm for sorting the elements within the buckets significantly affects performance.

• When is it fastest?

When the input data can be evenly distributed across each bucket.

• When is it slowest?

When the input data is allocated to the same bucket.

• Python Code

def bucket_sort(s):    """Bucket Sort"""    min_num = min(s)    max_num = max(s)    # Size of the buckets    bucket_range = (max_num-min_num) / len(s)    # Bucket array    count_list = [ [] for i in range(len(s) + 1)]    # Fill the bucket array    for i in s:        count_list[int((i-min_num)//bucket_range)].append(i)    s.clear()    # Refilling, directly calling sorted for internal bucket sorting    for i in count_list:        for j in sorted(i):            s.append(j)
if __name__ == '__main__':    a = [3.2,6,8,4,2,6,7,3]    bucket_sort(a)    print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]

10 Radix SortRadix Sort is a non-comparison based integer sorting algorithm. Its principle is to cut integers into different digits and then compare them based on each digit. Since integers can also represent strings (like names or dates) and specific formatted floating-point numbers, Radix Sort is not limited to integers.

1. Radix Sort vs Counting Sort vs Bucket Sort

Radix Sort has two methods:These three sorting algorithms all utilize the concept of buckets but differ significantly in their usage:

• Radix Sort: Allocates buckets based on each digit of the key value;
• Counting Sort: Each bucket stores a single key value;
• Bucket Sort: Each bucket stores a certain range of values.

2. Animated Demo3. Python Code

def RadixSort(list):    i = 0                                    # Start with sorting by the unit place    n = 1                                     # Set the smallest digit to 1 (including 0)    max_num = max(list) # Get the maximum number in the array to be sorted    while max_num > 10**n: # Determine how many digits the maximum number has        n += 1    while i < n:        bucket = {} # Use a dictionary to construct buckets        for x in range(10):            bucket.setdefault(x, []) # Empty each bucket        for x in list: # Sort each digit            radix =int((x / (10**i)) % 10) # Get the radix for each digit            bucket[radix].append(x) # Add the corresponding number to the respective digit bucket        j = 0        for k in range(10):            if len(bucket[k]) != 0: # If the bucket is not empty                for y in bucket[k]: # Place each element in that bucket                    list[j] = y # Put back into the array                    j += 1        i += 1    return list

Editor: Wang JingProofreader: Lin Yilin