Quicksort on Single Linked list

Question

I'm trying to write a simply C code for QUICKSORT on single linked list. Program will get a txt file with password and frequency of usage this password. Program should sort the passwords in order. Can some one tell me how to write function void qsort_list because I don't understand how to get 3 parameters that "partiition()" need.

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


typedef struct list_element{
char passwort[100];
int haufigkeit;
struct list_element *next;
} list_element;

typedef struct list{ list;


void init_list(list* mylist)
{
mylist->first=NULL;
mylist->last=NULL;
}


void insert_front(list_element* le, list* mylist)
{
// HIER Code einfügen

if(mylist->first == NULL){
le->next = mylist-> first;
mylist->first=le;
mylist->last=le;
}
else {
le->next = mylist-> first;
mylist->first= le;
}
}

// Speicher für Listenelemente wieder freigeben
void free_list(list* mylist)
{
// HIER Code einfügen
}


// Namen, Zahlen Paare in Liste einlesen
void read_data(char* filename, list* mylist)
{
assert(mylist != NULL);
FILE* f=fopen(filename,"rb");
assert(f != NULL);
while (1)
{

list_element* temp = malloc(siezof(list_element))// * Speicher allozieren
fscanf(f,"%s %d",temp->passwort, &temp-> haufigkeit)// * Daten in list_element einlesen
insert_front(temp, mylist) // * insert_front benutzen um list_element in Liste einzufügen

}
fclose(f);
}

// Pivot finden, das die Liste aufteilt
list_element* partition( list* input, list* left, list* right )
{
list_element* pivot= list->last;
input= mylist;
while(mylist->first != mylist->last)
{
// HIER Code einfügen
list_element* list_right = list* right;
list_element* list_left = list* left;
list_element *i;
for(i=list->first; i != NULL; i=i->next){
if ((i -> haufigkeit) < (pivot -> haufigkeit)){
insert_front(i, list_left);
}
else{
insert_front(i,list_right);
}
}
}

}
return pivot;
}

/*
void partition1(){
    list* pivot= list->last;
}return pivot;
}
*/

void qsort_list(list* mylist)
{
list left = mylist;
list first;  //  = list mylist->first:
list pivot= list* last; 

partition(list* left, list* first, list* pivot);
pivot = 


}

// Liste ausgeben
void print_list(list* mylist)
{
// HIER Code einfügen:

}

// Argumente einlesen, Liste kreieren, verarbeiten und ausgeben
int main(int argc, char** args)
{
if (argc != 2)
{
printf("Nutzung: %s <Dateiname>\n",args[0]);
return 1;
}
list mylist;
init_list(&mylist);
read_data(args[1],&mylist);
qsort_list(&mylist);
printf("Sortierte Liste:\n");
print_list(&mylist);
free_list(&mylist);
return 0;
}

Quicksort relies on indexable search which lists don't provide. I'm not convinced that quick sort on a linked list makes sense. — Jonathan Leffler, Dec 12 '14 at 00:08
Linked list is not a structure that lends itself to quicksort. See this question for alternatives http://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list — hatchet - done with SOverflow, Dec 12 '14 at 00:10
This may help http://stackoverflow.com/questions/9368076/quick-sort-on-a-linked-list-with-a-random-pivot-in-c?rq=1 — hatchet - done with SOverflow, Dec 12 '14 at 00:18
A singly linked list can't be easily quicksorted, because you need to traverse in both directions (not just forward). — Ken White, Dec 12 '14 at 01:45
In fact you can QuickSort a linked list very easily. The classic QS need to traverse in both directions because it operate in the same memory array, but linked lists can be splitted in a different way. Please read my answer below. — Will, Dec 13 '14 at 02:17

score 2 · Answer 1 · answered Dec 13 '14 at 02:10

The general idea of the quicksort algorithm over a linked list is:

1 - To choice a pivot key, in your case you are choosing the last key in the list.

2 - To split the list of elements in 2 sublist: one with elements < pivot (or <=) and the other with elements >= pivot (or >). You are calling this list left and right.

3 - To order the left and right lists. This is the recursive part: you use quicksort to order each sublist, unless the list is empty or with one element.

4 - To concatenate the elements of left and right lists.

So your qsort_list must be something like:

void qsort_list(list* mylist) {
    list left,right;
    int pivotKey= mylist->last->haufigkeit;
    /* stop condition: mylist empty or with 1 element*/
    if( (mylist->first == 0) || (mylist->first == mylist->last) )
        return;
    init_list(left);
    init_list(right);
    partition(mylist, &left, &right, pivotKey);
    /* recursive part: */
    qsort_list(&left);
    qsort_list(&right);
    join(mylist, &left, &right);
}

Notes:

I changed pivot to pivotKey, you just need to know the key to split the list. It may even be a non-existing key (eg. the average between the first one and the last one)
Based on the said, you must create your partition function, remember to update the original list as you take elements from it and insert them in one sublist. Your original list will be empty after the partition. Alternatively, you can think on a way to just remove the greater elements so your original list will replace the left list.
You must implement the join function, that insert all the elements of left and right (in that order) in mylist. You does not need to move the elements one by one, just manipulate the first and last pointers.

Quicksort on Single Linked list

1 Answers1

Linked