Ordered Array Algorithm
The Ordered Array Algorithm refers to a data structure where elements are maintained in a sorted manner at all times. This algorithm is most commonly used in searching and insertion operations, where the elements in the array are kept sorted either in ascending or descending order. The primary advantage of using an ordered array is that it simplifies searching for specific elements, as binary search can be employed, which has a significantly faster runtime complexity of O(log(n)) compared to linear search's O(n) complexity. This makes ordered arrays particularly attractive for applications where searching is a frequent and critical operation.
However, this advantage comes with a trade-off in terms of insertion and deletion operations. When inserting a new element into an ordered array, the algorithm needs to find the correct position for the new element to maintain the sorted order, which can take up to O(n) time in the worst case. Similarly, deletion of an element may also require shifting the remaining elements to fill the gap, leading to a time complexity of O(n) in the worst case. Despite its not-so-optimal performance in insertion and deletion operations, the ordered array algorithm is still a valuable choice in scenarios where search operations are dominant and the data set is relatively static, benefiting from reduced search times and simplicity in implementation.
/**
* Created by gazollajunior on 02/04/16.
*/
class OrderedArray<T:Comparable<T>>(list:MutableList<T>){
var items: MutableList<T> = this.quicksort(list) as MutableList<T>
/**
* Use quicksort algorithm to order elements in array
*/
fun quicksort(its:List<T>):List<T>{
if (its.count() < 1) return its
val pivot = its[its.count()/2]
val equal = its.filter { it == pivot }
val less = its.filter { it < pivot }
val greater = its.filter { it > pivot }
return quicksort(less) + equal + quicksort(greater)
}
fun insert(element:T){
val position = findElementPosition(element)
this.items.add(position, element)
}
/**
* Use binarySearch algorithm to find the position for the new element in array
*/
fun findElementPosition(element:T):Int{
var rangeStart = 0
var rangeEnd = this.items.count()
while (rangeStart < rangeEnd) {
val midIndex = rangeStart + (rangeEnd - rangeStart)/2
if (this.items[midIndex] == element) {
return midIndex
} else if (this.items[midIndex] < element){
rangeStart = midIndex + 1
} else {
rangeEnd = midIndex
}
}
return rangeStart
}
override fun toString():String = this.items.toString()
}
fun main(args: Array<String>) {
println("\nOriginal list:")
val names = listOf<String>("Tim", "Steve", "Zack", "Adam", "John", "Peter", "Clark") as MutableList<String>
println(names)
println("\nOrdered list:")
val ordered = OrderedArray<String>(names)
println(ordered)
val n1 = "Paul"
println("\nAdding ${n1} to the list:")
ordered.insert(n1)
println(ordered)
val n2 = "Demetrius"
println("\nAdding ${n2} to the list:")
ordered.insert(n2)
println(ordered)
}
