Selection sort [linked list]

#include
#include

#define MAX 10

struct lnode {
 int data;
 struct lnode *next;
} *head, *visit;

/* add a new entry to the linked list */
void llist_add(struct lnode **q, int num);
/* preform a selection sort on the linked list */
void llist_selection_sort(void);
/* print the entire linked list */
void llist_print(void);

int main(void) {
 /* linked list */
 struct lnode *newnode = NULL;
 int i = 0; /* a general counter */

 /* load some random values into the linked list */
 for(i = 0; i < MAX; i++) {
  llist_add(&newnode, (rand() % 100));
 }

 head = newnode;
 printf("Before selection sort:\n");
 llist_print();
 printf("After  selection sort:\n");
 llist_selection_sort();
 llist_print();

 return 0;
}

/* adds a node at the end of a linked list */
void llist_add(struct lnode **q, int num) {
 struct lnode *temp;

 temp = *q;

 /* if the list is empty, create first node */
 if(*q == NULL) {
  *q = malloc(sizeof(struct lnode));
   temp = *q;
 } else {
  /* go to last node */
  while(temp->next != NULL)
   temp = temp->next;

   /* add node at the end */
   temp->next = malloc(sizeof(struct lnode));
   temp = temp->next;
 }

 /* assign data to the last node */
 temp->data = num;
 temp->next = NULL;
}

/* print the entire linked list */
void llist_print(void) {
 visit = head;

 /* traverse the entire linked list */
 while(visit != NULL) {
  printf("%d ", visit->data);
  visit = visit->next;
 }
 printf("\n");
}

void llist_selection_sort(void) {
 struct lnode *a = NULL;
 struct lnode *b = NULL;
 struct lnode *c = NULL;
 struct lnode *d = NULL;
 struct lnode *tmp = NULL;

 a = c = head;
 while(a->next != NULL) {
  d = b = a->next;
  while(b != NULL) {
   if(a->data > b->data) {
    /* neighboring linked list node */
    if(a->next == b) {
     if(a == head) {
      a->next = b->next;
      b->next = a;
      tmp = a;
      a = b;
      b = tmp;
      head = a;
      c = a;
      d = b;
      b = b->next;
     } else {
      a->next = b->next;
      b->next = a;
      c->next = b;
      tmp = a;
      a = b;
      b = tmp;
      d = b;
      b = b->next;
     }
    } else {
     if(a == head) {
      tmp = b->next;
      b->next = a->next;
      a->next = tmp;
      d->next = a;
      tmp = a;
      a = b;
      b = tmp;
      d = b;
      b = b->next;
      head = a;
    } else {
     tmp = b->next;
     b->next = a->next;
     a->next = tmp;
     c->next = b;
     d->next = a;
     tmp = a;
     a = b;
     b = tmp;
     d = b;
     b = b->next;
    }
   }
  } else {
   d = b;
   b = b->next;
  }
 }
  c = a;
  a = a->next;
 }
}

Qsort [string, dynamic pointer array]

#include
#include
#include

void sortstrarr(void *array, unsigned n);
static int cmpr(const void *a, const void *b);

int main (void) {
 char **strarray = NULL;
 int i = 0, strcount = 0;
 char line[1024];

 while((fgets(line, 1024, stdin)) != NULL) {
  if(strlen(line) == 1)
   continue;

  strarray = (char **)realloc(strarray, (strcount + 1) * sizeof(char *));
  strarray[strcount++] = strdup(line);
 }
                
 printf("### Before ###\n");
 for(i = 0; i < strcount; i++)
  printf("%2d: %s", i, strarray[i]);

 sortstrarr(strarray, strcount);

 printf("### After ###\n");
 for(i = 0; i < strcount; i++)
  printf("%2d: %s", i, strarray[i]);

 /* free mem... */
 for(i = 0; i < strcount; i++)
  free(strarray[i]);

 free(strarray);
 return 0;
}

static int cmpr(const void *a, const void *b) {
 return strcmp(*(char **)a, *(char **)b);
}

void sortstrarr(void *array, unsigned n) {
 qsort(array, n, sizeof(char *), cmpr);
}

Qsort [string array]

#include
#include
#include

void sortstrarr(void *array, unsigned n);
static int cmpr(const void *a, const void *b);

int main(void) {
 char line[1024];
 char *line_array[1024];
 int i = 0;
 int j = 0;

 while((fgets(line, 1024, stdin)) != NULL)
  if(i < 1024)
   line_array[i++] = strdup(line);
  else
   break;

 sortstrarr(line_array, i);

 while(j < i)
  printf("%s", line_array[j++]);

 return 0;
}

static int cmpr(const void *a, const void *b) {
 return strcmp(*(char **)a, *(char **)b);
}

void sortstrarr(void *array, unsigned n) {
 qsort(array, n, sizeof(char *), cmpr);
}

Qsort [array of pointers to structures]

#include
#include
#include

struct node {
 char *str;
};

/* compare function for qsort */
static int cmpr(const void *a, const void *b);

int main(void) {
 struct node **strarray = NULL;
 int i = 0, count = 0;
 char line[1024];

 while(fgets(line, 1024, stdin) != NULL) {
  /* add ONE element to the array */
  strarray = (struct node **)realloc(strarray, (count + 1) * sizeof(struct node *));

  /* allocate memory for ONE `struct node` */
  strarray[count] = (struct node *)malloc(sizeof(struct node));

  /* copy the data into the new element (structure) */
  strarray[count]->str = strdup(line);
  count++;
 }

 /* before sorting ... */
 printf("Before:\n");
 for(i = 0; i < count; i++) {
  printf("[%d]->str: %s", i, strarray[i]->str);
 }

 /* qsort array of structures */
 qsort(strarray, count, sizeof(*strarray), cmpr);

 /* after sorting ... */
 printf("\n--\nAfter:\n");
 for(i = 0; i < count; i++) {
  printf("[%d]->str: %s", i, strarray[i]->str);
 }

 /* free all strarray elements */
 for(i = 0; i < count; i++) {
  free(strarray[i]->str);
  free(strarray[i]);
  i++;
 }
 free(strarray);
 
 return 0;
}

/* compare function for qsort */
static int cmpr(const void *a, const void *b) {
 struct node * const *one = a;
 struct node * const *two = b;

 return strcmp((*one)->str, (*two)->str);
}

Qcksort, quick sort [array]

#include

#define MAXARRAY 10

void quicksort(int arr[], int low, int high);

int main(void) {
 int array[MAXARRAY] = {0};
 int i = 0;

 /* load some random values into the array */
 for(i = 0; i < MAXARRAY; i++)
  array[i] = rand() % 100;

 /* print the original array */
 printf("Before quicksort: ");
 for(i = 0; i < MAXARRAY; i++) {
  printf(" %d ", array[i]);
 }
 printf("\n");

 quicksort(array, 0, (MAXARRAY - 1));

 /* print the `quicksorted' array */
 printf("After  quicksort: ");
 for(i = 0; i < MAXARRAY; i++) {
  printf(" %d ", array[i]);
 }
 printf("\n");

 return 0;
}

/* sort everything inbetween `low' <-> `high' */
void quicksort(int arr[], int low, int high) {
 int i = low;
 int j = high;
 int y = 0;
 /* compare value */
 int z = arr[(low + high) / 2];

 /* partition */
 do {
  /* find member above ... */
  while(arr[i] < z) i++;

  /* find element below ... */
  while(arr[j] > z) j--;

  if(i <= j) {
   /* swap two elements */
   y = arr[i];
   arr[i] = arr[j];
   arr[j] = y;
   i++;
   j--;
  }
 } while(i <= j);

 /* recurse */
 if(low < j)
  quicksort(arr, low, j);

 if(i < high)
  quicksort(arr, i, high);
}