Help me on Quick Sort algorithm

This is a discussion on Help me on Quick Sort algorithm within the C Programming forums, part of the General Programming Boards category; I'm getting a 'Segmentation fault' program while running the following program.Please help me to find out the error. Code: //------------------------------------------------------------------------- ...

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    4

    Help me on Quick Sort algorithm

    I'm getting a 'Segmentation fault' program while running the following program.Please help me to find out the error.
    Code:
    //-------------------------------------------------------------------------
    int partition(int a[],int first,int last)
    {
    int pivot,up,down,i,j,n,pivindex,temp;
    
    up=first;
    down=last;
    pivot=a[first];
    
    
    
    do
    {
    
    //move 'up' to the first value > pivot
    
    for(i=0;i<n;i++)
    	{
    		if(a[i]>pivot)
    			up=i;
    	}
    //move 'down' to the first value <=pivot
    
    for(i=n;i>0;i--)
    	{
    		if(a[i]<=pivot)
    		down=i;
    	}
    temp=a[up];
    a[up]=a[down];
    a[down]=temp;
    }while(up<=down);
    
    //Swap pivot and a[down]
    
    temp=a[first];
    a[first]=a[down];
    a[down]=temp;
    
    //Set pivindex at the current position of down 
    //so that all values below pivindex are <=pivot 
    //and vice versa
    
    pivindex=down; 
    
    return pivindex;
    
    }
    //----------------------------------------------------------------------------
    void quicksort(int a[],int first,int last)
    {
    int pivindex;
    
    	if(first<last){
    	pivindex=partition(a,first,last);
    	quicksort(a,first,pivindex-1);
    	quicksort(a,pivindex+1,last);
    			}
    		
    }
    //-----------------------------------------------------------------------------
    main()
    {
    int a[20],n;
    
    printf("\nPlease enter the no. of elements::");
    scanf("%d",&n);
    printf("\nPls enter the array to sorted(quick sort)::");
    read_arr(a,n);
    printf("\nArray elements are as follows:\n");
    print_arr(a,n);
    quicksort(a,0,n-1);
    printf("\n The Sorted list is:\n");
    print_arr(a,n);
    
    }
    //-------------------------------------------------------------------------------

  2. #2
    Registered User
    Join Date
    Mar 2006
    Posts
    4
    I attach the c file itself.
    Attached Files Attached Files

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by chatterjee View Post
    I'm getting a 'Segmentation fault' program while running the following program.Please help me to find out the error.
    Have you tried to locate the line which causes the seg fault?

    Do you have access to a debugger?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Your base assumption seems to be that n has a meaningful value inside partition. Why you make this assumption when it is demonstrably false, I don't know.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Even if 'n' did have a meaningful value, the partition step still shouldn't be going over ALL items in the array each time. You need to stop thinking of the function as if you're writing it for the first call, and write it as if it has already been called recursively several times and you're partitioning data somewhere in the middle of your array.
    Perhaps performing a quicksort by hand, using say a deck of cards, might help?
    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 slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    I have to hit my hand sometime when I see these types posts to prevent me from writing some code down. The jist of the matter is that you should read up on "Algorithms in C - Robert Sedgewick" that really nailed it for me in terms of understanding the sorting algorithms that are out there and how to properly use them.

  7. #7
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78
    here is one of the compact easy to memorize and understand implementations of quicksort.. forgot where i got it:

    pivot is selected to be the mid value here

    Code:
    void quicksort(int a[], int l, int r)
    {
        int i=l, j=r;
        int temp;   
        int pivot=a[(l+r)/2]; //pivot value is the mid value
    
        /* Split the array into two parts */
        do
        {    
            while (a[i] < pivot) i++; 
            while (a[j] > pivot) j--;
            if (i<=j)
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
                i++;
                j--;
            }
        } while (i<=j);
    
        /* call the functions recursively */
        if (l < j) quicksort(a, l, j);
        if (i < r) quicksort(a, i, r);
    }

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by slingerland3g View Post
    The jist of the matter is that you should read up on "Algorithms in C - Robert Sedgewick" that really nailed it for me in terms of understanding the sorting algorithms that are out there and how to properly use them.
    I used "Beginning Programming for Dummies" (W. Wang) .

    All of the sort algorithms, including quicksort, can be easily described in a single page using a diagram. The pivot value can make a *huge* difference in the efficiency of the outcome; using a random one (as in BlackOp's example) is the worst way to do it, because the two arrays can easily end up lopsided. A slightly better way would be to take two random values and use the average. Using the actual average would be the best, but ultimately inefficient since that means performing operations on the entire array.
    Last edited by MK27; 07-18-2009 at 08:48 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,889
    Quote Originally Posted by MK27
    The pivot value can make a *huge* difference in the efficiency of the outcome; using a random one (as in BlackOp's example) is the worst way to do it, because the two arrays can easily end up lopsided.
    Eh, BlackOp's pivot selection is not random, but rather, fixed as the middle element of the given partition. A randomly selected pivot is actually not bad.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78
    just selecting a mid value seems ok for me for most of the common sorting problems

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    Eh, BlackOp's pivot selection is not random, but rather, fixed as the middle element of the given partition. A randomly selected pivot is actually not bad.
    Since the array has not been sorted, the value of pivot has been selected from the array at random; you might as well just use a[0].

    For example, in the series: 2 9 3 1 4 5 7, if I picked 1 as the pivot value, one side will have only one element and the other will have 7. Quick sort will suffer badly if it repeatedly processes lopsided lists because of a random pivot -- sorting a shorter list is expontentially faster (it takes more than twice as long to sort a list twice as long). Way back when I did this

    How to sort a simple linked list using swap-sort method

    The profile for quicksort was improved like 1000%+ on large lists by using some kind of chosen value for the pivot (I think I did what I said above) vs. a random value from the list.

    Quote Originally Posted by BlackOps View Post
    just selecting a mid value seems ok for me for most of the common sorting problems
    pivot=a[(l+r)/2] is not a "mid value", unless you mean it is just the value in the middle of a series. Which, as I just explained, could be the lowest or highest value in the array -- there is no way to know.

    However, if the list is mostly or somewhat sorted it is a good one since quick sort's "worst case" scenario is (generally) the already sorted list.

    IMO mergesort is more consistent than quicksort because of stuff like this...
    Quote Originally Posted by mk27
    Quicksort suffers [...] with ties for the same reason it suffers sorting an already ordered list, which is it's worst case scenario. Because mergesort does not spend time putting a list in order after it's been split off, and instead does it when merging them together, it will benefit if the original list was already in some kind of order, whereas this will only hurt quicksort depending on how the pivot value is choosen. To establish a mean or median value, we must iterate through the list before splitting it -- although in discussions of quicksort I have seen, this process apparently "does not count" as part of it's big O notation. Additional comparisons at each of these iterations would be required as well. Taking the pivot from an already ordered tied list will usually end up on the low side, creating an imbalanced list. Putting pivot ties on the right (opposite the pivot) may improve performance slightly.
    Last edited by MK27; 07-18-2009 at 11:11 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,889
    Quote Originally Posted by MK27
    Since the array has not been sorted, the value of pivot has been selected from the array at random; you might as well just use a[0].
    That is a flawed premise: the array could well be sorted or mostly sorted. Quicksort with a randomly selected pivot would be expected to perform roughly the same with any input on average.

    Quote Originally Posted by MK27
    The profile for quicksort was improved like 1000% on large lists by using some kind of chosen value for the pivot (I think I did what I said above) vs. a random value from the list.
    If I know what (fixed) method was used, I can design pathological worst case input for it. With a truly randomly selected pivot, that is not possible (or rather, it is possible, but would not matter since I will only trigger quadratic time performance by luck), and with a pseudorandomly selected pivot, that is only possible if I can determine the state of the PRNG.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    That is a flawed premise: the array could well be sorted or mostly sorted. Quicksort with a randomly selected pivot would be expected to perform roughly the same with any input on average.
    The longer an unsorted list, the less chance it has of resembling something partially sorted. Getting dealt a 10 or 100 or 1000 value run is unlikely, but if the list is only 20 items then 3 values in a row will make a difference.

    I was just trying to decifer/remember the stuff from my earlier thread, but I'm almost positive the quicksort I wrote went from taking several minutes to sort millions of strings alphabetically to less than 10 seconds just by tweaking the way the pivot value is chosen; when I say 1000%+ plus improvement I'm not exaggerating. (Obviously, this becomes more and more apparently the longer the list. It will not be notable with only a few hundred items.)

    I also recall from reading and googling that a number of people who have written widely used implementations put a lot of stress on the significance of the pivot and how this could make the difference between a weak or mediocre implementation and a real "high performance, best in class" kind of thing.
    Last edited by MK27; 07-18-2009 at 11:24 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,889
    Quote Originally Posted by MK27
    I also recall from reading and googling that a number of people who have written widely used implementations put a lot of stress on the significance of the pivot and how this could make the difference between a weak or mediocre implementation and a real "high performance, best in class" kind of thing.
    Yes, that is indeed the case, and it helps if we know the characteristics of the likely input. I am not sure if a randomly selected pivot selection method can be considered "high performance" since there is the same probability of selecting the worst pivot as there is of selecting the best pivot, but characterising it as "the worst way to do it" is wrong, in my opinion.

    By the way, when you say "average", you mean median, not mean, right? In such a case, "take two random values and use the average" sounds strange.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Thanks for posting that version of Quicksort, BlackOps. It's simplicity somehow makes it shine just a bit brighter, imo.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. testing a bubble sort algorithm
    By rushhour in forum C++ Programming
    Replies: 4
    Last Post: 02-27-2009, 12:00 AM
  2. STL Sort Algorithm
    By f1player in forum C++ Programming
    Replies: 9
    Last Post: 10-10-2008, 01:12 PM
  3. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  4. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 04:21 PM
  5. Sort algorithm and an ugly error
    By Trauts in forum C++ Programming
    Replies: 7
    Last Post: 02-25-2003, 11:36 AM

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