problems with quicksort!

This is a discussion on problems with quicksort! within the C Programming forums, part of the General Programming Boards category; I'm writing an inplace quicksort for linked lists, but I seem to have a bug. I don't know if it's ...

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    16

    problems with quicksort!

    I'm writing an inplace quicksort for linked lists, but I seem to have a bug. I don't know if it's because I changed the structure of my list, but it shouldn't be? I'm infinite looping.

    here is my quicksort function
    Code:
    struct label * quicksort(struct table *p, int list_start, int list_end, FILE *o)
    {
    
    	printTable(p, o);
    	printf("quicksort starting\n");
    	fflush(stdout);
    	struct label *list = p->first;
    	struct label *pivot = malloc(sizeof(struct label));
    	struct label *left=list;
    	struct label *right=list;
    	struct label *tmp;
    	int i = list_start;
    	int j= list_end-1;
    
      	if (list_start >= list_end) {
      		return list;
      	}
    
      	//printf("right is %s\n", right->labelsymbol);
      	right = getNth(list, list_end);
      	//printf("right is %s\n", right->labelsymbol);
      	left = getNth(list, list_start);
    
      	pivot = right;
      	right = findBefore(left, pivot);
      	//printf("right is %s\n", right->labelsymbol);
      	//printf("went here\n");
      	//printf("left %s\n", left->labelsymbol);
      	//printf("pivot %s\n", pivot->labelsymbol);
      	//printf("%d\n", strcmp(left->labelsymbol, pivot->labelsymbol));
      	//printf("%d\n", strcmp(right->labelsymbol, pivot->labelsymbol));
      	fflush(stdout);
    
      	printf("right is %s\n", right->labelsymbol);
      	printf("left %s\n", left->labelsymbol);
      	printf("pivot %s\n", pivot->labelsymbol);
      	while (1) {
    
      		for(; strcmp(left->labelsymbol, pivot->labelsymbol) < 0; left=left->next,i++);
      		for(; strcmp(right->labelsymbol, pivot->labelsymbol) > 0; right = findBefore(list,right),j--); //seems to be looping around here, when right is "main" for some reason?
    
      		printf("!!!came here\n");
      		fflush(stdout);
      		printf("2left %s\n", left->labelsymbol);
      		printf("2right %s\n", right->labelsymbol);
      		printf("i %d j %d\n", i, j);
      		if (i < j) {
      			list = swapEntries(list, left, right);
      			tmp = left;
      			left = right;
      			right = tmp;
      			printf("swapped\n");
      			fflush(stdout);
        }
        else
        	break;
      	}
    
      list = swapEntries(list, left, pivot);
      printf("came here\n");
      printTable(p, o);
      fflush(stdout);
    
      printf("next %d %d\n", list_start, i-1);
      list = quicksort(p, list_start, i-1, o);
      printf("next %d %d\n", i+1, list_end);
      list = quicksort(p, i+1, list_end, o);
    
      //printTable(p, o);
      return list;
    }
    here are the helpers I use:
    Code:
    struct label *getNth(struct label *node, int n)
    {
      int i=1;
      for(i=1;i<n;i++)
      {
        node = node->next;
      }
      return node;
    }
    
    struct label *findBefore(struct label *list, struct label *current) {
    	//printf("finding before %s\n", list->labelsymbol);
    	//printf("current %s\n", current->labelsymbol);
    
    	for(;list && list->next; list = list->next) {
    		if(strcmp(current->labelsymbol, list->next->labelsymbol) == 0) {
    			break;
    		}
    	}
    
    	if (list->next != current) {
    		return current;
    	}
      return list;
    }
    
    
    struct label *swapEntries(struct label *list, struct label *node1, struct label *node2) {
    
      struct label *node1prev;
      struct label *node2prev;
      struct label *tmp;
    
      node1prev = findBefore(list, node1); //find the node before current
      node2prev = findBefore(list, node2);
    
      tmp = node2->next;
      if (node1 != list) {
        node1prev->next = node2;
      }
      else {
        list = node2;
      }
    
      if (node1->next == node2) {
        node2->next = node1;
        node1->next = tmp;
      }
      else {
        node2->next = node1->next;
        node1->next = tmp;
        node2prev->next = node1;
      }
      return list;
    }
    I don't understand why it's not working now, when it worked before. The table I'm putting in looks like this:
    main y 0000
    counter y 001C lhi 0002 llo 0006
    loop y 000A jmp 0014
    done y 0016 jmp 0016
    dummy y 001E
    foo n FFFF jmp 0020
    (I'm only sorting the first labels, so "main", "counter", etc...)

    the structs for my table
    Code:
    struct label {
           char * labelsymbol;
           char defined;
           int value;
           struct lineNode *occur;
           struct label *next;
    };
    
    struct table {
           int labelcount;
           struct label *first;
    };
    this is my printout when I call it
    quicksort starting
    right is dummy
    left main
    pivot foo
    !!!came here
    2left main
    2right dummy
    i 0 j 5
    swapped
    !!!came here
    2left loop
    2right done
    i 2 j 4
    swapped
    !!!came here
    2left loop
    2right done
    i 3 j 3
    came here
    main y 0000
    loop y 000A jmp 0014
    next 0 2
    main y 0000
    loop y 000A jmp 0014
    quicksort starting

    Any help would be much appreciated! Thanks!

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    You're approach is wrong unfortunately. You've obviously written an array sorting algorithm at some point and you're applying the same methods of sorting to a list. Don't do that! A list is fundamentally different and needs different actions to sort it.

    E.g. an array has constant-time lookup but linear time insertion. A list has linear-time lookup, but constant-time insertion.
    You can still perform essentially the same algorithm with a list, but you need to do things a little differently.
    There are some techniques that don't work well for singly-linked-lists:
    • Swapping
    • Reverse iterating
    You've already seen first-hand how annoyingly difficult those are and have attempted to write helper functions for them because of how tricky they actually are. But it doesn't have to be that way. The answer is to not fight with the data structure, just work with its different strengths.
    When it comes to singly-linked-list sorting, you abandon any use of the above operations completely.
    Instead you adopt some different techniques that are perfectly suited to lists:
    • Insertion
    • Removal
    • Prepending
    • Appending
    • Splitting lists
    • Concatenating lists
    Being able to easily do all of these new operations quickly and easily certainly makes up for what you lose with not being an array any more.

    Now lets see how this applies to the partitioning step of quicksort (to start with).
    In the array version we take a single portion and split it into two portions, one of items less-than the splitter, and one of items not less than the splitter. We can still logically do exactly that for singly-linked lists. However instead of swapping items, you iterate forwards over the input list, removing each item as you go, and prepending (or appending if you prefer) each item onto one of two new lists. One new list for the less-than items, and one new list for the not-less-than items.
    Try to take a moment to understand what this all means (ponder it for a bit until it all 'clicks') and start over from scratch.
    The good news is that the actual solution is far simpler than what you have already! You'll find it really easy if you do it the right way.

    You need to get rid of your helper functions entirely anyway. If you were to use those then your sort function would end up more like O(n^4) which is awful, and not really quicksort anymore. Not to mention that actually performing a swap on linked lists is even harder than you realise. Your code almost certainly didn't take into account every case, such as when one item comes after the one you want to swap it with. That's possibly where your infinite loop comes from. Trust me, I've tried it and it's really a pain to get right!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Sep 2009
    Posts
    16
    thanks for your response! unfortunately, I don't have a lot of time, so I don't think I can write out all those inserting removal functions. Also, I'm avoiding creating new lists, because each of my nodes has a lot more stuff attached to it, and I'm worried about creating wrong pointers.

    The run-time doesn't really matter to me, I just want to be able to sort correctly. What I still don't understand is how it can break when I change the structure of my lists, but I'm still comparing the same keys.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Insertion into a linked-list is only two short lines of code! You don't even need to write a function for it. All six of the things I mentioned are either one or two short lines of code each!
    Those six list operations are the basic things you should be using.
    Not having much time is precisely why you should immediately stop going down the dead-end path that you're going down.

    As long as you are aware that you're doing it completely the wrong way, and are likely to get a low mark if this is what you turn in (IMHO), here's a big hint for your current code:
    What does findBefore return when right==list, i.e. you've reached the start of the list?
    Bonus question: What prevents the first for-loop form looping until it goes past the end of the list? (It is prevented, but I'm just seeing if you know why, and I'll help you out furthur if you can answer that correctly)

    Also, get rid of that malloc. You don't allocate heap memory while quicksorting, especially not when all you do is leak it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. pointer problems
    By BradC78 in forum C Programming
    Replies: 9
    Last Post: 02-18-2009, 11:14 PM
  2. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 10:26 PM
  3. No clue how to make a code to solve problems!
    By ctnzn in forum C Programming
    Replies: 8
    Last Post: 10-16-2008, 02:59 AM
  4. Problems with Quicksort and Pointers
    By algatt in forum C Programming
    Replies: 3
    Last Post: 10-10-2007, 04:24 AM
  5. Problems implementing quicksort function
    By rvanbeusichem in forum C Programming
    Replies: 3
    Last Post: 11-24-2004, 08:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21