Programa para la ordenación rápida en Kotlin

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

Quicksort es un algoritmo de clasificación que utiliza Divide y enfoque Conquer como Merge Ordenar . Su class tiempo de funcionamiento más desfavorable es O (n2) , pero lo mejor de un tiempo medio de funcionamiento es O (n log (n)) . Es un lugar en la clasificación .

Aquí es la de tres pasos de divide y vencerás proceso case ordenar una submatriz típico A [p ..R] .

Divide: partición la matriz A [pág.R] en dos submatrices A [pág.Q-1] y A [q + 1..r] tal manera que cada elemento de a [pág.Q-1] es menor que o igual a a [q] , que es, a su vez, menor que o igual a cada elemento de a [q + 1..r] . Entonces calcular el índice q como parte de este procedimiento de partición.

Conquer: Ordenar las dos submatrices A [pág.Q-1] y A [q + 1..r] por llamadas recursivas a QuickSort.

Combinar: Debido a que las submatrices ya están ordenados, no hay necesidad de combinarlos, toda la matriz A [p ..R] está ahora ordenadas.

Algoritmos

    QUICK_SORT(A,p,r)
1. if(p<r)
2. q=partition(A,p,r)
3. quick_sort(A,p,q-1)
4. quick_sort(A,q+1,r)
PARTITION(A,p,r)
1. x= A[r]
2. I =p-1
3. for j=p to r-1
4. if A[j]<=x
5. i=i +i
6. exchange a[i] with a[j]
7. exchange a[i+1] with a[r]
8. return i+1

fuente algoritmo de Introducción a los algoritmos por Cormen

programa para implementar la ordenación rápida en Kotlin

fun quick_sort(A: Array<Int>, p: Int, r: Int) {
if (p < r) {
var q: Int = partition(A, p, r)
quick_sort(A, p, q - 1)
quick_sort(A, q + 1, r)
}
}
fun partition(A: Array<Int>, p: Int, r: Int): Int {
var x = A[r]
var i = p - 1
for (j in p until r) {
if (A[j] <= x) {
i++
exchange(A, i, j)
}
}
exchange(A, i + 1, r)
return i + 1
}
fun exchange(A: Array<Int>, i: Int, j: Int) {
var temp = A[i]
A[i] = A[j]
A[j] = temp
}
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()
quick_sort(A, 0, A.size - 1)
println("Sorted array is : ")
for (i in 0 until n)
print("${A[i]} ")
}

salida

Enter no. of elements :5
Enter elements :
10
34
22
56
74
Sorted array is :
10 22 34 56 74

Leer más: La aplicación de la ordenación rápida en C ++


Deja un comentario

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