“Bowl of seasoned pistachios and nuts for a salty snack” by Whitney Wright on Unsplash

6. Sorting 2

6. 6. Heap Sort — O(NlogN)

No additional array required.

(1) Make the array you want to sort on Heap. (Heapify) — O(N)
The subtree rooted at the first node, not the leaf node, performs a Heapify operation.

func buildMaxHeap(_ n:Int){
    for i in (1...(n/2)).reversed(){
        maxHeapify(i, n)
    }
}

(2) In the heap, change the maximum value (root node) to the last value.
(3) The size of the heap is assumed to be reduced by one. That is, the last value is not considered part of the heap.
(4) Heapify (1) for the root node.
(5) Repeat steps 2 to 4.

func heapSort(_ n:Int){
    buildMaxHeap(n)
    for i in (1...n).reversed(){
        let temp = data[1]
        data[1] = data[i]
        data[i] = temp
        maxHeapify(1,i-1)
    }
}

6. 7. Radix Sort

Default assumption: number of values ​​are n and d-digit integers.

We sort from the last digit. Each digit is sorted by a stable sorting (counting sort, bucket sort) algorithm.

func radixSort(_ array: inout [Int] ) {
    let radix = 10  //Here we define our radix to be 10
    var done = false
    var index: Int
    var digit = 1  //Which digit are we on?
  
    while !done {  //While our  sorting is not completed
        done = true  //Assume it is done for now
        var buckets: [[Int]] = []  
        //Our sorting subroutine is bucket sort, 
        //so let us predefine our buckets
    
        for _ in 1...radix {
            buckets.append([])
        }
        for number in array {
            index = number / digit  //Which bucket will we access?
            buckets[index % radix].append(number)
            
            if done && index > 0 {  
            //If we arent done, continue to finish, 
            //otherwise we are done
            done = false
            }
        }
        var i = 0
        for j in 0..<radix {
            let bucket = buckets[j]
            for number in bucket {
                array[i] = number
                i += 1
            }
        }
        digit *= radix  //Move to the next digit
    }
}