top 5 sorting algorithms with code examples

Top 5 Sorting Algorithms with Python Code Examples

Sorting algorithms form the backbone of computer science and software engineering, playing a crucial role in organizing data efficiently. In this article, we'll explore the top five sorting algorithms, complete with Python code examples, to help you understand their mechanics and choose the right one for your needs.

1. Bubble Sort

Overview:

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted. Despite its simplicity, bubble sort is not suitable for large data sets due to its inefficiency.

Python Code Example:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

This algorithm has a time complexity of O(n²) in the average and worst-case scenarios, making it less efficient for larger lists Analytics Vidhya.

2. Selection Sort

Overview:

Selection sort divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted. Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element from the unsorted sublist, swapping it with the leftmost unsorted element, and moving the sublist boundaries one element to the right.

Python Code Example:

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Selection sort is also O(n²) inefficient, but it is more straightforward than bubble sort GeeksforGeeks.

3. Insertion Sort

Overview:

Insertion sort builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms like quicksort, heapsort, or merge sort. However, it is more efficient in practice compared to those algorithms when sorting smaller datasets.

Python Code Example:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

With a time complexity of O(n²), insertion sort excels in sorting small arrays and lists Real Python.

4. Merge Sort

Overview:

Merge sort is an efficient, stable, and general-purpose sorting algorithm. It is a divide and conquer algorithm that was invented by John von Neumann in 1945. It works by dividing the unsorted list into n sublists, each containing one element, then repeatedly merging sublists to produce new sorted sublists until there is only one sublist remaining.

Python Code Example:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

Merge sort operates in O(n log n) time complexity, making it efficient for large data sets Educative.io.

5. Quick Sort

Overview:

Quick sort is an efficient sorting algorithm that utilizes a "divide and conquer" strategy. Developed by Tony Hoare in 1960, it works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Python Code Example:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

Quick sort is generally faster in practice than other O(n log n) algorithms, due to better cache performance and average performance Practicus AI.

Conclusion

In summary, selecting the appropriate sorting algorithm depends largely on the size and nature of the dataset you are working with. Bubble and selection sorts are easy to understand and implement but are only suitable for small datasets due to their inefficiency. Insertion sort can be more efficient for small to medium datasets. Merge sort and quicksort are robust choices for larger datasets, offering more reliable performance across a wide range of conditions.

These algorithms form an essential toolkit in any developer's arsenal, enabling more informed and effective data manipulation strategies.