Write a program for sorting array. Quick sort, merge sort, Heap Sort

Ans : 

Quick Sorting Integer Array - Explanation

func swap<T: Comparable>(leftValue: inout T, rightValue: inout T) {

    (leftValue, rightValue) = (rightValue, leftValue)

}

func partition<T: Comparable>(array: inout [T], startIndex: Int, endIndex: Int) -> Int {

    var q = startIndex

    for index in startIndex..<endIndex {

        if array[index] < array[endIndex] {

            swap(leftValue: &array[q], rightValue: &array[index])

            q += 1

        }

    }

    swap(leftValue: &array[q], rightValue: &array[endIndex])

    return q

}

func quickSort<T: Comparable>(array: inout [T], startIndex: Int, endIndex: Int) {

    // Base case

    if startIndex >= endIndex {

        return

    }

    let placedItemIndex = partition(array: &array, startIndex: startIndex, endIndex: endIndex)

    quickSort(array: &array, startIndex: startIndex, endIndex: placedItemIndex-1)

    quickSort(array: &array, startIndex: placedItemIndex+1, endIndex: endIndex)

}

func quickSort<T: Comparable>(array: inout [T]) {

    quickSort(array: &array, startIndex: 0, endIndex: array.count-1)

}

var numbers = [13, 77, 20, 45, 2, 15, 0, 59, 5, 68, 51, 1, -1, 77]

quickSort(array: &numbers)

Merge Sorting Integer Array - Explanation

func merge<T: Comparable> (array: inout [T], startIndex: Int, middleIndex: Int, endIndex: Int) {

    let leftSubarray = Array(array[startIndex...middleIndex])

    let rightSubarray = Array(array[middleIndex+1...endIndex])

    var index = startIndex

    var leftIndex = 0

    var rightIndex = 0

    while leftIndex < leftSubarray.count && rightIndex < rightSubarray.count {

        if leftSubarray[leftIndex] < rightSubarray[rightIndex] {

            array[index] = leftSubarray[leftIndex]

            leftIndex += 1

        }

        else {

            array[index] = rightSubarray[rightIndex]

            rightIndex += 1

        }

        index += 1

    }

    while leftIndex < leftSubarray.count {

        array[index] = leftSubarray[leftIndex]

        index += 1

        leftIndex += 1

    }

    while rightIndex < rightSubarray.count {

        array[index] = rightSubarray[rightIndex]

        index += 1

        rightIndex += 1

    }

}

func mergeSort<T: Comparable>(array: inout [T], startIndex: Int, endIndex: Int) {

    // Base case

    if startIndex >= endIndex {

        return

    }

    let middleIndex = (startIndex + endIndex) / 2

    mergeSort(array: &array, startIndex: startIndex, endIndex: middleIndex)

    mergeSort(array: &array, startIndex: middleIndex+1, endIndex: endIndex)

    merge(array: &array, startIndex: startIndex, middleIndex: middleIndex, endIndex: endIndex)

}

func mergeSort<T: Comparable>(array: inout [T]) {

    mergeSort(array: &array, startIndex: 0, endIndex: array.count-1)

}

var numbers = [13, 77, 20, 45, 2, 15, 0, 59, 5, 68, 51, 1, -1, 77]

mergeSort(array: &numbers)

Heap Sorting Integer Array - Explanation

extension Heap {

    public mutating func sort() -> [T] {

        for i in stride(from: (nodes.count - 1), through: 1, by: -1) {

            nodes.swapAt(0, i)

            shiftDown(from: 0, until: i)

        }

        return nodes

    }

}

/*

 Sorts an array using a heap.

 Heapsort can be performed in-place, but it is not a stable sort.

 */

public func heapsort<T>(_ a: [T], _ sort: @escaping (T, T) -> Bool) -> [T] {

    let reverseOrder = { i1, i2 in sort(i2, i1) }

    var h = Heap(array: a, sort: reverseOrder)

    return h.sort()

}

//Testing

func testSort() {

    var h1 = Heap(array: [5, 13, 2, 25, 7, 17, 20, 8, 4], sort: >)

    let a1 = h1.sort()

}

// output : [2, 4, 5, 7, 8, 13, 17, 20, 25]