Loading topic...

Sorting Algorithms Tutorial**in C

Sorting Algorithms

Sorting algorithms are fundamental to computer science. They arrange elements of a collection in a specific order (typically ascending or descending).

Module 22: Sorting Algorithms

A Comprehensive Formal Tutorial

Introduction

Sorting algorithms are fundamental to computer science. They arrange elements of a collection in a specific order (typically ascending or descending). Efficient sorting enables optimized searching, data organization, and improved performance of other algorithms.

This tutorial covers all major sorting algorithms with detailed explanations, time and space complexity analysis, Python implementations, and practical examples.

1. Bubble Sort

Bubble Sort is a simple, comparison-based sorting algorithm. It repeatedly traverses the list, compares adjacent elements, and swaps them if they are in the wrong order. Larger elements gradually "bubble up" to their correct positions.

Complexity Analysis

Time Complexity: $O(n^2)$ (worst and average case)
Space Complexity: $O(1)$ (in-place)
Stable: Yes

Python Implementation

python
1def bubble_sort(arr):
2    n = len(arr)
3    for i in range(n):
4        swapped = False
5        for j in range(0, n - i - 1):
6            if arr[j] > arr[j + 1]:
7                arr[j], arr[j + 1] = arr[j + 1], arr[j]
8                swapped = True
9        if not swapped:
10            break
11    return arr
12
13# Example
14data = [64, 34, 25, 12, 22, 11, 90]
15print(bubble_sort(data))
16# Output: [11, 12, 22, 25, 34, 64, 90]

2. Selection Sort

Selection Sort divides the input into a sorted and an unsorted region. In each iteration, it finds the minimum element from the unsorted region and swaps it with the first unsorted element.

Complexity Analysis

Time Complexity: $O(n^2)$ (always)
Space Complexity: $O(1)$
Stable: No (standard implementation)

Python Implementation

python
1def selection_sort(arr):
2    n = len(arr)
3    for i in range(n):
4        min_idx = i
5        for j in range(i + 1, n):
6            if arr[j] < arr[min_idx]:
7                min_idx = j
8        arr[i], arr[min_idx] = arr[min_idx], arr[i]
9    return arr
10
11# Example
12data = [64, 25, 12, 22, 11]
13print(selection_sort(data))

3. Insertion Sort

Insertion Sort builds the sorted array one element at a time by inserting each new element into its correct position within the already sorted portion.

Complexity Analysis

Time Complexity: $O(n^2)$ worst/average, $O(n)$ best (nearly sorted)
Space Complexity: $O(1)$
Stable: Yes

Python Implementation

python
1def insertion_sort(arr):
2    for i in range(1, len(arr)):
3        key = arr[i]
4        j = i - 1
5        while j >= 0 and arr[j] > key:
6            arr[j + 1] = arr[j]
7            j -= 1
8        arr[j + 1] = key
9    return arr

4. Merge Sort

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

Complexity Analysis

Time Complexity: $O(n \log n)$ (always)
Space Complexity: $O(n)$
Stable: Yes

Python Implementation

python
1def merge_sort(arr):
2    if len(arr) <= 1:
3        return arr
4    mid = len(arr) // 2
5    left = merge_sort(arr[:mid])
6    right = merge_sort(arr[mid:])
7    return merge(left, right)
8
9def merge(left, right):
10    result = []
11    i = j = 0
12    while i < len(left) and j < len(right):
13        if left[i] <= right[j]:
14            result.append(left[i])
15            i += 1
16        else:
17            result.append(right[j])
18            j += 1
19    result.extend(left[i:])
20    result.extend(right[j:])
21    return result

5. Quick Sort

Quick Sort is an efficient divide-and-conquer algorithm that selects a pivot element and partitions the array around it.

Complexity Analysis

Time Complexity: $O(n \log n)$ average, $O(n^2)$ worst
Space Complexity: $O(\log n)$ average

Python Implementation (Lomuto Partition Scheme)

python
1def quick_sort(arr, low=0, high=None):
2    if high is None:
3        high = len(arr) - 1
4    if low < high:
5        pi = partition(arr, low, high)
6        quick_sort(arr, low, pi - 1)
7        quick_sort(arr, pi + 1, high)
8    return arr
9
10def partition(arr, low, high):
11    pivot = arr[high]
12    i = low - 1
13    for j in range(low, high):
14        if arr[j] <= pivot:
15            i += 1
16            arr[i], arr[j] = arr[j], arr[i]
17    arr[i + 1], arr[high] = arr[high], arr[i + 1]
18    return i + 1

6. Heap Sort

Heap Sort utilizes a binary max-heap. It first builds a heap, then repeatedly extracts the maximum element while maintaining the heap property.

Complexity Analysis

Time Complexity: $O(n \log n)$
Space Complexity: $O(1)$
Stable: No

Python Implementation

python
1def heapify(arr, n, i):
2    largest = i
3    l, r = 2 * i + 1, 2 * i + 2
4    if l < n and arr[l] > arr[largest]:
5        largest = l
6    if r < n and arr[r] > arr[largest]:
7        largest = r
8    if largest != i:
9        arr[i], arr[largest] = arr[largest], arr[i]
10        heapify(arr, n, largest)
11
12def heap_sort(arr):
13    n = len(arr)
14    for i in range(n // 2 - 1, -1, -1):
15        heapify(arr, n, i)
16    for i in range(n - 1, 0, -1):
17        arr[i], arr[0] = arr[0], arr[i]
18        heapify(arr, i, 0)
19    return arr

7. Counting Sort

Counting Sort is a non-comparison integer sorting algorithm that counts occurrences of each value.

Complexity Analysis

Time Complexity: $O(n + k)$ (where $k$ is the range)
Space Complexity: $O(n + k)$
Stable: Yes

Python Implementation

python
1def counting_sort(arr):
2    if not arr:
3        return arr
4    min_val, max_val = min(arr), max(arr)
5    count = [0] * (max_val - min_val + 1)
6    output = [0] * len(arr)
7    
8    for num in arr:
9        count[num - min_val] += 1
10    
11    for i in range(1, len(count)):
12        count[i] += count[i - 1]
13    
14    for i in range(len(arr) - 1, -1, -1):
15        output[count[arr[i] - min_val] - 1] = arr[i]
16        count[arr[i] - min_val] -= 1
17    
18    return output

8. Radix Sort

Radix Sort processes integer digits starting from the least significant digit (LSD) using a stable subroutine sort (usually Counting Sort).

Complexity Analysis

Time Complexity: $O(d(n + k))$ (where $d$ is number of digits)
Space Complexity: $O(n + k)$
Stable: Yes

Python Implementation

python
1def radix_sort(arr):
2    if not arr:
3        return arr
4    max_val = max(arr)
5    exp = 1
6    while max_val // exp > 0:
7        # Counting sort for current digit
8        n = len(arr)
9        output = [0] * n
10        count = [0] * 10
11        for i in range(n):
12            count[(arr[i] // exp) % 10] += 1
13        for i in range(1, 10):
14            count[i] += count[i - 1]
15        for i in range(n - 1, -1, -1):
16            digit = (arr[i] // exp) % 10
17            output[count[digit] - 1] = arr[i]
18            count[digit] -= 1
19        for i in range(n):
20            arr[i] = output[i]
21        exp *= 10
22    return arr

Practice Problems

1. Sort Students

Sort students by marks (descending) and by name (ascending) in case of ties.

python
1students = [
2    {"name": "Alice", "marks": 85},
3    {"name": "Bob", "marks": 92},
4    {"name": "Charlie", "marks": 85},
5    {"name": "Diana", "marks": 78}
6]
7
8sorted_students = sorted(students, key=lambda x: (-x["marks"], x["name"]))
9print(sorted_students)

2. Custom Sorting

Using cmp_to_key for advanced custom comparison.

python
1from functools import cmp_to_key
2
3def custom_cmp(a, b):
4    if len(a) != len(b):
5        return len(a) - len(b)
6    return -1 if a < b else (1 if a > b else 0)
7
8words = ["apple", "banana", "kiwi", "grape", "fig"]
9sorted_words = sorted(words, key=cmp_to_key(custom_cmp))
10print(sorted_words)

Summary Table

Algorithm	Time Complexity (Avg)	Worst Case	Space	Stable	In-place
Bubble Sort	$O(n^2)$	$O(n^2)$

Recommendation: For most real-world applications, use Python’s built-in sorted() or list.sort() (Timsort — a hybrid of Merge Sort and Insertion Sort) for optimal performance and stability.

This document is written in MDX format and can be directly used in documentation sites (Next.js, Docusaurus, etc.).


You can copy the entire content above and save it as `sorting-tutorial.mdx`. It follows a clean, formal, and professional structure suitable for educational or documentation purposes.

Loading topic...

Sorting Algorithms

Sorting algorithms are fundamental to computer science. They arrange elements of a collection in a specific order (typically ascending or descending).

Module 22: Sorting Algorithms

A Comprehensive Formal Tutorial

Introduction

This tutorial covers all major sorting algorithms with detailed explanations, time and space complexity analysis, Python implementations, and practical examples.

1. Bubble Sort

Complexity Analysis

Time Complexity: $O(n^2)$ (worst and average case)
Space Complexity: $O(1)$ (in-place)
Stable: Yes

Python Implementation

python
1def bubble_sort(arr):
2    n = len(arr)
3    for i in range(n):
4        swapped = False
5        for j in range(0, n - i - 1):
6            if arr[j] > arr[j + 1]:
7                arr[j], arr[j + 1] = arr[j + 1], arr[j]
8                swapped = True
9        if not swapped:
10            break
11    return arr
12
13# Example
14data = [64, 34, 25, 12, 22, 11, 90]
15print(bubble_sort(data))
16# Output: [11, 12, 22, 25, 34, 64, 90]

2. Selection Sort

Selection Sort divides the input into a sorted and an unsorted region. In each iteration, it finds the minimum element from the unsorted region and swaps it with the first unsorted element.

Complexity Analysis

Time Complexity: $O(n^2)$ (always)
Space Complexity: $O(1)$
Stable: No (standard implementation)

Python Implementation

python
1def selection_sort(arr):
2    n = len(arr)
3    for i in range(n):
4        min_idx = i
5        for j in range(i + 1, n):
6            if arr[j] < arr[min_idx]:
7                min_idx = j
8        arr[i], arr[min_idx] = arr[min_idx], arr[i]
9    return arr
10
11# Example
12data = [64, 25, 12, 22, 11]
13print(selection_sort(data))

3. Insertion Sort

Insertion Sort builds the sorted array one element at a time by inserting each new element into its correct position within the already sorted portion.

Complexity Analysis

Time Complexity: $O(n^2)$ worst/average, $O(n)$ best (nearly sorted)
Space Complexity: $O(1)$
Stable: Yes

Python Implementation

python
1def insertion_sort(arr):
2    for i in range(1, len(arr)):
3        key = arr[i]
4        j = i - 1
5        while j >= 0 and arr[j] > key:
6            arr[j + 1] = arr[j]
7            j -= 1
8        arr[j + 1] = key
9    return arr

4. Merge Sort

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

Complexity Analysis

Time Complexity: $O(n \log n)$ (always)
Space Complexity: $O(n)$
Stable: Yes

Python Implementation

python
1def merge_sort(arr):
2    if len(arr) <= 1:
3        return arr
4    mid = len(arr) // 2
5    left = merge_sort(arr[:mid])
6    right = merge_sort(arr[mid:])
7    return merge(left, right)
8
9def merge(left, right):
10    result = []
11    i = j = 0
12    while i < len(left) and j < len(right):
13        if left[i] <= right[j]:
14            result.append(left[i])
15            i += 1
16        else:
17            result.append(right[j])
18            j += 1
19    result.extend(left[i:])
20    result.extend(right[j:])
21    return result

5. Quick Sort

Quick Sort is an efficient divide-and-conquer algorithm that selects a pivot element and partitions the array around it.

Complexity Analysis

Time Complexity: $O(n \log n)$ average, $O(n^2)$ worst
Space Complexity: $O(\log n)$ average

Python Implementation (Lomuto Partition Scheme)

python
1def quick_sort(arr, low=0, high=None):
2    if high is None:
3        high = len(arr) - 1
4    if low < high:
5        pi = partition(arr, low, high)
6        quick_sort(arr, low, pi - 1)
7        quick_sort(arr, pi + 1, high)
8    return arr
9
10def partition(arr, low, high):
11    pivot = arr[high]
12    i = low - 1
13    for j in range(low, high):
14        if arr[j] <= pivot:
15            i += 1
16            arr[i], arr[j] = arr[j], arr[i]
17    arr[i + 1], arr[high] = arr[high], arr[i + 1]
18    return i + 1

6. Heap Sort

Heap Sort utilizes a binary max-heap. It first builds a heap, then repeatedly extracts the maximum element while maintaining the heap property.

Complexity Analysis

Time Complexity: $O(n \log n)$
Space Complexity: $O(1)$
Stable: No

Python Implementation

python
1def heapify(arr, n, i):
2    largest = i
3    l, r = 2 * i + 1, 2 * i + 2
4    if l < n and arr[l] > arr[largest]:
5        largest = l
6    if r < n and arr[r] > arr[largest]:
7        largest = r
8    if largest != i:
9        arr[i], arr[largest] = arr[largest], arr[i]
10        heapify(arr, n, largest)
11
12def heap_sort(arr):
13    n = len(arr)
14    for i in range(n // 2 - 1, -1, -1):
15        heapify(arr, n, i)
16    for i in range(n - 1, 0, -1):
17        arr[i], arr[0] = arr[0], arr[i]
18        heapify(arr, i, 0)
19    return arr

7. Counting Sort

Counting Sort is a non-comparison integer sorting algorithm that counts occurrences of each value.

Complexity Analysis

Time Complexity: $O(n + k)$ (where $k$ is the range)
Space Complexity: $O(n + k)$
Stable: Yes

Python Implementation

python
1def counting_sort(arr):
2    if not arr:
3        return arr
4    min_val, max_val = min(arr), max(arr)
5    count = [0] * (max_val - min_val + 1)
6    output = [0] * len(arr)
7    
8    for num in arr:
9        count[num - min_val] += 1
10    
11    for i in range(1, len(count)):
12        count[i] += count[i - 1]
13    
14    for i in range(len(arr) - 1, -1, -1):
15        output[count[arr[i] - min_val] - 1] = arr[i]
16        count[arr[i] - min_val] -= 1
17    
18    return output

8. Radix Sort

Radix Sort processes integer digits starting from the least significant digit (LSD) using a stable subroutine sort (usually Counting Sort).

Complexity Analysis

Time Complexity: $O(d(n + k))$ (where $d$ is number of digits)
Space Complexity: $O(n + k)$
Stable: Yes

Python Implementation

python
1def radix_sort(arr):
2    if not arr:
3        return arr
4    max_val = max(arr)
5    exp = 1
6    while max_val // exp > 0:
7        # Counting sort for current digit
8        n = len(arr)
9        output = [0] * n
10        count = [0] * 10
11        for i in range(n):
12            count[(arr[i] // exp) % 10] += 1
13        for i in range(1, 10):
14            count[i] += count[i - 1]
15        for i in range(n - 1, -1, -1):
16            digit = (arr[i] // exp) % 10
17            output[count[digit] - 1] = arr[i]
18            count[digit] -= 1
19        for i in range(n):
20            arr[i] = output[i]
21        exp *= 10
22    return arr

Practice Problems

1. Sort Students

Sort students by marks (descending) and by name (ascending) in case of ties.

python
1students = [
2    {"name": "Alice", "marks": 85},
3    {"name": "Bob", "marks": 92},
4    {"name": "Charlie", "marks": 85},
5    {"name": "Diana", "marks": 78}
6]
7
8sorted_students = sorted(students, key=lambda x: (-x["marks"], x["name"]))
9print(sorted_students)

2. Custom Sorting

Using cmp_to_key for advanced custom comparison.

python
1from functools import cmp_to_key
2
3def custom_cmp(a, b):
4    if len(a) != len(b):
5        return len(a) - len(b)
6    return -1 if a < b else (1 if a > b else 0)
7
8words = ["apple", "banana", "kiwi", "grape", "fig"]
9sorted_words = sorted(words, key=cmp_to_key(custom_cmp))
10print(sorted_words)

Summary Table

Algorithm	Time Complexity (Avg)	Worst Case	Space	Stable	In-place
Bubble Sort	$O(n^2)$	$O(n^2)$

This document is written in MDX format and can be directly used in documentation sites (Next.js, Docusaurus, etc.).


You can copy the entire content above and save it as `sorting-tutorial.mdx`. It follows a clean, formal, and professional structure suitable for educational or documentation purposes.