Programa ejecuta a medias
Publicado por A3434 (1 intervención) el 19/05/2021 05:43:09
Hola buenas, el código ejecuta un QuickSelect modificado, donde n es el número de elementos de un arreglo cualquiera y k representa los k números menores a buscar, que posteriormente se almacena en un arreglo B, el problema que tengo que es lo ejecuta correctamente (hace la función) para valores de n y k pequeños ,pero cuando les pongo valores como 100 000 para n y 50 000 para k el código ejecuta por unos momentos y luego se detiene, puse unos cout para ver el valor del pivote (p) y me di cuenta que se forman ciclos ej: 590 1100 1500 y luego el k decrece de uno en uno, hasta que de a poco el p se iguala con el k, cuando los números son grandes esos ciclos también lo son, y el k decrece lentamente hasta que de cierta forma el programa dice "basta" y termina la ejecución, y bueno, llevo un par de días pero no logro entender que lo hace fallar concretamente...
Ej de ejecución:
A[2, 4, 6, 1, 7, 9] -> arreglo aleatorio; n=6
B[k celdas] ->almacena k menores; si k=2 y se ejecuta el quickSelect => B[1, 2]
Ej de ejecución:
A[2, 4, 6, 1, 7, 9] -> arreglo aleatorio; n=6
B[k celdas] ->almacena k menores; si k=2 y se ejecuta el quickSelect => B[1, 2]
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
#include <bits/stdc++.h>
using namespace std;
int partition(int *a,int l, int r){
int piv=a[l];
int p=l;for (int i=l+1;i<=r;i++){
if(a[i]<=piv){
p=p+1;
swap(a[i],a[p]);
} }swap(a[l],a[p]);
return p;
}int quickSelect(int *A,int *B,int l, int r, int k){
if((l>=r) && (k==0)){
B[k]=A[l];
cout<<"QuickSelect exitoso."<<endl;
return 0; //finaliza }int p=partition(A,l,r);
//cout<<"p : "<<p<<" k : "<<k<<endl;if (k==p+1){
B[p]=A[p];
return quickSelect(A,B,0,p-1,k-1);
}if (k<p+1){
//cout<<"p< : "<<p<<" k : "<<k<<endl;return quickSelect(A,B,l,p-1,k); //se busca igualar el pivote+1 con k
} //cout<<"p> : "<<p<<" k : "<<k<<endl;return quickSelect(A,B,p+1,r,k);
}void imprimeArr(int *A,int n){
cout<<endl;
for (int i=0;i<n;i++){
cout<<A[i]<<" ";
}cout<<endl;
}void matrizRandom(int *A,int n){
for (int i=0;i<n;i++){
A[i]=rand() % (50)+1;
//cout<<A[i]<<" "; }cout<<"Matriz aleatoria creada."<<endl;
}int main(){
int k = 50000;int *masPeque = new int[k];
int n=100000;int *arrayToSearch= new int[n];
matrizRandom(arrayToSearch,n);
quickSelect(arrayToSearch,masPeque,0,n-1,k);
cout<<endl;
imprimeArr(masPeque,k);
cout<<endl;
return 0;
}Valora esta pregunta
0