Skip to content

Instantly share code, notes, and snippets.

@clausecker
Created May 10, 2017 11:27
Show Gist options
  • Save clausecker/77e42dadea6f2c05d532d1871e340a51 to your computer and use it in GitHub Desktop.
Save clausecker/77e42dadea6f2c05d532d1871e340a51 to your computer and use it in GitHub Desktop.
Bubblesort on singly linked lists
/* bubble sort a linked list */
#include <stdio.h>
#include <stdlib.h>
static struct list *scan_list(void);
static void sort_list(struct list **);
static void print_list(struct list *);
static void free_list(struct list *);
struct list {
struct list *next;
int elem;
};
int main()
{
struct list *l = scan_list();
sort_list(&l);
print_list(l);
free_list(l);
}
static struct list *
scan_list(void)
{
struct list *l = NULL, **cell = &l;
int val;
while (scanf("%d", &val) == 1) {
*cell = malloc(sizeof **cell);
if (*cell == NULL) {
perror("malloc");
exit(EXIT_FAILURE);
}
(*cell)->next = NULL;
(*cell)->elem = val;
cell = &(*cell)->next;
}
return (l);
}
static void
print_list(struct list *l)
{
while (l != NULL) {
printf("%d\n", l->elem);
l = l->next;
}
}
static void
free_list(struct list *l)
{
struct list *ll;
while (l != NULL) {
ll = l->next;
free(l);
l = ll;
}
}
/* sort list using bubble sort */
static void
sort_list(struct list **l)
{
int swap;
struct list **i, *a, *b;
do {
swap = 0;
for (i = l; *i != NULL && (*i)->next != NULL; i = &(*i)->next)
if ((*i)->elem > (*i)->next->elem) {
swap = 1;
a = *i;
b = (*i)->next;
a->next = b->next;
b->next = a;
*i = b;
}
} while (swap);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment