Salve a tutti. Sto cercando di implementare un algoritmo di quicksort iterativo in C++, alla compilazione tutto ok, ma purtroppo quando lo eseguo credo che si avvii un ciclo infinito in quanto si blocca tutto, ma non riesco proprio a trovare il problema. Il codice è il seguente:
Stack.cpp
codice:
//definizione di elem
typedef struct elem{
int data;
struct elem *next;
}elem;
typedef struct elem elem;
//definizione di stack
struct stack{
int cnt;
elem *top;
};
typedef struct stack stack;
//definizione delle funzioni
void init(stack *stk){
//SCOPO: Inizializza un'istanza vuota dello stack.
stk->top = NULL;
stk->cnt = 0;
}
bool isempty(stack *stk){
//SCOPO: Restituisce TRUE se lo stack è vuoto, FALSE altrimenti.
if(stk->cnt == 0){
return true;
}else{
return false;
}
}
void push(stack *stk, int d){
//SCOPO: Inserisce un elemento nello stack.
elem *nodo;
nodo = new elem;
nodo->data = d;
if(isempty(stk)){
stk->top = nodo;
}else{
nodo->next = stk->top;
stk->top = nodo;
}
stk->cnt++;
}
int pop(stack *stk){
//SCOPO: Restituisce l'elemento in cima allo stack, -1 se è vuoto.
int d;
if(!isempty(stk)){
d = stk->top->data;
delete(stk->top);
stk->top = stk->top->next;
stk->cnt--;
}else{
d = -1;
}
return d;
}
Partiziona.cpp
codice:
void partiziona(int a[], int left, int right, int middle, int &p){
/*SCOPO:
Partiziona l'array da left a right rispetto a middle.
In OUTPUT restituisce la posizione di middle dopo l'operazione di partizione.*/
int i = left;
int j = right;
int t;
int x = a[middle];
while(a[i] <= x && i<j)
i++;
while(a[j] > x && i<j)
j--;
if(a[j] > x)
j--;
while(i < j){
t = a[i];
a[i] = a[j];
a[j] = t;
i++;
j--;
while(a[i] <= x)
i++;
while(a[j] > x)
j--;
}
p = j;
}
quicksort.cpp
codice:
#include "stack.cpp"
#include "partiziona.cpp"
void quicksort(int a[], int n){
/*SCOPO:
Ordina l'array in input usando il metodo di Hoare*/
int right, left, middle, p;
stack *head;
head = new stack;
init(head);
push(head, 0);
push(head, n);
while(!isempty(head)){
right = pop(head);
left = pop(head);
while(left < right){
middle = (right + left)/2;
partiziona(a, left, right, middle, p);
//esamino prima la partizione di dimensione minore, salvo quindi i limiti di quella maggiore.
if(p <= middle){
if(p + 1 < right){
push(head, p + 1);
push(head, right);
}
right = p;
}else{
if(p > left){
push(head, left);
push(head, p);
}
left = p + 1;
}
}
}
}
main.cpp
codice:
#include "quicksort.h"
main(){
//dichiarazione variabili
int a[MAX];
int n;
//richiesta dimensione dell'array
do{
cout<<"Inserisci la dimensione del vettore desiderata (max "<<MAX<<")"<<endl;
cin>>n;
}while(n > MAX);
//assegnazione dei valori all'array
for(int i = 0; i < n; i++){
cout<<"Inserisci il valore per la posizione "<<i<<endl;
cin>>a[i];
}
//mostro l'array prima dell'ordinamento
cout<<"L'array è il seguente:"<<endl;
for(int i = 0; i < n; i++){
cout<<"|"<<a[i];
}
cout<<"|"<<endl;
//chiamata funzione per l'ordinamento
quicksort(a, n - 1);
//rimostro l'array ordinato
cout<<"L'array dopo l'ordinamento è il seguente:"<<endl;
for(int i = 0; i < n; i++){
cout<<"|"<<a[i];
}
cout<<"|"<<endl;
}