Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

quicksort.c

By: Johnthomas on Feb 20th, 2012  |  syntax: C  |  size: 3.26 KB  |  views: 100  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <stdlib.h>             //rand, malloc
  2. #include <stdio.h>              //printf
  3.  
  4.  
  5. struct listnode {
  6.  
  7.         struct listnode *next;
  8.         long value;
  9. };
  10.  
  11. //Finds length of list, which is usefull in selecting a random pivot
  12. int ListLength (struct listnode *list)
  13. {
  14.         struct listnode *temp = list;
  15.        
  16.         int i=0;
  17.         while(temp!=NULL)
  18.         {
  19.                 i++;
  20.                 temp=temp->next;
  21.  
  22.         }
  23.         return i;
  24. }
  25.  
  26. // Prints list to help while working on homework
  27. void printList(struct listnode *list)
  28. {      
  29.         struct listnode *node;
  30.         node=list;
  31.         printf("\nList Values\n");
  32.         while(node!=NULL)
  33.         {
  34.                 printf("%2lo ", node->value);
  35.         node=node->next;
  36.         }
  37. }
  38. // Creates a list of desired length
  39. struct listnode *createList(int lengthOfList)
  40. {
  41.         long i;
  42.     struct listnode *node, *space;
  43.     space =  (struct listnode *) malloc( lengthOfList*sizeof(struct listnode));
  44.     for( i=0; i< lengthOfList; i++ )
  45.     {  (space + i)->value = 2*((17*i+1)%lengthOfList);
  46.        (space + i)->next = space + (i+1);
  47.     }
  48.  
  49.     (space+(lengthOfList-1))->next = NULL;
  50.     node = space;
  51.  
  52.     return node;
  53. }
  54.  
  55. // Prof Brass's test
  56. void Brass_test(struct listnode *list)
  57. {
  58.         int i;
  59.         printf("\nChecking sorted list\n");
  60.         for( i=0; i < 100; i++)
  61.     {  
  62.             if( list == NULL )
  63.         {
  64.                 printf("List ended early\n"); exit(0);
  65.         }
  66.         if( list->value != 2*i )
  67.         {  
  68.                 printf("Node contains wrong value\n"); exit(0);
  69.         }
  70.         list = list->next;
  71.    }
  72.    printf("Sort successful\n");
  73. }
  74.  
  75. // Selects a random pivot point
  76. struct listnode *SelectPivot(struct listnode *list)
  77. {
  78.  
  79.         int k, n, i = 0;
  80.         n = ListLength(list);
  81.  
  82.  
  83.         struct listnode *pivot=list;
  84.  
  85.         k=rand()%n;
  86.  
  87.         for (; i < k; ++i)
  88.         {
  89.                 pivot=pivot->next;
  90.         }
  91.  
  92.         return pivot;
  93. }
  94.  
  95. // Sorts a list using quicksort algo with random pivot point
  96. struct listnode *Quicksort(struct listnode *list)
  97. {
  98.         // Return NULL list
  99.         if (ListLength(list) <= 1) return list;
  100.  
  101.         struct listnode *less=NULL, *more=NULL, *next, *endl, *temp=list;
  102.  
  103.         // Select a random pivot point
  104.         struct listnode *pivot = SelectPivot(list);
  105.  
  106.         printf("Pivot Value = %lo\n", pivot->value);
  107.  
  108.  
  109.        
  110.         // Divide & Conquer
  111.         while(temp != NULL)
  112.         {
  113.                
  114.                 next = temp->next;
  115.  
  116.                 if(temp->value < pivot->value)
  117.                 {
  118.                         temp->next = less;
  119.                         less = temp;
  120.                 }
  121.                 else
  122.                 {
  123.                         temp->next = more;
  124.                         more = temp;
  125.                
  126.                 }
  127.                 temp = next;
  128.         }
  129.         // printf("\nLess list =\n");
  130.         // printf("List Count %d\n", ListLength(less));
  131.         // printList(less);
  132.        
  133.         // printf("\nMore list =\n");
  134.         // printf("List Count %d\n", ListLength(more));
  135.         // printList(more);
  136.  
  137.  
  138.         // printf("\nlist list =\n");
  139.         // printf("List Count %d\n", ListLength(list));
  140.         // printList(list);
  141.         // Recursive Calls
  142.  
  143.  
  144.         // less = Quicksort(less);
  145.     // more = Quicksort(more);
  146.  
  147.         // Merge
  148.         if(ListLength(less)!=0)
  149.         {              
  150.                 while(endl != NULL)
  151.                 {
  152.                         endl = less->next;
  153.                         less->next = more;
  154.                         more = less;
  155.                         less = endl;
  156.                 }
  157.  
  158.                 return more;           
  159.         }
  160.         else
  161.         {
  162.                
  163.                
  164.                 return more;   
  165.         }
  166.  
  167. }
  168.  
  169. int main(void)
  170. {
  171.         struct listnode *node;
  172.  
  173.         node = createList(25);
  174.  
  175.         printf("Unsorted List\n");
  176.     printList(node);
  177.  
  178.         printf("\nSorted List\n");
  179.     node =      Quicksort(node);
  180.  
  181.  
  182.         printf("\nList Count node %d\n", ListLength(node));
  183.     printList(node);
  184.  
  185.     // Brass_test(node);
  186.  
  187.  
  188.  
  189.  
  190.         exit(0);
  191. }
  192. ;