Ans :
Quick Sorting Integer Array - Explanation
Merge Sorting Integer Array - Explanation
Heap Sorting Integer Array - Explanation
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)
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]
