Programa para el tipo de inserción en Kotlin

En este artículo, vamos a aprender cómo implementar un tipo de inserción en Kotlin ? A continuación, se dará cuenta de lo que es una especie de inserción, su algoritmo, programa con la explicación?

La ordenación por inserción es un algoritmo de ordenación en la que mantenemos una matriz ordenada en el principio de la lista y una lista sin ordenar de forma simultánea. Elegimos un elemento de una matriz no seleccionada y la colocamos en la secuencia ordenada de elementos a su posición correcta. Repetimos el mismo paso hasta que toda la matriz en solucionarse.

Algoritmo

    INSERTION-SORT(A)
1. for j = 1 to A.length
2. key = A[j]
3. i = j-1
4. while i> 0 and A[i] > key
5. A[i+1]=A[i]
6. I = i-1
7. A[i+1] = key

fuente algoritmo de Introducción a los algoritmos 3ª edición por Cormen .

Este algoritmo toma tiempo O (n2), en el peor class. Sin embargo, en el mejor case, lo hace sólo una comparación en cada fase. La mejor case es si la matriz ya está ordenada. Este es el mejor case una situación en la que una serie está casi ordenadas o el tamaño del problema es pequeño.

Programa

fun insertion_sort(A: Array<Int>) {
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 main(arg: Array<String>) {
print("Enter no. of elements :")
var n = readLine()!!.toInt()
println("Enter elements : ")
var A = Array(n, { 0 })
for (i in 0 until n)
A[i] = readLine()!!.toInt()
insertion_sort(A)
println("Sorted array is : ")
for (i in 0 until n)
print("${A[i]} ")
}

salida

Enter no. of elements :5
Enter elements :
22
12
33
32
11
Sorted array is :
11 12 22 32 33


Deja un comentario

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