Thread: no one is able to explain!

  1. #1
    Registered User
    Join Date
    Mar 2010

    Angry no one is able to explain!

    qsort -> please explain-it

    I started my discussion in the above link, while copy and pasting the Quicksort Algorithm from "The C Programming Language, Second Edition" by Brian W. Kernighan and Dennis M. Ritchie (page 87).

    And I rised a simple question, e.g. if we have these inputs: e.g. {11, 3, 9, 7, 4)

    How this algorithm will work (just one iteration)! Believe me or not, no one was able to explain it

    TERRIFYING! And I still have problem to understand it... well I am novice, dummy etc. But what about others?

    /* qsort: sort v[left]...v[right] into increasing order */
    void qsort(int v[], int left, int right)
    int i, last;
    void swap(int v[], int i, int j);
    if (left >= right) /* do nothing if array contains */
    return; /* fewer than two elements */
    swap(v, left, (left + right)/2); /* move partition elem */
    last = left; /* to v[0] */
    for (i = left + 1; i <= right; i++) /* partition */
    if (v[i] < v[left])
    swap(v, ++last, i);
    swap(v, left, last); /* restore partition elem */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
    /* swap: interchange v[i] and v[j] */
    void swap(int v[], int i, int j)
    int temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;

  2. #2
    Registered User GL.Sam's Avatar
    Join Date
    Aug 2009
    The idea is somewhat close to that of binary search, but here no part of an array should be ignored, that's why two statements of recursion are used. Try to trace this algorithm in debugger or even on plain paper.
    The only good is knowledge and the only evil is ignorance.

  3. #3
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    United States
    Are you even still paying attention to that thread?

    Quick sort sorts through something called partitioning.

    Explaining partitioning: You pick an element to partition around called the pivot (or last, in your code). In your code, the algorithm is going to pick the middle one every time. Then you swap the middle and first arguments. Then you walk the array comparing the ith element with the left element, and swapping to arrange it such that everything to the left of 'last' is less than 'left', and everything greater is to the right. This sorts the pivot into its final position, last, which explains the swap at the end.

    With one element sorted, you still have to divide the array into two parts and partition each part. When every element has had a chance to be a pivot, the array is sorted.

    ( 9, 3, 11, 7, 4, ) pivot=0...
    ( 9, 3, 11, 7, 4, ) pivot=1...
    ( 9, 3, 7, 11, 4, ) pivot=2...
    ( 9, 3, 7, 4, 11, ) pivot=3...
    ( 4, 3, 7, 9, 11, ) pivot=3...
    ( 3, 4, 7, ) pivot=0...
    ( 3, 4, 7, ) pivot=0...
    ( 4, 7, ) pivot=1...
    ( 4, 7, ) pivot=1...
    You could have done this yourself, you know.

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    segmentation fault
    Quote Originally Posted by c_lady View Post
    How this algorithm will work (just one iteration)! Believe me or not, no one was able to explain it
    Part of that was my fault for not interpreting the initial inputs correctly, but you need to take some responsibility too, because the reason I mis-interpreted them is that YOU did not provide the information.

    If you want help with stuff like this, you have to use your brain and make an effort to provide the necessary information, and not expect others to deduce -- which might be why no one else even tried.

    void qsort(int v[], int left, int right)
    What should the initial values for "left" and "right" be here for array (11, 3, 9, 7, 4)? YOU have the book this code came from, it MUST explain that part. Anyway, I am sure if you go thru the process I did in the last thread, but use 0 and 4 instead of 0 and 3, it will work out. Try it on paper.* The -1 indicated a premature end to one side of the sort.

    Also, it is kind of amazing that almost 24 hours later it has not occurred to you to TEST the code and include some simple printf() statements to help you follow the course of execution and how various values change (you could also do that with a debugger). This is a MANDATORY skill for programming, start today!!

    * if it doesn't work out, post the attempt you made and I will go thru it again, promise. Oh but also you must post the information I mentioned. Perhaps maybe the exercise # too, a lot of K&R stuff is online. I think except for the random pivot value that is actually a pretty nice in-place qsort.
    Last edited by MK27; 05-12-2010 at 09:52 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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please explain?
    By neo_phyte in forum C Programming
    Replies: 3
    Last Post: 08-25-2006, 05:23 AM
  2. Can someone explain to me what this code means
    By Shadow12345 in forum C++ Programming
    Replies: 3
    Last Post: 12-22-2002, 12:36 PM
  3. Replies: 4
    Last Post: 11-19-2002, 09:18 PM
  4. Pls explain how this program works...
    By Unregistered in forum C Programming
    Replies: 9
    Last Post: 01-05-2002, 09:53 AM
  5. Can someone explain "extern" to me?
    By valar_king in forum C++ Programming
    Replies: 3
    Last Post: 09-16-2001, 12:22 AM