Jump to content
Paul4games

QuickSort infinite loop?

Recommended Posts

Posted

Am scris algoritmul de quicksort in delphi dar am o problema, la un moment dat intra intr-un loop infinit si nu inteleg de ce(am until (i<=j) iar la acel moment i=26 iar j=24 deci nu vad cum ar putea fi mai mica).Codul este urmatorul:


program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils;

procedure QuickSort(V: array of integer; left,right: integer);
var
i,j,mid,aux: integer;
begin
i:= left;
j:= right;
mid:= V[(left+right) div 2];
repeat begin
while (V[i]<mid) do Inc(i);
while (V[j]>mid) do Dec(j);
if(i<=j) then begin
aux:= V[i];
V[i]:= V[j];
V[j]:= aux;
Inc(i);
Dec(j);
end;
end;
until (i<=j);
if (j>left) then QuickSort(V, left, j)
else if (i<right) then QuickSort(V, i, right);
end;

var
i: integer;
v: array[1..100] of integer;
begin
for i:= 100 downto 1 do V[i]:=i;
QuickSort(V, 1, 100);
for i:= 1 to 100 do WriteLn(V[i]);
end.

Are cineva vreo idee de ce intra in acel loop infinit?

Posted

Ai aici un program in C pe care l-am scris anul trecut. Sunt implementati algoritmii bubble, insertion, selection si quick sort.

Faci o paralela cu ce vezi aici si cu algoritmul tau. Nu sunt in dispozitia necesara sa ma uit peste cod si sa fac analize ca sunt unpic nervos. :)

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int v[10000],n,stanga=0,dreapta,a=0,c=0;


void afisare(int v[],int n){
int i;
printf("Vectorul sortat este: ");
for (i=0;i<n;i++){
printf("%d < ",v[i]);
}
}

void bubble_sort(int v[],int n){
int i,j,aux;

for (i=0;i<n-1;i++){
for(j=0;j<n-1;j++){

c++;

if (v[j]>v[j+1]){
aux=v[j];
v[j]=v[j+1];
v[j+1]=aux;
a+=3;
}
}
}

}
void ins_sort(int v[],int n){
int i,j,aux;
for (i=1;i<n;i++){
aux=v[i];
j=i-1;
c++;
while ((j>=0) && (v[j]>aux))
{
c++;
v[j+1]=v[j];
j--;
}
v[j+1]=aux;
a+=3;
}

}

void selectie(int v[], int n){

int i,j,min,aux,imin;
for(i=0;i<n-1;i++){
min=v[i];
imin=i;
c++;
for(j=i+1;j<n;j++) {
c++;
if (v[j]<min]){
min=v[j];
imin=j;
}
}
aux=v[i];
v[i]=v[imin];
v[imin]=aux;
a+=3;

}

}

void quickSort(int v[], int stanga, int dreapta) {

int i = stanga, j = dreapta;
int aux;
int pivot = v[(stanga + dreapta) / 2];
c++;

/* partitie */

while (i <= j) {
while (v[i] < pivot)
i++;
c++;
while (v[j] > pivot)
j--;
c++;
if (i <= j) {
aux = v[i];
v[i] = v[j];
v[j] = aux;

a+=3;

i++;
j--;

}
}

/* recursivitate */

if (stanga < j)
quickSort(v, stanga, j);
if (i < dreapta)
quickSort(v, i, dreapta);

}

void average(int v[], int n) {
int i;
for(i=0; i<n; i++) {
v[i] = rand();
}
}

void best_case(int v[], int n){
int i;
for (i=0;i<n;i++){
v[i]=i;
}
}

void worst_case(int v[], int n){
int i;
for (i=1;i<n+1;i++){
v[i]=n-i;
}
}

void visual(int n){

switch (n){
case 1000: printf("*");break;
case 2000: printf("*");break;
case 3000: printf("*");break;
case 4000: printf("*");break;
case 5000: printf("*");break;
case 5500: printf("*");break;
case 6000: printf("*");break;
case 6500: printf("*");break;
case 7000: printf("*");break;
case 7500: printf("*");break;
case 8000: printf("*");break;
case 8500: printf("*");break;
case 9000: printf("*");break;
case 9500: printf("*");break;
case 10000: printf("*");break;
}

}

int main()
{
FILE *f;
//bubble sort
//bubble average
f = fopen("bubble_average.csv", "w");
printf("Bubble Sort -- Average:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){
visual(n);
average(v,n);
a=0;c=0;
bubble_sort(v,n);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f);printf("| [Done]\n\n");
//bubble best
f = fopen("bubble_best.csv", "w");
printf("Bubble Sort -- Best case:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
best_case(v,n);
bubble_sort(v,n);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");
//bubble worst
f = fopen("bubble_worst.csv", "w");
printf("Bubble Sort -- Worst case:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
worst_case(v,n);
bubble_sort(v,n);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");
//insertion sort
//insertion worst
f = fopen("insertion_worst.csv", "w");
printf("<=================================================================>\n\n");
printf("Insertion Sort -- Worst case:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
worst_case(v,n);
ins_sort(v,n);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");
//insertion best
f = fopen("insertion_best.csv", "w");
printf("Insertion Sort -- Best case:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
best_case(v,n);
ins_sort(v,n);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");
//insertion average
f = fopen("insertion_average.csv", "w");
printf("Insertion Sort -- Average:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
average(v,n);
ins_sort(v,n);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");

//selection sort
//selection worst
f = fopen("selection_worst.csv", "w");
printf("<=================================================================>\n\n");
printf("Selection Sort -- Worst case:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
worst_case(v,n);
selectie(v,n);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");
//selection best
f = fopen("selection_best.csv", "w");
printf("Selectionn Sort -- Best case:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
best_case(v,n);
selectie(v,n);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");
//selection average
f = fopen("selection_average.csv", "w");
printf("Selection Sort -- Average:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
average(v,n);
selectie(v,n);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");

//quick sort
//quick worst
f = fopen("quick_worst.csv", "w");
printf("<=================================================================>\n\n");
printf("Quick Sort -- Worst case:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
worst_case(v,n);
dreapta=n-1;
quickSort(v,stanga, dreapta);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");
//quick best
f = fopen("quick_best.csv", "w");
printf("Quick Sort -- Best case:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
best_case(v,n);
dreapta=n-1;
quickSort(v,stanga, dreapta);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");
//quick average
f = fopen("quick_average.csv", "w");
printf("Quick Sort -- Average:\n");
printf("Algorithm progress |");
for(n=100;n<=10000;n+=100){ visual(n);
a=0;c=0;
average(v,n);
dreapta=n-1;
quickSort(v,stanga, dreapta);
fprintf(f, "%d,%d,%d\n", a, c, a+c);

} fclose(f); printf("| [Done]\n\n");

printf("<----+++-----Finish----+++----->\n");
printf("Press any key to exit...");
getch();
return 0;

}

Posted

if(i<=j) then begin
aux:= V[i];
V[i]:= V[j];
V[j]:= aux;
Inc(i);
Dec(j);
end;

Nu cunosc limbajul, dar cred ca if-ul nu se executa niciodata. Asa cred ca ar trebui sa fie:

if(V[i]<=V[j]) then begin
aux:= V[i];
V[i]:= V[j];
V[j]:= aux;
Inc(i);
Dec(j);
end;

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...