QuickSort

19 de maio de 2012 9 respostas

danielcaminhas 19 de maio de 2012

Implementacao do QuickSort:

Olá pessoal, estou tentando implementar o QuickSort em C, mas estou tendo alguns problemas. O código esta abaixo, o compilador não gera nenhuma mensagem de erro, mas após algum tempo de execução (já era esperado que a ordenação fosse levar alguns minutos/horas) o programa gera um exceção e é encerrado.
*a esta apontando para o vetor de tamanho variável que foi alocado dinamicamente usando malloc. Alguem tem alguma ideia do que possa estar acontecendo?
Desde já, obrigado.
Obs: O código não foi totalmente escrito por mim, fui juntando vários outros que achei pela internet e ?traduzindo? códigos de outras linguagens ate chegar nesse ai, mas não achei nada de errado com ele.

void swap(int *a, int x, int y) {
	int temp = a[x];
	a[x] = a[y];
	a[y] = temp;
}

int partition(int *a, int f, int l) {
	int pivo = a[f];
	while (f < l) {

		while (a[f] < pivo) {
			f++;
		}
		while (a[l] > pivo) {
			l--;
		}
		swap(a, f, l);
	}
	return f;
}

void quicksort(int *a, int l, int r) {
	if (r > l) {
    int pivotIndex = partition(a, l, r);
	quicksort(a, l, pivotIndex-1);
	quicksort(a, pivotIndex + 1, r);
}
}

9 Respostas

KamikazeBr 20 de mai. de 2012

Antes de mais nada, na linha 08, voce trata “a” como se fosse array?

danielcaminhas 20 de mai. de 2012

Na verdade nao.
a[f] aponta para a j-ezima posiçao de memória após a primeira posicçao apontada por a, lembrando que será levado a consideraçao o tamanho da estrutura que está sendo alocada, no caso números inteiros.

A ideia é a mesma de:

int main()
{
   int *a; 
   a = (int*) malloc(sizeof(int)*10); 
   
   for(int i = 0; i < 10; i++)
   a[i] = i; 
   
   printf("%d", a[3]);
   
   free(a); 
   
   return 0;    
}

Neste caso a[i] nao é uma posiçao no vetor, mas sim uma posiçao de memória.

KamikazeBr 20 de mai. de 2012

Ah desculpe a ignorancia ^^

Não estou executando seu código e não havia entendido sobre o malloc onde você havia comentado.

Mas…sendo posição de memoria ou não é um “vetor” certo? Se sim, na linha 11 e 12 não há uma possibilidade de estourar?

Suponhamos que “a” tem um limite de 10 posicões, e a ultima posição ainda é menor que sua variavel “pivo”, ela irá incrementar f++ acima do limite de “a”, estourando, certo?

danielcaminhas 20 de mai. de 2012

Que isso... eu que agradeço a sua disposição para responder.
Então.. o programa só vai entrar no looping da linha 11 se a condição de looping da linha 9 for atendida. Observe que para que o índice de a seja incrementado, este índice deve ser menor que o parâmetro L, que inicialmente é o tamanho do ?vetor? menos uma unidade. Se em um dado momento f for incrementado e se igualar ao (tamanho do ?vetor? ? 1), o looping externo será encerrado, e portando f não será mais incrementado e nem L será decrementado. O que impede que haja vazamento.
Ficou um pouco confuso porque eu não postei onde as funções estavam sendo chamadas na main (esqueci deste detalhe :P). Vou postar a main ai acho que vai ficar mais fácil de entender.

int main() {
	int *a;
	int n = 100000; //variar o valor de n até que ocorra estouro de memoria e observar os efeitos no tempo de ordencao

	time_t start, end;
	double dif = 0;

	a = (int*) malloc(sizeof(int) * n);

	if(!a)
	printf("Erro na alocacao de memoria");

	for (int i = 0; i < n; i++) {
		//vet[i] = rand();  //caso medio
		a[i] = (n - i); //pior caso
		//vet[i] = i; //melhor caso
	}

	start = time(NULL);
	quicksort(a, 0, n - 1);

	end = time(NULL);
	dif = difftime(end, start);
	printf("\nTempo de ordencao: %lf", dif);
	scanf("%d", &n);

	free(a);

	return 0;

}

KamikazeBr 20 de mai. de 2012

O loop externo não será encerrado…enquanto está dentro de outro loop.

Exemplo basico:

while( b==true){
       while(c<10){
              c++
              if (c==5){
                     b=false;
              }
       }
}
print c;//c =10 e não 5

danielcaminhas 20 de mai. de 2012

É verdade… não tinha me atentado para isso. Obrigado pela resposta. Eu mudei a função para que o looping não aconteça se f<=l (o que impede o vazamento de memoria). Percebi também que os parametros da funçao partition estavam trocados em relaçao a funçao QuickSort. Mas ainda assim o problema persiste. Entao além do que você citou e do que eu mudei ainda tem mais alguma coisa errada que eu nao estou conseguindo encontrar.
obs: troquei a variavel f por uma r(right) só para dar mais legibilidade.

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *a, int x, int y);
int partition(int *a, int f, int l);
void quicksort(int *a, int f, int l);

int main() {
	int *a;
	int n = 100000;

	time_t start, end;
	double dif = 0;

	a = (int*) malloc(sizeof(int) * n);

	if(!a)
	printf("Erro na alocacao de memoria");

	srand(time(NULL));

	for (int i = 0; i < n; i++) {
		//vet[i] = rand();  //caso medio
		a[i] = (n - i); //pior caso
		//vet[i] = i; //melhor caso
	}

	start = time(NULL);
	quicksort(a, 1, n - 1);

	end = time(NULL);
	dif = difftime(end, start);
	printf("\nTempo de ordencao: %lf", dif);
	scanf("%d", &n);

	free(a);

	return 0;

}

void swap(int *a, int x, int y) {
	int temp = a[x];
	a[x] = a[y];
	a[y] = temp;
}

int partition(int *a, int l, int r) {
	int pivo = a[l];
	while (l < l) {

		while (a[l] < pivo && l <=l) {
			l++;
		}
		while (a[r] > pivo) {
			r--;
		}
		swap(a, l, r);
	}
	return r;
}

void quicksort(int *a, int l, int r) {
	//if (r > l) {
    int pivotIndex = partition(a, l, r);
	quicksort(a, l, pivotIndex-1);
	quicksort(a, pivotIndex + 1, r);
    //}
}

danielcaminhas 20 de mai. de 2012

Ops… já vi que o while da linha 53 estava errado. Consertei mas também nao mudou nada.

while (l < r) {
...
}

KamikazeBr 20 de mai. de 2012

danielcaminhas:

É verdade... não tinha me atentado para isso. Obrigado pela resposta. Eu mudei a função para que o looping não aconteça se f<=l (o que impede o vazamento de memoria). Percebi também que os parametros da funçao partition estavam trocados em relaçao a funçao QuickSort. Mas ainda assim o problema persiste. Entao além do que você citou e do que eu mudei ainda tem mais alguma coisa errada que eu nao estou conseguindo encontrar. obs: troquei a variavel f por uma r(right) só para dar mais legibilidade.

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *a, int x, int y);
int partition(int *a, int f, int l);
void quicksort(int *a, int f, int l);

int main() {
	int *a;
	int n = 100000;

	time_t start, end;
	double dif = 0;

	a = (int*) malloc(sizeof(int) * n);

	if(!a)
	printf("Erro na alocacao de memoria");

	srand(time(NULL));

	for (int i = 0; i < n; i++) {
		//vet[i] = rand();  //caso medio
		a[i] = (n - i); //pior caso
		//vet[i] = i; //melhor caso
	}

	start = time(NULL);
	quicksort(a, 1, n - 1);

	end = time(NULL);
	dif = difftime(end, start);
	printf("\nTempo de ordencao: %lf", dif);
	scanf("%d", &n);

	free(a);

	return 0;

}

void swap(int *a, int x, int y) {
	int temp = a[x];
	a[x] = a[y];
	a[y] = temp;
}

int partition(int *a, int l, int r) {
	int pivo = a[l];
	while (l < l) {

		while (a[l] < pivo && l <=l) {
			l++;
		}
		while (a[r] > pivo) {
			r--;
		}
		swap(a, l, r);
	}
	return r;
}

void quicksort(int *a, int l, int r) {
	//if (r > l) {
    int pivotIndex = partition(a, l, r);
	quicksort(a, l, pivotIndex-1);
	quicksort(a, pivotIndex + 1, r);
    //}
}

"r" vai ser -1 e estourar?? na linha 55?
l<=l está correto tambem?

danielcaminhas 20 de mai. de 2012

KamikazeBr:

danielcaminhas:

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *a, int x, int y);
int partition(int *a, int f, int l);
void quicksort(int *a, int f, int l);

int main() {
	int *a;
	int n = 100000;

	time_t start, end;
	double dif = 0;

	a = (int*) malloc(sizeof(int) * n);

	if(!a)
	printf("Erro na alocacao de memoria");

	srand(time(NULL));

	for (int i = 0; i < n; i++) {
		//vet[i] = rand();  //caso medio
		a[i] = (n - i); //pior caso
		//vet[i] = i; //melhor caso
	}

	start = time(NULL);
	quicksort(a, 1, n - 1);

	end = time(NULL);
	dif = difftime(end, start);
	printf("\nTempo de ordencao: %lf", dif);
	scanf("%d", &n);

	free(a);

	return 0;

}

void swap(int *a, int x, int y) {
	int temp = a[x];
	a[x] = a[y];
	a[y] = temp;
}

int partition(int *a, int l, int r) {
	int pivo = a[l];
	while (l < l) {

		while (a[l] < pivo && l <=l) {
			l++;
		}
		while (a[r] > pivo) {
			r--;
		}
		swap(a, l, r);
	}
	return r;
}

void quicksort(int *a, int l, int r) {
	//if (r > l) {
    int pivotIndex = partition(a, l, r);
	quicksort(a, l, pivotIndex-1);
	quicksort(a, pivotIndex + 1, r);
    //}
}

"r" vai ser -1 e estourar?? na linha 55?
l<=l está correto tambem?

Na verdade isso também estava errado. Já mudei lá, mas do mesmo jeito o programa não termina a ordenação. Começo a achar que o problema nao esta no código, rodei o programa em outro sistema operacional e ele funcionou corretamente, mas no Windows, usando o code::blocks, qualquer outro programa executa, menos este. :(

int partition(int *a, int l, int r) {
	int pivo = a[l];
	while (l < r) {

		while (a[l] < pivo && l <=r) {
			l++;
		}
		while (a[r] > pivo) {
			r--;
		}
		swap(a, l, r);
	}
	return r;
}

Criado 19 de maio de 2012

Ultima resposta 20 de mai. de 2012

Respostas 9

Participantes 2

9 Respostas

Topicos relacionados