Programa de Cubo Ordenar en Kotlin

En este artículo, vamos a aprender cómo implementar cubo especie en Kotlin ? A continuación, se dará cuenta de lo que es una especie de cubo, su algoritmo y el programa en Kotlin.

algoritmo Bucket tipo ordena los elementos que se distribuyen de manera uniforme. Al igual que en el conteo de clase, se supone que la entrada elementsarein pequeña gama , aquí suponemos que los elementos se distribuyen de manera uniforme sobre el intervalo [0,1] por lo que ambos son rápidos. Ambos tienen poca idea sobre la entrada que van a proceso.

Bucket distribuye Ordenar los elementos en los cubos y luego por separado especie cada cubo mediante la ordenación por inserción. Puesto que los elementos se distribuyen de manera uniforme por lo que no muchos elementos caerían en cada cubo. Así que simplemente ordenar cada cubo y luego combinarlas para producir el resultado.

Fuente de la imagen: Introducción a los algoritmos, libro de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, y Clifford Stein (CLRC)

Asumir Si los elementos no están distribuidos de manera uniforme a continuación, todos los elementos pueden caer en un solo cubo y luego Si especie usando ordenación por inserción, entonces esto puede tomar hasta O (n2) tiempo como de costumbre por la ordenación por inserción. No habría ningún sentido de la utilización de cubo tipo.

Aquí están algunas suposiciones antes de usar Bucket Ordena,

  1. elementos están en el rango [0,1) // no incluyendo 1.
  2. Los elementos se distribuyen de manera uniforme en todo el rango.

Algoritmo

	    BUCKET_SORT(A)
1. let B[0..n-1] be a new array
2. for I = 0 to n-1
3. make B[i] an empty list
4. for i=1 to n
5. insert a[i] into b[floor(n*a[i])]
6. for I = 0 to n-1
7. sort b[i] using insertion sort
8. concatenate list b[0],b[1]…b[n-1] together in order
//Algorithm source from Introduction to Algorithms by CLRC

Complejidad O (n + k)

fun insertion_sort(A: ArrayList<Double>) {
var n = A.size
var i: Int
for (j in 1 until n) {
var key = A[j]
i = j - 1
while (i >= 0 && A[i] > key) {
A[i + 1] = A[i]
i--
}
A[i + 1] = key
}
}
fun bucket_sort(A:Array<Double>){
var n=A.size
var bucket = Array<ArrayList<Double>>(n,{i-> ArrayList() }) // creating buckets with n size
for(i in 0..A.size-1){
bucket[Math.floor(n*A[i]).toInt()].add(A[i]) // adding element a[i] into position n*a[i]
}
for(i in 0..A.size-1){
insertion_sort(bucket[i]) // sorting a list using inserton sort
}
for (i in 1..A.size-1){
bucket[0].addAll(bucket[i]) // concatenate all the buckets
}
println("After sorting :")
for (i in bucket[0])
{
print("$i ") // print the sorted elements
}
}
fun main(arg: Array<String>) {
print("Enter no. of elements :")
var n = readLine()!!.toInt()
println("Enter elements : ")
var A = Array(n, { 0.0 })
for (i in 0 until n)
A[i] = readLine()!!.toDouble()
bucket_sort(A)
}

salida

Enter no. of elements :10
Enter elements :
0.32
0.43
0.53
0.56
0.87
0.98
0.76
0.68
0.57
0.28
After sorting :
0.28 0.32 0.43 0.53 0.56 0.57 0.68 0.76 0.87 0.98


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *