Programa para el ordenamiento por mezcla en Kotlin

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

Combinar tipo es un algoritmo de clasificación que utiliza el enfoque divide y vencerás. En este enfoque, el problema se divide en subproblemas más pequeños similares al problema original . Entonces resolverlos de forma recursiva, y luego combinar los resultados para encontrar la solución al problema original. Combinar especie es más rápido algoritmo de ordenación por inserción o la selección tipo que hemos aprendido en los artículos anteriores.

Algoritmos

    MERGE_SORT(A,p,r)
1. if(p<r)
2. q=(p+r)/2
3. merge_sort(A,p,q)
4. merge_sort(A,q+1,r)
5. merge(A,p,q,r)
MERGE(A,p,q,r)
1. n1 = q-p+1
2. n2 = r-q
3. create array L[0..n1] and R[0..n2]
4. fori = 0 to n1)
5. L[i]=A[p+i]
6. for j = 0 to n2)
7. R[j]=A[q+j]
8. i=0
9. j=0
10. for k = p to r
11. if(L[i]<=R[j])
12. A[k]=L[i]
13. i=i+1
14. else
15. A[k]=R[j]
16. j=j+1

fuente Algoritmo de Introducción a los algoritmos por Cormen

Este algoritmo toma O (n log (n)) tiempo. En esto, la matriz no seleccionados se divide en subconjuntos de tamaño más pequeño (hasta cada submatriz de tamaño de uno), entonces cada subconjunto es uno ordenados por uno, y luego fusionar los subconjuntos para conseguir requieren un arreglo ordenado. Este es un algoritmo de ordenación estable, pero no en su lugar, ya que requiere espacios n adicionales.

programa para implementar ordenamiento por mezcla en Kotlin

fun merge(A: Array<Int>, p: Int, q: Int, r: Int) {
var left = A.copyOfRange(p, q + 1)
var right = A.copyOfRange(q + 1, r + 1)
var i = 0
var j = 0
for (k in p..r) {
if ((i <= left.size - 1) && ((j >= right.size) || (left[i] <= right[j]))) {
A[k] = left[i];
i++;
} else {
A[k] = right[j];
j++;
}
}
}
fun merge_sort(A: Array<Int>, p: Int, r: Int) {
if (p < r) {
var q = (p + r) / 2
merge_sort(A, p, q)
merge_sort(A, q + 1, r)
merge(A, p, q, r)
}
}
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()
merge_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 :
23
45
65
23
21
Sorted array is :
21 23 23 45 65


Deja un comentario

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