"Common Sorting Algorithms in Python with Examples"

Sorting algorithms are a fundamental part of computer science and often a hot topic in coding interviews. Understanding how these algorithms work, their time complexities, and their implementations in Python is essential for anyone preparing for a Python language interview. In this blog, we’ll cover some common sorting algorithms, explain their mechanics, and provide Python implementations to help you ace your Python language interview questions.

Table of Contents

1. Bubble Sort

2. Selection Sort

3. Insertion Sort

4. Merge Sort

5. Quick Sort

6. Python's Built-in Sorting Method

7. Comparing Time Complexities

1. Bubble Sort

How It Works

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

Python Implementation

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

# Example
array = [64, 34, 25, 12, 22, 11, 90]
print("Sorted array:", bubble_sort(array))

Time Complexity

• Best Case: O(n) (when the array is already sorted)

• Worst Case: O(n²)

• Average Case: O(n²)

2. Selection Sort

How It Works

Selection Sort divides the list into two parts: sorted and unsorted. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the sorted part.

Python Implementation

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

# Example
array = [64, 25, 12, 22, 11]
print("Sorted array:", selection_sort(array))

Time Complexity

• Best Case: O(n²)

• Worst Case: O(n²)

• Average Case: O(n²)

3. Insertion Sort

How It Works

Insertion Sort builds the sorted list one element at a time. It picks an element from the unsorted part and inserts it into the correct position in the sorted part.

Python Implementation

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

# Example
array = [12, 11, 13, 5, 6]
print("Sorted array:", insertion_sort(array))

Time Complexity

• Best Case: O(n)

• Worst Case: O(n²)

• Average Case: O(n²)

4. Merge Sort

How It Works

Merge Sort is a divide-and-conquer algorithm. It divides the array into halves, recursively sorts each half, and then merges the sorted halves.

Python Implementation

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

# Example
array = [38, 27, 43, 3, 9, 82, 10]
print("Sorted array:", merge_sort(array))

Time Complexity

• Best Case: O(n log n)

• Worst Case: O(n log n)

• Average Case: O(n log n)

5. Quick Sort

How It Works

Quick Sort is another divide-and-conquer algorithm. It selects a "pivot" element, partitions the array around the pivot, and recursively applies the same logic to the sub-arrays.

Python Implementation

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    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)

# Example
array = [10, 7, 8, 9, 1, 5]
print("Sorted array:", quick_sort(array))

Time Complexity

• Best Case: O(n log n)

• Worst Case: O(n²)

• Average Case: O(n log n)

6. Python's Built-in Sorting Method

Python provides a highly optimized sorting function called sorted() and an in-place sort method for lists called .sort().

Example

array = [64, 34, 25, 12, 22, 11, 90]
print("Sorted array using sorted():", sorted(array))

# In-place sort
array.sort()
print("Sorted array using .sort():", array)

Time Complexity

• Best Case: O(n log n)

• Worst Case: O(n log n)

• Average Case: O(n log n)

7. Comparing Time Complexities

Algorithm	Best Case	Average Case	Worst Case
Bubble Sort	O(n)	O(n²)	O(n²)
Selection Sort	O(n²)	O(n²)	O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)
Merge Sort	O(n log n)	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n log n)	O(n²)
Python's sort	O(n log n)	O(n log n)	O(n log n)

Conclusion

Sorting algorithms are a crucial topic in Python language interview questions, especially for roles requiring algorithmic problem-solving skills. Understanding their mechanics, strengths, and weaknesses can help you make informed decisions during interviews