Sorting Algorithms Analysis

Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It works by dividing the input list into two parts: a sorted sublist of items that is built up from left to right and remains sorted, and a sublist of the remaining unsorted items. The algorithm repeatedly selects the smallest (or largest, depending on the order) element from the unsorted sublist, swapping it with the leftmost unsorted element, and moving the sublist boundaries one element to the right.

Algorithm Steps:

1. Start with first element as the minimum.
2. Traverse the array to find the smallest element.
3. Swap the smallest element with the first element.
4. Move to the next element and repeat until the entire array is sorted.

1def selection_sort(arr):
2    n = len(arr)
3    for i in range(n):
4        # Find the minimum element in remaining unsorted array
5        min_index = i
6        for j in range(i+1, n):
7            if arr[j] < arr[min_index]:
8                min_index = j
9        # Swap the found minimum element with the first element
10        arr[i], arr[min_index] = arr[min_index], arr[i]
11    return arr
12
13# Example usage
14unsorted_list = [41, 39, 16, 12, 56, 89]
15print("Unsorted List: ", unsorted_list)
16sorted_list = selection_sort(unsorted_list)
17print("Sorted List: ", sorted_list)
18

Complexity Analysis:

• Time Complexity: O(n²)
• Space Complexity: O(1)

Bubble Sort

Bubble Sort is another simple comparison-based algorithm. The algorithm 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.

Algorithm Steps:

1. Start at the beginning of the array.
2. Compare each pair of adjacent and swap them if necessary.
3. Repeat the process for the entire array.
4. Repeat steps 1-4 for all elements, reducing the range of comparison by one each time.

1def bubble_sort(arr):
2    n = len(arr)
3    for i in range(n):
4        # Traverse the array from 0 to n-i-1
5        for j in range(0, n - i - 1):
6            # Swap if the element found is greater than the next element
7            if arr[j] > arr[j + 1]:
8                arr[j], arr[j + 1] = arr[j + 1], arr[j]
9    return arr
10
11# Example usage:
12unsorted_list = [41, 39, 16, 12, 56, 89]
13print("Unsorted List: ", unsorted_list)
14sorted_list = bubble_sort(unsorted_list)
15print("Sorted List: ", sorted_list)
16

Complexity Analysis:

• Time Complexity: O(n²)
• Space Complexity: O(1)

Insertion Sort

Insertion sort is a simple and intuitive sorting algorithm that builds the final sorted array one item at a time. It is much like sorting playing cards in your hands; you pick up one card at a time and insert it into its correct position among the already sorted cards.

Algorithm Steps:

1. Start with the first element as the sorted part.
2. Take the next element and insert it into the correct position in the sorted part.
3. Shift all larger elements in the sorted part to the right to make room for the new element.
4. Repeat steps 2-3 until the entire array is sorted.

1def insertion_sort(arr):
2    for i in range(1, len(arr)):
3        key = arr[i]
4        j = i - 1
5        # Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
6        while j >= 0 and key < arr[j]:
7            arr[j + 1] = arr[j]
8            j -= 1
9        arr[j + 1] = key
10    return arr
11
12# Example usage:
13unsorted_list = [41, 39, 16, 12, 56, 89]
14print("Unsorted List: ", unsorted_list)
15sorted_list = insertion_sort(unsorted_list)
16print("Sorted List: ", sorted_list)
17

Complexity Analysis:

• Time Complexity: O(n²)
• Space Complexity: O(1)

Quick Sort

Quick Sort is a highly efficient and popular sorting algorithm that uses the divide-and-conquer strategy. 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.

Algorithm Steps:

1. Choose a pivot element.
2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
3. Recursively apply quicksort to the left and right sub-arrays.
4. Combine the sorted sub-arrays and the pivot into the final sorted array.

1def quick_sort(arr):
2    # Base case: array with 0 or 1 elements is already sorted
3    if len(arr) <= 1:
4        return arr
5    # Choose pivot element
6    pivot = arr[len(arr) // 2]
7    # Partition the array into three parts
8    left = [x for x in arr if x < pivot]
9    middle = [x for x in arr if x == pivot]
10    right = [x for x in arr if x > pivot]
11    # Recursively apply quicksort to left and right parts, then concatenate results
12    return quick_sort(left) + middle + quick_sort(right)
13
14# Example usage:
15unsorted_list = [41, 39, 16, 12, 56, 89]
16print("Unsorted List: ", unsorted_list)
17sorted_list = quick_sort(unsorted_list)
18print("Sorted List: ", sorted_list)
19

Complexity Analysis:

• Time Complexity: O(n²)
• Space Complexity: O(log n)

Merge Sort

Merge Sort is an efficient, stable, comparison-based sorting algorithm. It divides the array into two halves, sorts each half recursively, and then merges the sorted halves to produce the final sorted array. This divide-and-conquer approach ensures that the algorithm has a consistent time complexity of O(n log n). However, it requires additional space proportional to the array size, which can be a disadvantage.

Algorithm Steps:

1. Find the middle point to divide the array into two halves.
2. Recursively apply merge sort to the left half.
3. Recursively apply merge sort to the right half.
4. Merge the two sorted halves to produce the final sorted array.

1def merge_sort(arr):
2    if len(arr) > 1:
3        # Find the middle point to divide the array into two halves
4        mid = len(arr) // 2
5        L = arr[:mid]
6        R = arr[mid:]
7
8        # Sort the first and second halves
9        merge_sort(L)
10        merge_sort(R)
11
12        i = j = k = 0
13
14        # Copy data to temp arrays L[] and R[]
15        while i < len(L) and j < len(R):
16            if L[i] < R[j]:
17                arr[k] = L[i]
18                i += 1
19            else:
20                arr[k] = R[j]
21                j += 1
22            k += 1
23
24        # Checking if any element was left
25        while i < len(L):
26            arr[k] = L[i]
27            i += 1
28            k += 1
29
30        while j < len(R):
31            arr[k] = R[j]
32            j += 1
33            k += 1
34    return arr
35
36# Example usage:
37unsorted_list = [41, 39, 16, 12, 56, 89]
38print("Unsorted List: ", unsorted_list)
39sorted_list = merge_sort(unsorted_list)
40print("Sorted List: ", sorted_list)
41

Complexity Analysis:

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It first builds a max heap from the input data and then repeatedly extracts the maximum element from the heap and rebuilds the heap until all elements are sorted. Heap Sort is notable for its O(n log n) time complexity and in-place sorting capability, making it a good choice for situations where space complexity is a concern. However, it is not a stable sort, meaning the relative order of equal elements may not be preserved.

Algorithm Steps:

1. Build a max heap from the input data.
2. Swap the root (maximum value) with the last element of the heap.
3. Reduce the heap size by one.
4. Heapify the root element to ensure the heap property is maintained.
5. Repeat steps 2-4 until the heap size is reduced to 1.

1def heapify(arr, n, i):
2    # Initialize largest as root
3    largest = i
4    l = 2 * i + 1  # left = 2*i + 1
5    r = 2 * i + 2  # right = 2*i + 2
6
7    # See if left child of root exists and is greater than root
8    if l < n and arr[l] > arr[largest]:
9        largest = l
10
11    # See if right child of root exists and is greater than root
12    if r < n and arr[r] > arr[largest]:
13        largest = r
14
15    # Change root, if needed
16    if largest != i:
17        arr[i], arr[largest] = arr[largest], arr[i]  # swap
18        # Heapify the root
19        heapify(arr, n, largest)
20
21def heap_sort(arr):
22    n = len(arr)
23
24    # Build a maxheap
25    for i in range(n // 2 - 1, -1, -1):
26        heapify(arr, n, i)
27
28    # One by one extract elements
29    for i in range(n - 1, 0, -1):
30        arr[i], arr[0] = arr[0], arr[i]  # swap
31        heapify(arr, i, 0)
32    return arr
33
34# Example usage:
35    unsorted_list = [41, 39, 16, 12, 56, 89]
36print("Unsorted List: ", unsorted_list)
37sorted_list = heap_sort(unsorted_list)
38print("Sorted List: ", sorted_list)
39

Complexity Analysis:

• Time Complexity: O(n log n)
• Space Complexity: O(1)

Sorting Algorithms Analysis

First things first, lets understand Big O, Big Ω, and Big θ notations.

Big O (O): It describes the worst-case time complexity of an algorithm, providing an upper bound on the time it takes to complete as the input size grows. It helps understand the maximum time an algorithm might take.

Big Ω (Ω): It describes the best-case time complexity, providing a lower bound on the time an algorithm takes to complete. It indicates the minimum time required.

Big θ (θ): It provides a tight bound on the time complexity, representing both the upper and lower bounds. It gives an accurate measure of the average time complexity of an algorithm.

Among the discussed sorting algorithms, Merge Sort and Quick Sort are generally preferred due to their efficient average-case time complexities of O(n log n). Merge Sort is stable and has a consistent performance with a guaranteed O(n log n) time complexity, but it requires additional space O(n). Quick Sort is often faster in practice for average cases due to low constant factors but can degrade to O(n²) in the worst case. Heap Sort is another robust option with O(n log n) time complexity and O(1) space complexity, making it suitable for space-constrained environments. The choice between them depends on the specific use case, stability requirements, and memory constraints.

Some of the LeetCode problems to try these algorithms:

• 912. Sort an Array
• 215. Kth Largest Element in an Array
• 75. Sort Colors
• 88. Merge Sorted Array
• 1685. Sum of Absolute Differences in a Sorted Array
• 164. Maximum Gap
• 148. Sort List

References

• https://www.bigocheatsheet.com/
• https://www.geeksforgeeks.org/sorting-algorithms/