Tree sort
A Binary Sort is inspired by a Binary Search and the Binary Tree Sort. A binary search is used to insert each element of an unsorted array into the newly formed sorted array. The difference between a Binary Sort and a Tree Sort is that a tree is reconstructed after each element of the unsorted array is added to the sorted array.
Example
var array: [Int] array = [9,10,7,6,11, 4,3,2,1,7,8,9,0,5,7,5,5,12,32,43,56,23,545,23,45,12,45,23,11,80,2,1] let sortedArray = binarySort(array) print(sortedArray)
func binarySort(array: [Int] ) -> [Int] {
var sortedArray = [0]
for i in 0...(array.count - 1) {
print("\(sortedArray) \(array[i]) \(sortedArray.count - 1)")
let position = findInsertPosition(sortedArray, number: array[i], upperBound: (sortedArray.count - 1), lowerBound: 0)
sortedArray.insert(array[i], atIndex: position)
}
sortedArray.removeFirst()
return sortedArray
}
func findInsertPosition(sortedArray: [Int], number: Int, upperBound: Int, lowerBound: Int) -> Int {
let currentPosition = (upperBound - lowerBound) / 2 + lowerBound
if number >= sortedArray[currentPosition] {
if (upperBound == lowerBound) {
return (currentPosition + 1)
} else {
let newUpperBound = upperBound
let newLowerBound = currentPosition + 1
return findInsertPosition(sortedArray, number: number,upperBound: newUpperBound, lowerBound: newLowerBound)
}
} else {
if (upperBound == lowerBound) {
return (currentPosition)
} else {
let newUpperBound = currentPosition
let newLowerBound = lowerBound
return findInsertPosition(sortedArray, number: number,upperBound: newUpperBound, lowerBound: newLowerBound)
}
}
}
See also
External links
The Wikibook Algorithm Implementation has a page on the topic of: Binary Tree Sort