Hỏi về thuật toán sắp xếp trên linked list

[sytay]

Làm phiền anh chị chỉ giúp em thuật toán sắp xêp inssertionsort và qicksort cho linkedlist.thanks

[Gio (Gió)]

Insert sort thì làm như trên wiki. Quicksort thì phải dùng 2 list phụ:

function quicksort(list a)
   if size(a)<2: return
   list lower,upper;
   pivot =head(a);
   for each elem in a do
       if elem<pivot: append(lower,elem)
       if elem>=pivot: append(upper,elem)
   end
   quicksort(lower)
   quicksort(upper)
   concat(lower,upper)
end

[sytay]

Ai có thể chỉ kĩ hơn cho e được k.vì e mới học nên còn lơ mơ lắm

[Gio (Gió)]

Code quick sort voi linkedlist

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


typedef struct node node;

struct node{
    int value;
    node * next;
};

typedef struct list list;

struct list{
    node * head, *last;
};

list * make_list(){
    list * L=(list *)malloc(sizeof(list));
    L->head=L->last=NULL;
    return L;
}

node * make_node(int value){
    node * n=(node *)malloc(sizeof (node));
    assert(n);
    n->value=value;
    n->next=NULL;
    return n;
}
node * append(list * L, int value){ // them vao cuoi danh sach, tra ve node dc tao thanh
    
    node * newNode=make_node(value);
    if(L->head==NULL){
        L->head=L->last=newNode;
    }else{
        L->last->next=newNode;
        L->last=newNode;
    }
    return newNode;
}

void * free_list(list * L){
    node *p=L->head;
    while(p){
        node * t=p->next;
        free(p);
        p=t;
    }
    L->head=L->last=NULL;
}

void print_list(list *L){
    node *p=L->head;
    while(p){
        printf("%d -> ",p->value);
        p=p->next;
    }
    printf("\n");
}

void quick_sort(list *L){
    if(!L->head || !L->head->next){
        return;
    }
    list * lower=make_list();
    list * upper=make_list();
    int pivot=L->head->value;
    node *p;
    
    for(p=L->head->next; p!=NULL; p=p->next){
        if(p->value>=pivot){
            append(upper,p->value);
        }else{
            append(lower,p->value);
        }
    }
    quick_sort(lower);
    append(lower,pivot);
    quick_sort(upper);
    lower->last->next=upper->head;
    lower->last=upper->last;
    free_list(L);
    L->head=lower->head;
    L->last=lower->last;
}
int main() {
    list *L=make_list();
    append(L, 1);
    append(L,3);
    append(L,2);
    append(L,5);
    append(L,4);
    puts("# before quick sort:");
    print_list(L);
    
    quick_sort(L);
    puts("# after quick sort: ");
    print_list(L);
    return 0;
}

###ouput

# before quick sort:
1 -> 3 -> 2 -> 5 -> 4 -> 
# after quick sort: 
1 -> 2 -> 3 -> 4 -> 5 -> 

quick sort 10^5 phan tu [0,10000)

int main() {
    list *L=make_list();
    int n=100000;
    int i;
    srand(time(NULL));
    for(i=0;i<n;i++){
        append(L,random()%10000);
    }
    quick_sort(L);
    return 0;
}

time ~ 0.19s

[sytay]

Cảm ơn bạn mình đã hiểu.