• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
47%
SHARE
TWEET

# quicksort.c

Johnthomas Feb 20th, 2012 147 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. ;
RAW Paste Data
Top