Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdlib.h> //rand, malloc
- #include <stdio.h> //printf
- struct listnode {
- struct listnode *next;
- long value;
- };
- //Finds length of list, which is usefull in selecting a random pivot
- int ListLength (struct listnode *list)
- {
- struct listnode *temp = list;
- int i=0;
- while(temp!=NULL)
- {
- i++;
- temp=temp->next;
- }
- return i;
- }
- // Prints list to help while working on homework
- void printList(struct listnode *list)
- {
- struct listnode *node;
- node=list;
- printf("\nList Values\n");
- while(node!=NULL)
- {
- printf("%2lo ", node->value);
- node=node->next;
- }
- }
- // Creates a list of desired length
- struct listnode *createList(int lengthOfList)
- {
- long i;
- struct listnode *node, *space;
- space = (struct listnode *) malloc( lengthOfList*sizeof(struct listnode));
- for( i=0; i< lengthOfList; i++ )
- { (space + i)->value = 2*((17*i+1)%lengthOfList);
- (space + i)->next = space + (i+1);
- }
- (space+(lengthOfList-1))->next = NULL;
- node = space;
- return node;
- }
- // Prof Brass's test
- void Brass_test(struct listnode *list)
- {
- int i;
- printf("\nChecking sorted list\n");
- for( i=0; i < 100; i++)
- {
- if( list == NULL )
- {
- printf("List ended early\n"); exit(0);
- }
- if( list->value != 2*i )
- {
- printf("Node contains wrong value\n"); exit(0);
- }
- list = list->next;
- }
- printf("Sort successful\n");
- }
- // Selects a random pivot point
- struct listnode *SelectPivot(struct listnode *list)
- {
- int k, n, i = 0;
- n = ListLength(list);
- struct listnode *pivot=list;
- k=rand()%n;
- for (; i < k; ++i)
- {
- pivot=pivot->next;
- }
- return pivot;
- }
- // Sorts a list using quicksort algo with random pivot point
- struct listnode *Quicksort(struct listnode *list)
- {
- // Return NULL list
- if (ListLength(list) <= 1) return list;
- struct listnode *less=NULL, *more=NULL, *next, *endl, *temp=list;
- // Select a random pivot point
- struct listnode *pivot = SelectPivot(list);
- printf("Pivot Value = %lo\n", pivot->value);
- // Divide & Conquer
- while(temp != NULL)
- {
- next = temp->next;
- if(temp->value < pivot->value)
- {
- temp->next = less;
- less = temp;
- }
- else
- {
- temp->next = more;
- more = temp;
- }
- temp = next;
- }
- // printf("\nLess list =\n");
- // printf("List Count %d\n", ListLength(less));
- // printList(less);
- // printf("\nMore list =\n");
- // printf("List Count %d\n", ListLength(more));
- // printList(more);
- // printf("\nlist list =\n");
- // printf("List Count %d\n", ListLength(list));
- // printList(list);
- // Recursive Calls
- // less = Quicksort(less);
- // more = Quicksort(more);
- // Merge
- if(ListLength(less)!=0)
- {
- while(endl != NULL)
- {
- endl = less->next;
- less->next = more;
- more = less;
- less = endl;
- }
- return more;
- }
- else
- {
- return more;
- }
- }
- int main(void)
- {
- struct listnode *node;
- node = createList(25);
- printf("Unsorted List\n");
- printList(node);
- printf("\nSorted List\n");
- node = Quicksort(node);
- printf("\nList Count node %d\n", ListLength(node));
- printList(node);
- // Brass_test(node);
- exit(0);
- }
- ;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement