Thread: Need help to display the process of partitioning and sorting of quick sorting

  1. #1
    Registered User
    Join Date
    Jul 2012
    Posts
    9

    Need help to display the process of partitioning and sorting of quick sorting

    i am totally new to programming and i have to do quick sort programming and i can't seem to find the correct code to write for the sorting, this is the best i can do though





    insert
    Code:
    #include <stdio.h>
    #include <conio.h>  
     #define cutoff 3  
     void swap(int *a,int *b)  
     {  
        int temp=*a;  
        *a=*b;  
        *b=temp;  
     }  
     int median(int a[],int left,int right)  
     {  
       int center=(left+right)/2;  
       if(a[left]>a[center])  
       swap(&a[left],&a[center]);  
       if(a[left]>a[right])  
       swap(&a[left],&a[right]);  
       if(a[right]<a[center])  
       swap(&a[right],&a[center]);  
       swap(&a[center],&a[right-1]);  
       return a[right-1];  
     }  
     void insertionsort(int A[],int n)  
     {  
     int j,p,temp;  
     for(p=1;p<n;p++)  
     {  
     temp=A[p];  
     for(j=p;j>0&&A[j-1]>temp;j--)  
     A[j]=A[j-1];  
     A[j]=temp;  
     }  
     }  
     void qsort(int a[],int left,int right)  
     {  
        int i,j,pivot;  
        if(left+cutoff<=right)  
        {  
         pivot=median(a,left,right);  
         i=left;  
         j=right-1;  
         while(1)  
         {  
             while(a[++i]<pivot){}  
             while(a[--j]>pivot){}  
             if(i<j)  
             swap(&a[i],&a[j]);  
             else  
             break;  
         }  
         swap(&a[i],&a[right-1]);  
         qsort(a,left,i-1);  
         qsort(a,i+1,right);  
        }  
        else  
        insertionsort(a+left,right-left+1);    
     }
     
    
     
     
     
       
     void quicksort(int a[],int n)  
     {  
        qsort(a,0,n-1);  
     }   
     int main()  
     {  
       printf("Unsorted array:\n8,5,2,13,1,17,6,4,9,15,7,3\n");
       printf("Sorted array: \n");
       int a[]={8,5,2,13,1,17,6,4,9,15,7,3};  
       quicksort(a,12);  
       int i;  
       for(i=0;i<12;i++)  
       
        {
         printf("%d ",a[i]);  
        }  
        getch();  
     }

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Can't FIND a program??

    Oh my!

    We're not a code library or scavenger oriented forum, but your Quicksort is similar to the one I use.

    What part of your program is working OK, -- and what part is NOT working OK?

    You will not learn anything about writing code (or Quicksort), by just posting bad code, and saying "It doesn't work". Roll up your sleeves and show some interest in fixing this. Quicksort is a brilliant piece of logic! REALLY worth your time to learn about it.

    I don't mean to be crude or rude, but the fact is, if you don't show some increased interest in this, why should anyone else take it upon themselves to work on it?

    Do you get warnings from your compiler (and are your warnings turned on)?
    Do you have any compiler errors

    If you try to sort 7 int's (0,1,2,3,4,5,6,7), what is the output from the program?
    Now try (5,4,7,6,0,3,2,1) and see what you get.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You are actually pretty close.
    One thing I see that is a problem is your inner while loops.
    "i" starts at "left", then the ++i adjusts that to left+1 before it looks at the item in the array.
    Similarly, the first item it indexes with j will be right-2.

    Have you traced it through in a debugger?
    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"

  4. #4
    Registered User
    Join Date
    Jul 2012
    Posts
    9
    everything is working i only don't know what to type in for displaying the partitioning and sorting when i run it

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Oh wow, you're right, it passes every test I threw at it. It does in fact appear to sort correctly! I can see why now too.

    If you are interested in drawing the items and animating the sorting process, then you need to put in some delays, and add some code to draw the items in their positions at various points throughout the sorting.
    I have a program which can animate lots of sorting algorithms here. Perhaps that is the kind of thing you are wanting to make?
    Or perhaps you just want to show numbers in the console?
    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"

  6. #6
    Registered User
    Join Date
    Dec 2007
    Posts
    2,675
    Adak nailed it. Typical copy/paste Turbo C code. The OP has no idea how to program (because he's a copy/paster), so the code doesn't exactly satisfy his assignment. Solution: find someone to give him the code to complete it.

  7. #7
    Registered User
    Join Date
    Jul 2012
    Posts
    9
    Unfortunately i'm only a beginner and i was told to search from the net to complete and the only hint given is this quick sort program running as shown in the picture
    (Display array of unsorted numbers which is defined as 8,5,2,13,1,17,6,4,9,15,7,3 , display process of partitioning and sorting, display the final sorted product)

    Need help to display the process of partitioning and sorting of quick sorting-1-jpgNeed help to display the process of partitioning and sorting of quick sorting-2-jpg

    I'm using Dev-C++ to write this program and i only can use C program code when i wasn't even guided what am i supposed to find
    Last edited by Low Chee Kwan; 07-11-2012 at 06:54 AM.

  8. #8
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    Quote Originally Posted by Low Chee Kwan View Post
    Unfortunately i'm only a beginner and i was told to search from the net to complete and the only hint given is this quick sort program running as shown in the picture
    Are you taking a programming class, or a "how to use google" class?

  9. #9
    Registered User
    Join Date
    Jul 2012
    Posts
    9
    Exactly. No source code to learn from. I don't understand why this task was even given

  10. #10
    Registered User
    Join Date
    Jul 2012
    Posts
    9
    can anyone show example or explain on which part of the code should i print array to show the process as shown in the picture?

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Low Chee Kwan View Post
    can anyone show example or explain on which part of the code should i print array to show the process as shown in the picture?
    My suggestion is to make the printing loop you have now in main(), into a printIt function by itself. Then call the printIt function: (and remove the current for loop used for printing from main(), and move it to the printIt function). Then:

    1) Before the start of the sort. Remove the current (first) print line in main(), and replace it with a call to the printIt function.
    2) After the mid point has been selected - and highlight the mid point number, perhaps by printing it with a yellow color so it stands out
    3) After each swap
    4) Immediately after each recursive call to qsort()

    Adding newlines as needed.

    Instead of printing all the array, all the time you call printIt(), I would just print the sub-array part that is actually being sorted, with each call. So if you have 10 numbers, you print all 10 numbers on the first, and on the last calls to printIt(). All the other calls to printIt(), you print only the part of the array, that you are passing to qsort().

    It sounds more difficult than it is to do this - you already are passing the parameters you would use for printIt(), to qsort().

    Your program has this recursive call:
    Code:
    qsort(a,left,i-1);
    And you would then call printIt() with:
    Code:
    qsort(a,left,i-1);
    printIt(a, left, i-1);
    So you're printing the subarray between left and i-1, only at that time.

    Similarly,
    Code:
    qsort(a,i+1,right); 
    
    //becomes
    qsort(a,i+1,right); 
    printIt(a, i+1, right);
    Since now you want to print out the sub-array between i+1, and right.

    Also, print out the entire array is before you call the Insertion sort function.
    Last edited by Adak; 07-11-2012 at 10:16 AM.

  12. #12
    Registered User
    Join Date
    Jul 2012
    Posts
    9
    not quick sure what you mean but i'll give it another try thanks a lot

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Low Chee Kwan View Post
    not quick sure what you mean but i'll give it another try thanks a lot
    In your example above, you are printing out the entire array, every time you print any part of the array.

    My suggestion was to print out only the part of the sub-array, that was being sorted, at that moment, instead.

    Quicksort works by repeatedly taking the array, choosing a pivot value, and moving the array values in comparison to that pivot. (Lower numbers go to the left, higher numbers go to the right). With every recursive call, the range of the array index being worked on, is cut down - that's why the call to qsort() has a variable for left and right (low and high) index values being passed to it, instead of just 0 and N-1 all the time. (Where 0 to N-1 is the full size of the array indexes). So as the recursive calls continue, the part of the array being sorted at that time, becomes progressively smaller.

    The beauty of the recursive Quicksort, is that these sub-array's being worked on (and there will be several of them), are all seamlessly put back "together" (rejoined), by the return from the recursive calls. If you haven't seen this before, it's a bit like magic, the way recursive calls keep track of all this, without anything being needed from you.

    This problem you're having now does highlight the problem with copy/pasting available code. As sure as the sun rises in the East, you're going to want code that does something - and you won't be able to find it! Now you're stuck!

    Try adding some print statements as I suggested above, and post that code, along with whatever problems you now are having.

    We can help, but we need to see what you're doing with the code, to understand how to help you.

  14. #14
    Registered User
    Join Date
    Jul 2012
    Posts
    9
    i haven't learn much about call function so i not sure how to relate printIt with the quick function i get printIt undeclared when i run it



    Code:
    #include <stdio.h>
    #include <conio.h>  
     #define cutoff 3  
     void swap(int *a,int *b)  
     {  
        int temp=*a;  
        *a=*b;  
        *b=temp;  
     }  
     int median(int a[],int left,int right)  
     {  
       int center=(left+right)/2;  
       if(a[left]>a[center])  
       swap(&a[left],&a[center]);  
       if(a[left]>a[right])  
       swap(&a[left],&a[right]);  
       if(a[right]<a[center])  
       swap(&a[right],&a[center]);  
       swap(&a[center],&a[right-1]);  
       return a[right-1]; 
     }  
     void insertionsort(int A[],int n)  
     {  
     int j,p,temp;  
     for(p=1;p<n;p++)  
     {  
     temp=A[p];  
     for(j=p;j>0&&A[j-1]>temp;j--)  
     A[j]=A[j-1];  
     A[j]=temp;
     }  
     }  
     void qsort(int a[],int left,int right)  
     {    
        int i,j,pivot;  
        if(left+cutoff<=right)  
        {  
         pivot=median(a,left,right);  
         i=left;  
         j=right-1;  
         while(1)  
         {  
             while(a[++i]<pivot){}  
             while(a[--j]>pivot){}  
             if(i<j)  
             swap(&a[i],&a[j]);  
             else  
             break;
             
         }  
         swap(&a[i],&a[right-1]);  
         qsort(a,left,i-1);
         printIt(a, left, i-1);     
         qsort(a,i+1,right);      
         printIt(a, i+1, right);
        }  
        else  
        insertionsort(a+left,right-left+1); 
       
       
     }
     
     void printIt()
     {
          printf("%d", a[i]);
    }
     
     
     
       
     void quicksort(int a[],int n)  
     {  
        qsort(a,0,n-1);  
     }   
     int main()  
     {  
       printf("Unsorted array:\n8,5,2,13,1,17,6,4,9,15,7,3\n");
       printIt( );
     printf("\n\t");
    system("pause");
    return 0;
    }

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    void printIt() is not recognized, because you don't have the parameters correct for it. You want to change line #63 to
    Code:
    void printIt(int a[], int left, int right) {
       int i;
       for(i=left, i<right;i++)
          printf("%2d ",a[i]);
       printf("\n");
    }
    Then, whenever you want to print out the array (the part that you want of it at least), you'd use:
    Code:
    printIt(a, NameOFLeftVariable, NameOFRightVariable);
    
    so your first call (where you want to print all the numbers), would be
    printIt(a, 0, 12);
    But, instead of using 12, I would add a

    #define N 12

    Right below your other define at the top of your program. Then use printIt(a, 0, N).

    And you removed the call to quicksort() in this version of your program. You need that added back into the program, as it was before.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 11
    Last Post: 02-20-2012, 10:38 PM
  2. Quick/Merge sorting floating point numbers
    By stupid_engineer in forum C Programming
    Replies: 3
    Last Post: 09-29-2010, 10:34 AM
  3. Quick Sorting ?!?!?
    By Moni in forum C++ Programming
    Replies: 3
    Last Post: 03-09-2003, 05:14 PM
  4. Sorting words with a fast, effincient sorting method
    By Unregistered in forum C++ Programming
    Replies: 19
    Last Post: 07-12-2002, 04:21 PM
  5. Quick question on sorting a singly linked list
    By Ham in forum C++ Programming
    Replies: 1
    Last Post: 10-08-2001, 11:26 PM

Tags for this Thread