Quicksort com Lista encadeada

[Henrique Cipriano]

Olá galera. Estou elaborando um algoritmo de QuickLista, no qual é otimizado o Quicksort para Listas encadeadas. Embora seja mais custoso do que o uso de vetores, necessito fazer dessa forma.

Se possível, analisem o código, está ocorrendo uma falha de segmentação, o qual aparentemente ocorre na função partition, quando o nó é removido.

##

#include <stdio.h>

#include <stdlib.h>

typedef struct NODE {

int valor;

struct NODE *proximo;

struct NODE *anterior;

}node;

typedef struct{

node *raiz;

}lista;

node *newNode(int);

void addNode(lista*, node*);

void rmNode(lista*, node*);

lista *newLista();

void printLista(lista*);

void partition(lista*,lista*,lista*);

void quicksort(lista*);

int main(int argc, char **argv){

int i = 1;

lista *l = newLista();

/*while(i < argc){

addNode(l, newNode(atoi(argv)));

i++;

}*/

addNode(l, newNode(5));

addNode(l, newNode(8));

addNode(l, newNode(1));

addNode(l, newNode(3));

addNode(l, newNode(9));

printLista(l);

quicksort(l);

printLista(l);

return 0;

}

node *newNode(int v){

node *n = (node*)malloc(sizeof(node));

n->valor = v;

n->anterior = NULL;

n->proximo = NULL;

return n;

}

void addNode(lista *l, node *n){

node *r = l->raiz;

if(r == NULL){

l->raiz = n;

}else{

while(r->proximo != NULL){

r = r->proximo;

}

r->proximo = n;

n->anterior = r;

}

}

void rmNode(lista *l, node *n){

node *a, *b;

if(n == l->raiz){

l->raiz = n->proximo;

}else{

a = n->anterior;

b = n->proximo;

a->proximo = b;

if(b != NULL){

b->anterior = a;

}

}

n->anterior = NULL;

n->proximo = NULL;

}

lista *newLista(){

lista *l = (lista*)malloc(sizeof(lista));

l->raiz = NULL;

return l;

}

void printLista(lista *l){

node *r = l->raiz;

while(r != NULL){

printf("%d ", r->valor);

r = r->proximo;

}

printf("\n");

}

void partition(lista *A,lista *B,lista *C){

node *n = A->raiz, *aux;

int pivot;

if(n != NULL){

aux = n->proximo;

pivot = n->valor;

while(n != NULL){

printf("pt\n");

rmNode(A, n);

if(n->valor < pivot){

addNode(A, n);

printf("menor\n");

}

if(n->valor == pivot){

addNode(B, n);

printf("igual\n");

}

if(n->valor > pivot){

addNode(C, n);

printf("maior\n");

}

}

}

}

void quicksort(lista* A){

printf("a\n");

node *a = A->raiz;

lista *B = newLista(), *C = newLista();

if(a->proximo != NULL){

printf("a\n");

partition(A, B, C);

printf("b\n");

quicksort(A);

quicksort©;

addNode(A, B->raiz);

addNode(B, C->raiz);

}

}

[Jhonas]

veja se ajuda

http://www.ime.usp.br/~pf/algoritmos/aulas/quick.html

abraço