QuickSort infinite loop?

Paul4games · March 1, 2012

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?

Starker · March 1, 2012

Il poti scrie te rog in limbaj C++ pentru MinGW? Te-as putea ajuta, dar asa nu mai stiu.

M2G · March 1, 2012

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;		  

}

TheTime · March 1, 2012

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;

Paul4games · March 1, 2012

Am gasit problema era din cauza ca in delphi repeat...until la until vine conditia negata si eu puneam conditia normala.....deci ca sa mearga in log de until (i<=j) vine until (i>=j).

Sign In

QuickSort infinite loop?

Recommended Posts

Paul4games

Link to comment

Share on other sites

Starker

Link to comment

Share on other sites

M2G

Link to comment

Share on other sites

TheTime

Link to comment

Share on other sites

Paul4games

Link to comment

Share on other sites

Join the conversation

Browse

Activity

Pages