Быстрая сортировка в едином списке

Question

Я пытаюсь написать просто C-код для QUICKSORT в одном связанном списке. Программа получит текстовый файл с паролем и частотой использования этого пароля. Программа должна отсортировать пароли по порядку. Может кто-нибудь сказать мне, как написать функцию void qsort_list, потому что я не понимаю, как получить 3 параметра, которые нужны "partiition()".

#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;
}

Answer 1

Общая идея алгоритма быстрой сортировки связанного списка:

1 - Чтобы выбрать поворотную клавишу, в вашем случае вы выбираете последнюю клавишу в списке.

2 - Разделить список элементов на 2 подсписка: один с элементами = pivot (или>). Вы называете этот список влево и вправо.

3 - Заказать левый и правый списки. Это рекурсивная часть: вы используете быструю сортировку для упорядочения каждого подсписка, если список не пустой или с одним элементом.

4 - объединить элементы левого и правого списков.

Таким образом, ваш список qsort_list должен быть примерно таким:

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);
}

Заметки:

• Я изменил pivot на pivotKey, вам просто нужно знать ключ, чтобы разделить список. Это может быть даже несуществующий ключ (например, среднее значение между первым и последним)
• Исходя из сказанного, вы должны создать функцию разделения, не забудьте обновить исходный список, когда вы берете из него элементы и вставляете их в один подсписок. Ваш оригинальный список будет пустым после раздела. Кроме того, вы можете подумать о том, как просто удалить более крупные элементы, чтобы ваш оригинальный список заменил левый список.
• Вы должны реализовать функцию join, которая вставляет все элементы left и right (в этом порядке) в mylist. Вам не нужно перемещать элементы один за другим, просто манипулируйте первым и последним указателями.