void selSortLL(NodeT *head) { // selection sort on a linked list NodeT *marker; for (marker=head; marker!=NULL; marker=marker->next) { NodeT *min = marker; // assume element 'marker' is minimum NodeT *rest; for (rest=marker->next; rest!=NULL; rest=rest->next) { if (rest->data < min->data) { min = rest; // found a better min at location 'rest' } } if (marker != min) { // swap data inside marker and min nodes int temp = marker->data; marker->data = min->data; min->data = temp; } } } |
NodeT *insSortLL(NodeT *head) { // insertion sort on a linked list if (head != NULL) { NodeT *marker = head->next; head->next = NULL; // cut off the rest from the head // in order to reinsert these elements while (marker != NULL) { NodeT *cur = marker; // take the current marker 'cur' ... marker = marker->next; // (advance marker for next round) if (cur->data < head->data) { // ... and make 'cur' the new head ... cur->next = head; head = cur; } else { // ... or find the new predecessor of 'cur' ... NodeT *pred = head; while (pred->next != NULL && (pred->next)->data < cur->data) { pred = pred->next; } cur->next = pred->next; // ... and insert 'cur' after 'pred' pred->next = cur; } } } return head; // head may have changed, hence needs to be returned } |
Alternative solution:
void insertSortLL(NodeT *head) { // insertion sort on a linked list // a data-copy version NodeT *marker = head; NodeT *cur; while (marker != NULL) { // for element 'marker' ... cur = head; // ... find the right position ... while (cur != marker) { // ... and move all other elements up ... if (marker->data < cur->data) { // ... by repeated swaps int save = marker->data; marker->data = cur->data; cur->data = save; } cur = cur->next; } marker = marker->next; } } |
// selsortQ.c: implement a selection sort of the command-line arguments using 2 stacks #include <stdio.h> #include <stdlib.h> #include "quack.h" void selectionSort(Quack, int); int linearSearch(Quack, Quack, int); int main(int argc, char *argv[]) { int readError = 0; int retval = EXIT_SUCCESS; Quack sq; sq = createQuack(); int i; int number; for (i=1; i<argc && !readError; i++) { if (sscanf(argv[i], "%d", &number) != 1) { fprintf(stderr, "Error in arguments\n"); readError = 1; retval = EXIT_FAILURE; } else { push(number, sq); // populate the first quack } } if (!readError) { printf("Original "); showQuack(sq); selectionSort(sq, argc-1); // argc-1 arguments to be sorted printf(" Sorted "); showQuack(sq); } return retval; } int linearSearch(Quack s1, Quack s2, int n) { // pop n items from s1, push to s2, except max int max = pop(s1); int i; for (i=1; i<=n-1; i++) { int num = pop(s1); if (num > max) { int temp = max; max = num; num = temp; } push(num, s2); } return max; } void selectionSort(Quack s1, int size) { Quack s2; s2 = createQuack(); if (!isEmptyQuack(s1)) { int n; for (n=size; n>1; n--) { int max = linearSearch(s1, s2, n); push(max, s1); while (!isEmptyQuack(s2)) { push(pop(s2), s1); } } } } |