La clasificación en tiempo lineal y el programa para el conde Ordenar en Kotlin

En este artículo, vamos a aprender cómo implementar Contar Ordenar en Kotlin? Aquí encontrará su algoritmo y el programa en Kotlin.

Hasta ahora hemos estudiado los algoritmos de ordenación que tienen O (nlogn) (Merge, montón, más o menos rápida) tiempo de O (n2) Tiempo (burbuja, inserción, ordenación por selección). Todos estos fueron comparación especie pero hay algunos otros algoritmos de clasificación que utilizan operaciones distintas de comparación para determinar el orden de clasificación y pueden ordenar los elementos en tiempo O (n), es decir en el tiempo lineal.

Los algoritmos de ordenación que puede ordenar los elementos en tiempo lineal son,

  1. Conde tipo
  2. cubo especie
  3. Radix sort

En este artículo, se discute acerca recuento tipo .

Leer más: contando especie (explicación, ejemplo y un programa en C ++)

Aquí están algunas suposiciones antes de usar conteo tipo ,

  1. no debería haber ningún número negativo.
  2. Todos los elementos están en el orden de 0 a max (elemento max de la lista) y max = O (n)

Algoritmo

	COUNTING_SORT(A,max)
1. Let C[0..max] be a new array
2. Let B[0..A.length] be a new array
3. for i=0 to max
4. C[A[i]] = C[A[i]] + 1
5. for i=1..C.length- 1
6. C[i] = C[i] + C[i– 1]
7. for i=A.length downTo 0
8. B[C[A[i] ]] = A[i]
9. C[A[i] ] = C[A[i] ] - 1
10. Print B[ ] as sorted array

fuente Algoritmo de Introducción a los algoritmos por CLRC

Complejidad -> O (n)

conteo Programa class especie en Kotlin

fun counting_sort(A: Array<Int>, max: Int) {
// Array in which result will store
var B = Array<Int>(A.size, { 0 })
// count array
var C = Array<Int>(max, { 0 })
for (i in 0..A.size - 1) {
//count the no. of occurrence of a
//particular element store in count array
C[A[i] - 1] = C[A[i] - 1] + 1
}
for (i in 1..C.size - 1) {
// calculate commutative sum
C[i] = C[i] + C[i - 1]
}
for (i in A.size - 1 downTo 0) {
// place the element at its position
B[C[A[i] - 1] - 1] = A[i]
// decrease the occurrence of the element by 1
C[A[i] - 1] = C[A[i] - 1] - 1
}
println("After sorting :")
for (i in B) {
print("$i ")
}
}
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()
// calculate maximum element from array
var max = A[0];
for (i in A) {
if (i > max) {
max = i
}
}
counting_sort(A, max)
}

salida

Enter no. of elements :10
Enter elements :
5
4
3
7
9
4
3
5
7
1
After sorting :
1 3 3 4 4 5 5 7 7 9


Deja un comentario

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