Results 1 to 2 of 2
  1. #1
    TheElder777 is offline Member
    Join Date
    Oct 2012
    Posts
    6
    Rep Power
    0

    Default What is the problem (quicksort)?

    Hi all. I am currently working on quicksort and have written the following code and gives "almost" good results. I am not too fond of the data structure I have chosen but it is too late for me to change. Lesson learned. Can anyone help me debug this thing. I have been at it for a while. Anyway here is the code:

    Java Code:
    	static Random myGen = new Random();
    	public static void quickSort(DLinkedList unsortedList, int start, int finish){
    		int randpiv;
    		int offset = 0;
    		if(finish == -1){
    			randpiv = 0;
    		}else{
    			randpiv = myGen.nextInt(finish+1);
    		}
    		
    		if(finish - start <= 1){
    			return;
    		}
    		for(int i = start; i < randpiv; i++){		
    			if(unsortedList.distofElem(i) >= unsortedList.distofElem(randpiv)){
    				offset++;
    				DLNode moveMe = unsortedList.removeDist(unsortedList.distofElem(i));
    				unsortedList.insertAfter(moveMe, randpiv);
    			}
    		}
    		for(int i = randpiv + offset + 1; i <= finish; i++){
    			if(unsortedList.distofElem(i) < unsortedList.distofElem(randpiv)){
    				DLNode moveMe = unsortedList.removeDist(unsortedList.distofElem(i));
    				unsortedList.insertBefore(moveMe, randpiv);
    			}
    		}
    		quickSort(unsortedList, start, randpiv - 1);
    		quickSort(unsortedList, randpiv + 1, finish);		
    	}
    
    //here are insert after and insert before//
    
    //insert before an index//
    	public void insertBefore(DLNode putMe, int index){
    		listLength++;
    		int intTemp = 0;
    		for(temp = myRoot; intTemp < index; temp = temp.next){
    			intTemp++;
    		}
    		System.out.println("Inserting: " + putMe.getDistance() + " BEFORE: " + temp.getDistance());
    		if(temp == myRoot){
    			myRoot.prev = putMe;
    			putMe.next = myRoot;
    			putMe.prev = null;
    			myRoot = myRoot.prev;
    		}else{
    			temp.prev.next = putMe;
    			putMe.prev = temp.prev;	
    			temp.prev = putMe;
    			putMe.next = temp;
    		}
    	}
    
    	//insert after an index//
    	public void insertAfter(DLNode putMe, int index){
    		listLength++;
    		int intTemp = 0;
    		for(temp = myRoot; intTemp < index; temp = temp.next){
    			intTemp++;
    		}
    		System.out.println("Inserting: " + putMe.getDistance() + " AFTER: " + temp.getDistance());
    		if(temp == myTail){
    			myTail.next = putMe;
    			putMe.prev = myTail;
    			putMe.next = null;
    			myTail = myTail.next;
    		}else{
    			temp.next.prev = putMe;
    			putMe.next = temp.next;	
    			temp.next = putMe;
    			putMe.prev = temp;
    		}
    	}
    here is the input i feed it:
    29403 97291 7211 487075 10000000 9902 89600 1620 22500 180000 152 10 14700 1026046 6646 19769 17708 10201 16250 533026 1424561 880025 12930 91210 25004 580800 926718

    Here is the output i get:
    10
    152
    1620
    6646
    7211
    9902
    10201
    12930
    14700
    16250
    17708
    19769
    22500
    25004
    29403
    89600
    97291
    180000
    487075
    880025
    533026
    1424561
    91210
    10000000
    1026046
    580800
    926718

    which is close, but not quite.

    Thanks for reading.

  2. #2
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default Re: What is the problem (quicksort)?

    I don't have time to step through your code line by line at the moment, but looking at the data, my guess is that one or several of your calls are either terminating early, or you have a bug in your partition code (an off by 1 index sometimes will do this).

    I suggest you make the smallest list you can (like 5 or 10 elements) in which the problem still occurs, and then step through the algorithm using the debugger while simultaneously doing it on a sheet of graph paper. At each step, do it on graph paper (with the master list and all the partitioned sub lists) so you will know the expected state of the list. Then see how the actual code is different.

    I had similar problems years ago, and it was something to do with my partitioning - don't remember exactly what, but it was either goofy median placement, or I had or was missing a >= instead of just a > - something like that. Essentially, it was moving my bounds index off by 1 in only one direction.

    Good luck!

Similar Threads

  1. Quicksort median
    By louboulos in forum New To Java
    Replies: 6
    Last Post: 05-16-2012, 11:36 PM
  2. my Quicksort attempt has failed
    By Jeremy8 in forum New To Java
    Replies: 4
    Last Post: 11-16-2009, 03:56 AM
  3. problem with quicksort
    By jvasilj1 in forum New To Java
    Replies: 2
    Last Post: 03-05-2009, 01:09 AM
  4. quicksort program
    By jvasilj1 in forum New To Java
    Replies: 5
    Last Post: 03-03-2009, 04:47 AM
  5. Quicksort
    By little_polarbear in forum New To Java
    Replies: 12
    Last Post: 07-12-2008, 10:20 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •