Skip to content

Instantly share code, notes, and snippets.

@dnmfarrell
Last active October 22, 2020 02:17
Show Gist options
  • Save dnmfarrell/554fd9a5b7194cf50d8de65633a18b79 to your computer and use it in GitHub Desktop.
Save dnmfarrell/554fd9a5b7194cf50d8de65633a18b79 to your computer and use it in GitHub Desktop.
quicksort on a linked list "gcc -o qsort qsort.c"
#include <stdio.h>
#include <stdlib.h>
typedef struct List {
int n;
void *next;
} List;
List* ListNew (int n) {
List *l = malloc(sizeof(List));
l->next = NULL;
l->n = n;
return l;
}
List* ListAdd (List *l, int n) {
List *ln = ListNew(n);
ln->next = l;
return ln;
}
void ListPrint (List *l) {
if (l->next) {
printf("%d,",l->n);
ListPrint(l->next);
} else {
printf("%d\n", l->n);
}
}
List* ListLessThan (List *l, int n) {
List *nl = NULL;
while (1) {
if (l->n < n) {
nl = nl ? ListAdd(nl, l->n) : ListNew(l->n);
}
l = l->next;
if (!l) break;
}
return nl;
}
List* ListGreaterEqual (List *l, int n) {
List *nl = NULL;
while (1) {
if (l->n >= n) {
nl = nl ? ListAdd(nl, l->n) : ListNew(l->n);
}
l = l->next;
if (!l) break;
}
return nl;
}
List* ListConcat (List *h, List *t) {
List *temp = h;
while (1) {
if (temp->next) {
temp = temp->next;
} else {
temp->next = t;
break;
}
}
return h;
}
List* qsort (List *l) {
if (!l->next) return l;
List *temp;
List *lt = ListLessThan(l->next, l->n);
List *ge = ListGreaterEqual(l->next, l->n);
l->next = NULL;
if (lt) {
temp = ListConcat(qsort(lt), l);
} else {
temp = l;
}
if (ge)
temp = ListConcat(temp, qsort(ge));
return temp;
}
int main () {
List *l1 = ListNew(5);
List *l2 = ListAdd(l1, 5);
List *l3 = ListAdd(l2, 4);
List *l4 = ListAdd(l3, 3);
List *l5 = ListAdd(l4, -1);
List *l6 = ListAdd(l5, 2);
List *l7 = ListAdd(l6, 1);
List *l8 = ListAdd(l7, 1);
ListPrint(l8);
ListPrint(qsort(l8));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment