Algorithm Introduction Implement 4 types of sorting in Python from pseudo code of 3rd edition

Introduction

Some sorts are introduced in "Algorithm Introduction 3rd Edition (Volume 1)". Based on that pseudo code

--Insert sort --Merge sort --Heapsort --Quicksort

Is implemented in Python. Follow the same procedure as the pseudo code to copy the variable names. All the arguments ʻA` passed to the sort function described below are a list of elements arranged in random order.

Insertion sort

The insertion sort can be written as:

insertion_sort.py

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

Merge sort

Merge sort is made up of two parts.

--MERGE: Merge two aligned arrays into one aligned array --MERGE-SORT: MERGE the subdivided arrays in order by recursive call

merge_sort.py

def merge(A, p, q, r):
    n_1 = q - p + 1
    n_2 = r - q
    L = []
    R = []
    for i in range(n_1):
        L.append(A[p + i])
    for j in range(n_2):
        R.append(A[q + j + 1])
    L.append(SENTINEL)
    R.append(SENTINEL)
    i, j = 0, 0
    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return A


def merge_sort(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = (p + r) // 2
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)
    return A

Heapsort

Preparation: Represent the heap

In heapsort, a structure called heap is used. First, as a preliminary preparation, create a Heap class to represent the heap in Python. This is Python's built-in object list with the addition of an attribute called heap_size.

heap_sort.py

class Heap(list):
    def __init__(self, *args):
        super().__init__(*args)
        self.heap_size = len(self)

This heap keeps its function as a list. Try writing:

heap = Heap([1, 2, 3, 2, 3, 4])
print("heap:", heap)
print("heap.heap_size:", heap.heap_size)
print("len(heap):", len(heap))

The result of the execution is as follows:

heap: [1, 2, 3, 2, 3, 4]
heap.heap_size: 6
len(heap): 6

Now, heapsort

Heapsort can be done with 5 parts.

--LEFT: When the heap is represented by a binary tree, it returns the element that is the left child with itself as the parent. --RIGHT: RIGHT procedure to return the right child with you as the parent --MAX-HEAPIFY: Assuming that the heap is below the root, move the root to an appropriate position and make the whole heap. --BUILD-MAX-HEAP: MAX-HEAPIFY a completely random array to make the whole heap --HEAP-SORT: Sort the entire array by taking out the roots and repairing the rest as a heap.

Using the Heap class created in the preparation, these are as follows:

heap_sort.py

def left(i):
    return 2 * (i + 1) - 1

def right(i):
    return 2 * (i + 1)

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    if l <= A.heap_size - 1 and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= A.heap_size - 1 and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def build_max_heap(list_A):
    A = Heap(list_A)
    A.heap_size = len(A)
    for i in reversed(range((len(A) - 1) // 2 + 1)):
        max_heapify(A, i)
    return A

def heap_sort(list_A):
    A = build_max_heap(list_A)  #Where A becomes an instance of the Heap class
    for i in reversed(range(1, len(A))):
        A[0], A[i] = A[i], A[0]
        A.heap_size = A.heap_size - 1
        max_heapify(A, 0)
    return A

Quick sort

Quicksort can be done with two parts.

--PARTITION: $ A [p..r] $ made up of only elements below the pivot $ A [p..q-1] $ and $ A [q + 1 .. made up of only elements larger than the pivot. Divide into two parts, r] $ --QUICK-SORT: Call PARTITION recursively to sort the entire $ A [p..r] $

The pivot is $ A [r] $, that is, the rightmost element.

quick_sort.py

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

def quick_sort(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)
    return A

Bonus: Sort in non-increasing order (descending order)

All four sorts created so far are the ones with the smallest one on the left, and the ones with the order of increasing the one to the right. As a bonus, make four sorts in reverse order. The name of the function is something like (sort name) _nonincreasing.

A brief explanation is added by commenting out the part rewritten from the original sort function.

insertion_sort_nonincreasing.py

def insertion_sort_nonincreasing(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] < key:  #And and subsequent inequalities reorient
            A[i + 1] = A[i]
            i -= 1
        A[i + 1] = key
    return A

merge_sort_nonincreasing.py

SENTINEL_SMALL = - float('inf')  #Make the sentinel minus infinity

def merge_nonincreasing(A, p, q, r):
    n_1 = q - p + 1
    n_2 = r - q
    L = []
    R = []
    for i in range(n_1):
        L.append(A[p + i])
    for j in range(n_2):
        R.append(A[q + j + 1])
    L.append(SENTINEL_SMALL)  #Use a minus infinity sentinel
    R.append(SENTINEL_SMALL)  #Same as above
    i, j = 0, 0
    for k in range(p, r + 1):
        if L[i] >= R[j]:  #Reorientation of inequalities
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return A

def mergeSort_nonincreasing(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = (p + r) // 2
        mergeSort_nonincreasing(A, p, q)      #Rename yourself
        mergeSort_nonincreasing(A, q + 1, r)  #Same as above
        merge_nonincreasing(A, p, q, r)       #Merge in non-increasing order
    return A

heqp_sort_nonincreasing.py

def min_heapify(A, i):  #Name min_make it heapify
    l = left(i)
    r = right(i)
    if l <= A.heap_size - 1 and A[l] < A[i]:  #And and subsequent inequalities reorient
        smallest = l  #Change to smallest instead of largest
    else:
        smallest = i
    if r <= A.heap_size - 1 and A[r] < A[smallest]:  #And and subsequent inequalities reorient
        smallest = r
    if smallest != i:
        A[i], A[smallest] = A[smallest], A[i]
        min_heapify(A, smallest)  # max_min instead of heapify_heapify


def build_min_heap(list_A):  #Build name_min_to heap
    A = Heap(list_A)
    A.heap_size = len(A)
    for i in reversed(range((len(A) - 1) // 2 + 1)):
        min_heapify(A, i)  # max_min instead of heapify_heapify
    return A


def heapSort_nonincreasing(list_A):
    A = build_min_heap(list_A)  # build_max_build instead of heap_min_heap
    for i in reversed(range(1, len(A))):
        A[0], A[i] = A[i], A[0]
        A.heap_size = A.heap_size - 1
        min_heapify(A, 0)  # max_min instead of heapify_heapify
    return A

quick_sort_nonincreasing.py

def partition_nonincreasing(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] >= x:  #Reorientation of inequalities
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

def quickSort_nonincreasing(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = partition_nonincreasing(A, p, r)  #Call the nonincreasing version
        quickSort_nonincreasing(A, p, q - 1)  #Same as above
        quickSort_nonincreasing(A, q + 1, r)  #Same as above
    return A