Jump to content
Paul4games

QuickSort infinite loop?

By Paul4games, in Programare

Recommended Posts

Paul4games Newbie

Paul4games

Posted
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?

M2G Apprentice

M2G

Posted
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;		  

}

TheTime Newbie

TheTime

Posted
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.

×
Go to topic listing
×
×
  • Create New...