12  Comparison sorting algorithms

13 Key concepts

13.1 Comparison vs. non comparison sorts

In the context of sorting algorithms, comparison sorts are algorithms that sort a sequence of elements by comparing pairs of elements and swapping them if they are in the wrong order, until the sequence is sorted. Comparison sorts are generally based on comparison-based sorting algorithms, such as merge sort, quicksort, and heapsort.

On the other hand, non-comparison sorts are algorithms that sort a sequence of elements without comparing pairs of elements. Non-comparison sorts are generally based on specialized sorting algorithms, such as counting sort, radix sort, and bucket sort.

Comparison sorts have a lower theoretical time complexity of O(nlogn) for the worst-case scenario. This is due to the fact that any comparison-based algorithm must compare a pair of elements at least once in order to determine their relative order, and the number of such comparisons that need to be made to sort a sequence of n elements grows at least logarithmically with n.

Non-comparison sorts can achieve linear time complexity for the average or worst-case scenario, which is faster than comparison sorts. However, non-comparison sorts are generally less versatile and have more restrictive assumptions about the nature of the input sequence, such as that the elements be integers within a certain range.

In practice, the choice between comparison and non-comparison sorts depends on the specific requirements of the problem being solved, such as the size of the input sequence, the range of possible values, and the desired level of efficiency and stability.

13.2 Bubble, Insertion and Selection sort

Bubble sort, insertion sort, and selection sort are three simple and widely used sorting algorithms. Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order until the entire list is sorted. Insertion sort builds the final sorted list by iterating through the list and inserting each unsorted element into its correct position in the sorted portion of the list. Selection sort selects the smallest unsorted element and swaps it with the leftmost unsorted element, moving the boundary of the sorted portion of the list one element to the right. While these sorting algorithms are easy to implement and understand, they generally have a worst-case time complexity of O(n^2), making them less efficient than more advanced sorting algorithms for large or complex lists.

13.2.1 Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly compares adjacent elements in a list and swaps them if they are in the wrong order. The algorithm iterates through the list until no more swaps are needed, indicating that the list is sorted. Bubble sort has a worst-case and average time complexity of O(n^2), where n is the number of elements in the list.

Here is the pseudocode for Bubble Sort in iterative form:

// Iterative Bubble Sort algorithm
bubble_sort(array):
    n = length(array)
    for i from 0 to n-1:
        for j from 0 to n-i-1:
            if array[j] > array[j+1]:
                swap(array[j], array[j+1])

It is also possible to implement bubble sort recursively.

Here is the pseudocode for Bubble Sort in recursive form:

// Recursive Bubble Sort algorithm
bubble_sort(array, n):
    if n == 1:
        return
        
    for i from 0 to n-1:
        if array[i] > array[i+1]:
            swap(array[i], array[i+1])
    
    bubble_sort(array, n-1)

In this recursive algorithm, the base case occurs when n is equal to 1, indicating that the array is already sorted. Otherwise, the algorithm iterates through the array and swaps adjacent elements if they are in the wrong order. The algorithm then makes a recursive call to bubble_sort with n-1, which reduces the size of the array by 1 and repeats the process until the entire array is sorted.

Note that the recursive version of Bubble Sort has a worst-case time complexity of O(n^2), the same as the iterative version, since both implementations make the same number of comparisons and swaps.

I hope this helps! Let me know if you have any further questions.

13.2.2 Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted list one element at a time. The algorithm iterates through the list and repeatedly inserts each unsorted element into its correct position in the sorted portion of the list. The sorted portion of the list grows until all elements are sorted. Insertion sort has a worst-case and average time complexity of O(n^2), but can perform better than other quadratic sorting algorithms on small or nearly sorted lists.

Here is the pseudocode for Insertion Sort in iterative form:

// Iterative Insertion Sort algorithm
insertion_sort(array):
    n = length(array)
    for i from 1 to n-1:
        key = array[i]
        j = i-1
        while j >= 0 and array[j] > key:
            array[j+1] = array[j]
            j = j-1
        array[j+1] = key

Here is the pseudocode for Insertion Sort in recursive form:

// Recursive Insertion Sort algorithm
insertion_sort(array, n):
    if n <= 1:
        return
    
    insertion_sort(array, n-1)
    
    key = array[n-1]
    j = n-2
    
    while j >= 0 and array[j] > key:
        array[j+1] = array[j]
        j = j-1
    
    array[j+1] = key

In this recursive algorithm, the base case occurs when n is less than or equal to 1, indicating that the array is already sorted. Otherwise, the algorithm makes a recursive call to insertion_sort with n-1, which sorts the first n-1 elements of the array. The algorithm then places the nth element in its correct position in the sorted subarray by iterating through the subarray and shifting elements to the right until the correct position is found.

Note that the recursive version of Insertion Sort has a worst-case time complexity of O(n^2), the same as the iterative version, since both implementations make the same number of comparisons and swaps.

13.2.3 Selection Sort

Selection sort is a simple sorting algorithm that repeatedly selects the smallest unsorted element and swaps it with the leftmost unsorted element, moving the boundary of the sorted portion of the list one element to the right. The algorithm iterates through the list until the entire list is sorted. Selection sort has a worst-case and average time complexity of O(n^2), and is generally less efficient than other quadratic sorting algorithms.

Here is the pseudocode for Selection Sort in iterative form:

// Iterative Selection Sort algorithm
selection_sort(array):
    n = length(array)
    for i from 0 to n-1:
        min_idx = i
        for j from i+1 to n-1:
            if array[j] < array[min_idx]:
                min_idx = j
        swap(array[i], array[min_idx])

And here is the pseudocode for Selection Sort in recursive form:

// Recursive Selection Sort algorithm
selection_sort(array, start_idx):
    n = length(array)
    if start_idx >= n-1:
        return
    
    min_idx = start_idx
    for i from start_idx+1 to n-1:
        if array[i] < array[min_idx]:
            min_idx = i
    
    swap(array[start_idx], array[min_idx])
    selection_sort(array, start_idx+1)

In this recursive algorithm, the base case occurs when the start index is greater than or equal to n-1, indicating that the array is already sorted. Otherwise, the algorithm selects the smallest element in the unsorted portion of the array by iterating through the array from the start index and comparing each element to the current minimum. The algorithm then swaps the smallest element with the leftmost unsorted element and makes a recursive call to selection_sort with start_idx+1, which sorts the remaining unsorted elements.

Note that the recursive version of Selection Sort has a worst-case time complexity of O(n^2), the same as the iterative version, since both implementations make the same number of comparisons and swaps.

Overall, these sorting algorithms are simple and easy to implement, but they are generally less efficient than more advanced sorting algorithms for large or complex lists.

13.3 Recursive sorts: Mergesort and Quicksort

In the context of comparison sorting algorithms, recursive sorts are algorithms that use a recursive approach to divide the input list into smaller sublists, sort the sublists recursively, and combine the sorted sublists to obtain the final sorted list. Recursive sorts are often based on divide-and-conquer strategies, which can lead to more efficient sorting algorithms than those based on simple comparison-based approaches.

Mergesort and Quicksort are two of the most popular recursive sorting algorithms, and they are particularly relevant in this category because they both have a worst-case time complexity of O(nlogn) and are widely used in practice.

13.3.1 Mergesort

Mergesort divides the input list into two halves, sorts each half recursively using mergesort, and then merges the sorted halves into a single sorted list. Mergesort is a stable sorting algorithm, which means that it preserves the relative order of equal elements in the input list, and it is often used in situations where stability is important.

Here is the pseudocode for recursive mergesort:

// Recursive Mergesort algorithm
mergesort(array):
    n = length(array)
    if n == 1:
        return array
    
    mid = n // 2
    left = mergesort(array[0:mid])
    right = mergesort(array[mid:n])
    
    return merge(left, right)
    
// Merge function
merge(left, right):
    result = []
    i = 0
    j = 0
    
    while i < length(left) and j < length(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    while i < length(left):
        result.append(left[i])
        i += 1
    
    while j < length(right):
        result.append(right[j])
        j += 1
    
    return result

In this recursive algorithm, the input list is first divided into halves recursively until the base case of n = 1 is reached. Then, the sorted halves are merged back together using the merge function, which iterates through the two sorted subarrays and compares their elements to create a new sorted array. The merge function works by copying the two subarrays into temporary arrays, comparing their elements, and copying them back into the original array in sorted order.

Note that the recursive mergesort algorithm has a worst-case time complexity of O(nlogn) and is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the input list.

It is also possible to implement mergesort iteratively using an algorithm known as iterative mergesort or bottom-up mergesort. This algorithm does not use recursion, and instead works by iteratively merging adjacent subarrays of the input list until the entire list is sorted.

The basic idea behind iterative mergesort is to start by merging adjacent pairs of elements in the input list to create sorted subarrays of size 2. The algorithm then merges adjacent pairs of subarrays to create sorted subarrays of size 4, and so on, until the entire input list is sorted.

Here is the pseudocode for iterative mergesort:

// Iterative Mergesort algorithm
mergesort(array):
    n = length(array)
    subarray_size = 1
    while subarray_size < n:
        for i from 0 to n-subarray_size-1 step subarray_size*2:
            left = i
            right = min(i+subarray_size, n)
            end = min(i+subarray_size*2, n)
            merge(array, left, right, end)
        subarray_size *= 2

In this iterative algorithm, the input list is first divided into subarrays of size 1, and then adjacent subarrays are merged iteratively until the entire list is sorted. The merge function is used to merge adjacent subarrays, and it works by copying the two subarrays into temporary arrays, comparing their elements, and copying them back into the original array in sorted order.

Note that the iterative mergesort algorithm has the same worst-case time complexity of O(nlogn) as the recursive mergesort algorithm, but it can be more efficient in practice due to its better cache locality and lack of recursion overhead.

13.3.2 Quicksort

Quicksort also uses a divide-and-conquer approach, but it sorts the input list in place by selecting a pivot element and partitioning the list into two sublists, one containing elements smaller than the pivot and the other containing elements greater than or equal to the pivot. Quicksort then recursively sorts each sublist using quicksort, and combines the sorted sublists to obtain the final sorted list. Quicksort is often faster than mergesort in practice due to its cache efficiency and low constant factors, but it can have a worst-case time complexity of O(n^2) if the pivot selection is not optimal.

Here is the pseudocode for the Recursive Quicksort algorithm:

// Recursive Quicksort algorithm
quicksort(array, start, end):
    if start < end:
        pivot = partition(array, start, end)
        quicksort(array, start, pivot-1)
        quicksort(array, pivot+1, end)

// Partition function
partition(array, start, end):
    pivot = array[end]
    i = start - 1
    
    for j from start to end-1:
        if array[j] < pivot:
            i += 1
            swap(array[i], array[j])
    
    swap(array[i+1], array[end])
    return i+1

In this recursive algorithm, the quicksort function sorts the input array by first partitioning the array around a pivot element, and then recursively sorting the resulting sublists. The partition function selects the rightmost element of the subarray as the pivot element, and rearranges the elements such that all elements less than the pivot are to its left, and all elements greater than the pivot are to its right.

The quicksort function then recursively sorts the subarray to the left and right of the pivot by calling itself on each of the subarrays. This process continues until the subarrays have a size of 1 or 0, at which point they are considered sorted.

Note that the time complexity of recursive Quicksort is O(nlogn) on average, but can be O(n^2) in the worst case if the pivot selection is not optimal.

14 Learning outcomes

14.1 Identify the different approaches of different comparison sorting algorithms

Comparison sorting algorithms are algorithms that sort a list of elements by comparing each element to one another. They can be broadly categorized into two main approaches: comparison-based and non-comparison-based.

Comparison-based algorithms are the most common approach to sorting and work by comparing pairs of elements in the input list and swapping them if they are out of order. These algorithms have a worst-case time complexity of O(nlogn) and are generally slower than non-comparison-based algorithms for large datasets. Some popular comparison-based sorting algorithms include Quicksort, Mergesort, Heapsort, Insertion Sort, and Selection Sort.

Non-comparison-based algorithms, on the other hand, do not compare individual elements to one another, but instead rely on other properties of the input data to sort the list. These algorithms can achieve linear time complexity, but are often more complex and less flexible than comparison-based algorithms. Examples of non-comparison-based sorting algorithms include Counting Sort, Radix Sort, and Bucket Sort.

It is worth noting that some sorting algorithms, such as Introsort and Timsort, combine elements of both comparison-based and non-comparison-based approaches to achieve a balance between performance and simplicity.

Overall, the choice of sorting algorithm depends on several factors, including the size of the input list, the distribution of the input values, and the specific requirements of the application.

14.2 Implement different comparison sorting algorithms

See the text above.

Here is the implementation of some of the popular comparison sorting algorithms in Python:

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

Insertion Sort:

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

Selection Sort:

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

Merge Sort:

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

Quick Sort:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort(left) + [pivot] + quick_sort(right)

Note that these are just sample implementations and there are many variations and optimizations that can be made to these algorithms depending on the specific requirements of the application. Additionally, these implementations may not be the most efficient or optimal for all cases.

14.3 Calculate the time complexity of different comparison sorting algorithms

The time complexity of different comparison sorting algorithms can vary depending on the specific implementation and the properties of the input data. Here are the time complexities of some common comparison sorting algorithms:

Bubble Sort:

• Best Case: O(n)
• Worst Case: O(n^2)
• Average Case: O(n^2)

Insertion Sort: - Best Case: O(n) - Worst Case: O(n^2) - Average Case: O(n^2)

Selection Sort: - Best Case: O(n^2) - Worst Case: O(n^2) - Average Case: O(n^2)

Merge Sort: - Best Case: O(nlogn) - Worst Case: O(nlogn) - Average Case: O(nlogn)

Quick Sort: - Best Case: O(nlogn) - Worst Case: O(n^2) - Average Case: O(nlogn)

Note that these time complexities are based on the number of comparisons or operations required to sort an input list of n elements. The actual running time of an algorithm may depend on factors such as memory access times, cache behavior, and the specific implementation of the algorithm. Additionally, there are other factors to consider when choosing a sorting algorithm, such as the stability of the algorithm, the space complexity, and the ease of implementation.