The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Advanced Sorting Algorithms

Next ►
►

In this section, we will delve into advanced sorting algorithms that go beyond the basic ones like Bubble Sort, Insertion Sort, and Selection Sort. These advanced algorithms are more efficient and are used in real-world applications where performance is critical.

Key Concepts

  1. Time Complexity: Understanding the efficiency of sorting algorithms in terms of time.
  2. Space Complexity: Understanding the memory usage of sorting algorithms.
  3. Stability: Whether the sorting algorithm maintains the relative order of equal elements.
  4. Comparison-based vs. Non-comparison-based: Differentiating between algorithms that compare elements and those that do not.

Advanced Sorting Algorithms Covered

  1. Merge Sort
  2. Quick Sort
  3. Heap Sort
  4. Radix Sort
  5. Bucket Sort

  1. Merge Sort

Explanation

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

Steps

  1. Divide the array into two halves.
  2. Recursively sort each half.
  3. Merge the two sorted halves into a single sorted array.

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

# Example usage
arr = [12, 11, 13, 5, 6, 7]
print("Sorted array is:", merge_sort(arr))

Analysis

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

  1. Quick Sort

Explanation

Quick Sort is another divide-and-conquer algorithm that selects a 'pivot' element and partitions the array around the pivot, recursively sorting the partitions.

Steps

  1. Choose a pivot element.
  2. Partition the array such that elements less than the pivot are on the left, and elements greater than the pivot are on the right.
  3. Recursively apply the above steps to the sub-arrays.

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)

# Example usage
arr = [3, 6, 8, 10, 1, 2, 1]
print("Sorted array is:", quick_sort(arr))

Analysis

  • Time Complexity: O(n log n) on average, O(n^2) in the worst case
  • Space Complexity: O(log n)
  • Stability: Not stable

  1. Heap Sort

Explanation

Heap Sort involves building a heap data structure from the array and then repeatedly extracting the maximum element from the heap and rebuilding the heap.

Steps

  1. Build a max heap from the input data.
  2. Extract the maximum element from the heap and place it at the end of the array.
  3. Repeat the process for the remaining elements.

Code Example

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[i] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    return arr

# Example usage
arr = [12, 11, 13, 5, 6, 7]
print("Sorted array is:", heap_sort(arr))

Analysis

  • Time Complexity: O(n log n)
  • Space Complexity: O(1)
  • Stability: Not stable

  1. Radix Sort

Explanation

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers by processing individual digits.

Steps

  1. Sort the numbers based on the least significant digit.
  2. Move to the next significant digit and repeat the process.

Code Example

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max1 = max(arr)
    exp = 1
    while max1 // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

    return arr

# Example usage
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("Sorted array is:", radix_sort(arr))

Analysis

  • Time Complexity: O(nk), where k is the number of digits in the largest number
  • Space Complexity: O(n + k)
  • Stability: Stable

  1. Bucket Sort

Explanation

Bucket Sort distributes elements into several buckets, sorts each bucket individually, and then concatenates the sorted buckets.

Steps

  1. Create buckets and distribute the elements into them.
  2. Sort each bucket individually.
  3. Concatenate all sorted buckets.

Code Example

def bucket_sort(arr):
    bucket = []
    slot_num = 10

    for i in range(slot_num):
        bucket.append([])

    for j in arr:
        index_b = int(slot_num * j)
        bucket[index_b].append(j)

    for i in range(slot_num):
        bucket[i] = sorted(bucket[i])

    k = 0
    for i in range(slot_num):
        for j in range(len(bucket[i])):
            arr[k] = bucket[i][j]
            k += 1

    return arr

# Example usage
arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
print("Sorted array is:", bucket_sort(arr))

Analysis

  • Time Complexity: O(n + k), where k is the number of buckets
  • Space Complexity: O(n + k)
  • Stability: Stable

Practical Exercises

Exercise 1: Implement Merge Sort

Implement the Merge Sort algorithm and test it on an array of your choice.

Solution

Refer to the Merge Sort code example above.

Exercise 2: Implement Quick Sort

Implement the Quick Sort algorithm and test it on an array of your choice.

Solution

Refer to the Quick Sort code example above.

Exercise 3: Compare Sorting Algorithms

Write a program that compares the performance of Merge Sort, Quick Sort, and Heap Sort on large datasets.

Solution

import time
import random

def compare_sorts():
    arr = [random.randint(0, 100000) for _ in range(100000)]

    start = time.time()
    merge_sort(arr.copy())
    print("Merge Sort took", time.time() - start, "seconds")

    start = time.time()
    quick_sort(arr.copy())
    print("Quick Sort took", time.time() - start, "seconds")

    start = time.time()
    heap_sort(arr.copy())
    print("Heap Sort took", time.time() - start, "seconds")

compare_sorts()

Conclusion

In this section, we explored several advanced sorting algorithms, including Merge Sort, Quick Sort, Heap Sort, Radix Sort, and Bucket Sort. Each algorithm has its own strengths and weaknesses, making them suitable for different types of problems. Understanding these algorithms and their complexities is crucial for solving high-difficulty computational problems efficiently.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved