Necesito ayuda con Heapsort
Publicado por Rodrigo (1 intervención) el 02/11/2014 18:32:05
Hola gente.
Como tarea he estado haciendo el algoritmo de ordenamiento heapsort, implementado en Java que me permita ordenar un arreglo, el problema que estoy teniendo es que se vuelve inestable cuando el arreglo tiene al menos 1 elemento repetido, cuando ocurre eso, el arreglo no se ordena como se debe, pero sin embargo, mi programa funciona de maravillas cuando el arreglo no tiene numeros repetidos, por lo que se ordena de menor a mayor.
Para este programa, decidí que el primer elementro del arreglo fuera el índice 1, y no el 0.
Dejo mi código, está documentado y explica lo que hace cada parte. Ojalá me puedan ayudar, ya que me provoca problemas con números repetidos. Estaría bien agradecido si me dieran una mano porfavor.
Mi programa crea un arreglo de 15 números (tamaño 16), de manera aleatoria.
Saludos.
Como tarea he estado haciendo el algoritmo de ordenamiento heapsort, implementado en Java que me permita ordenar un arreglo, el problema que estoy teniendo es que se vuelve inestable cuando el arreglo tiene al menos 1 elemento repetido, cuando ocurre eso, el arreglo no se ordena como se debe, pero sin embargo, mi programa funciona de maravillas cuando el arreglo no tiene numeros repetidos, por lo que se ordena de menor a mayor.
Para este programa, decidí que el primer elementro del arreglo fuera el índice 1, y no el 0.
Dejo mi código, está documentado y explica lo que hace cada parte. Ojalá me puedan ayudar, ya que me provoca problemas con números repetidos. Estaría bien agradecido si me dieran una mano porfavor.
Mi programa crea un arreglo de 15 números (tamaño 16), de manera aleatoria.
Saludos.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package ordenamiento7;
public class Ordenamiento7 { /**
* Método que permite crear un heap ordinario a max heap.
* @param a El arreglo a ordenar.
* @param i El índice actual en el arreglo.
* @param n Tamaño del arreglo.
*/public static void heapify(int[] a, int i, int n){
if(i <= n/2){ //Sí el nodo no es una hoja.
if((2*i+1) <= n){ //Sí el nodo tiene 2 hijos.
if((a[i] < a[2*i]) || (a[i] < a[2*i+1])){ //Si el padre tiene un hijo mayor.
if(a[2*i] > a[2*i+1]){ //Si el hijo izquierdo es mayor, se intercambia con el padre.
int num = a[i];
a[i] = a[2*i];
a[2*i] = num;
heapify(a,2*i,n); //Se vuelve a restablecer el maxheap.
}else{ //De lo contrario.
if(a[2*i+1] > a[2*i]){ //Si el hijo derecho es mayor, se intercambia con el padre.
int num = a[i];
a[i] = a[2*i+1];
a[2*i+1] = num;
heapify(a,2*i+1,n); //Se vuelve a restablecer el maxheap
} } }}else{ //De lo contrario.
if(((2*i+1) > n) && (2*i == n)){ //El nodo tiene 1 solo hijo.
if(a[i] < a[2*i]){ //Si el hijo es mayor, se intercambiar con el padre.
int num = a[i];
a[i] = a[2*i];
a[2*i] = num;
} } } } } /**
* Método que permitir construir un heap.
* @param a El arreglo inicialmente.
* @param n Tamaño del arreglo
*/public static void buildheap(int[]a, int n){
for(int i=n/2; i>=1; i--){
heapify(a,i,n);
} } /**
* Método que permite ordenar el heap.
* @param a El arreglo desordenado.
* @param n Tamaño del arreglo.
*/public static void heapsort(int[]a, int n){
buildheap(a,n);
int dim = n;for(int i=n; i>1; i--){
int num = a[1];
a[1] = a[i];
a[i] = num;
dim = dim - 1;
heapify(a,1,dim);
} }public static void desplegar(int[]a, int n){
System.out.println("\n\n");
for(int i=1; i<=n; i++){
System.out.print(a[i] + "\t");
} }public static void main(String[] args) {
//int[]a = {0,4,1,3,2,16,9,10,14,8,7};
int[]a = new int[16];
for(int i=1; i<=15; i++){
a[i] = (int)(Math.random()*99 + 1);
}desplegar(a,15); //Antes
heapsort(a,15);
desplegar(a,15); //Despues
}}Valora esta pregunta
-1