qsort example

This is a discussion on qsort example within the C Programming forums, part of the General Programming Boards category; Hi, i found this piece of code in K&R book, but i have not understood how it works, page 74, ...

  1. #1
    Registered User blob84's Avatar
    Join Date
    Jun 2010
    Posts
    46

    qsort example

    Hi, i found this piece of code in K&R book, but i have not understood how it works, page 74,
    for example, what represent "int left, int right" variables and how should i use it?
    I know this is not the complete qsort code inside standard library.
    Code:
    /* 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;
    }
    i tried to implement it :
    I renamed qsort to quicksort, because it conflicts with the qsort in the standard library.
    Code:
    #include <stdio.h>
    void qicksort( int v[], int left, int right );
    
    int main(void) {
        int arr[] = { 3, 5, 1, 2, 4 };
        qsort( arr, 0, 5 );    
        int i;
        for ( i = 0; i < 5; i++ )    
            printf("num=%d\n",  arr[i] );
    }
    
        /* qsort: sort v[left]...v[right] into increasing order */
        void qicksort(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 */
            qicksort(v, left, last-1);
            qicksort(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;
        }
    Last edited by blob84; 10-13-2010 at 11:45 AM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,659
    0 and 5 would be good.
    That is, the subscripts of the two ends of the array you want to sort.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User blob84's Avatar
    Join Date
    Jun 2010
    Posts
    46
    It still not working.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,659
    Well that is unfortunate.

    Does it compile - if not, post error messages
    Does it run - if not, post error messages
    Are the results wrong - post results

    We're here to guide you towards an answer, but you need to do actual work of investigation and reporting feedback.

    We don't typically take your first code, spend however long it takes to polish it to perfection and then post the result you can just run to teacher with.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is the part that I find very suspect:

    Code:
            for (i = left + 1; i <= right; i++) /* partition */
            if (v[i] < v[left])
            swap(v, ++last, i);
            swap(v, left, last);
            /* restore partition elem */
            qicksort(v, left, last-1);
            qicksort(v, last+1, right);
            }
    A few things:
    * This should be a do loop or while loop: ie.:
    Code:
    do {
       //inside the loop, you have two while loops, which increment or decrement
       //the left (i) and right (j) indeces:
      while(v[i] < your pivot) ++i;
      while(v[j] > your pivot) --j;
      if(i <= j) {
          swap(your v[i] with v[j]);
    }while(i<=j);
    
    //two calls for the partitions of the array, here
    Your logic is working with i in a mechanical way, and iteratively (imo), rather than flexibly, in a recursive way. Also, you don't do anything with j. You only work with left, right, and i.

    Since you're not swapping v[i] with v[j], I don't understand your swaps.
    Last edited by Adak; 10-13-2010 at 01:02 PM.

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,738
    Given that the array has five elements, using 0 and 4 as subscripts you want to sort would be better. The fifth subscript is actually the sixth element counting from one, and so on.

  7. #7
    Registered User blob84's Avatar
    Join Date
    Jun 2010
    Posts
    46
    This is not my code, i found it in the C language book, by Kernighan and Ritchie.
    I was calling the function with qsort instead of quicksort.
    It works very well.
    But the code is not very clear, i should study it.

    Code:
    #include <stdio.h>
    void qicksort( int v[], int left, int right );
    
    int main(void) {
        int arr[] = { 3, 5, 1, 2, 4 };
        qicksort( arr, 0, 4 );    
        int i;
        for ( i = 0; i < 5; i++ )    
            printf("num=%d\n",  arr[i] );
    }
    
        /* qsort: sort v[left]...v[right] into increasing order */
        void qicksort(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 */
            qicksort(v, left, last-1);
            qicksort(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;
        }

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Yeah, that's where I and qsort() have our differences.

    Because to me, Quicksort is a classic "divide and conquer" algorithm. What qsort does is to move the pivot out of the way, and then partition the whole sub-array space. (while i < right

    What I like to have it do, is to leave the pivot value where it started from, and then stop the partitioning, when the left index is greater than the right index (while i < j).

    The result is about the same, but the second version is quicker, in my several tests, and easier to understand, imo.

    Code:
    //Quicksort w/o a separate compare function :)
    void quicksort(int A[], int lo, int hi) {
      int i, j, pivot, temp;
    
      if(lo == hi) return; 
      i=lo; 
      j=hi;
      pivot= A[(lo+hi)/2]; 
    
      /* Split the array into two parts */
      do {    
        while (A[i] < pivot) i++; 
        while (A[j] > pivot) j--;
        if (i<=j) {
          //swap(A, i, j);   //this line works fine if you have a separate swap function
            temp= A[i];     //rem out the swap code on these 3 lines of code
            A[i]= A[j];
            A[j]=temp;
          i++;
          j--;
        }
      } while (i<=j);
        
      if (lo < j) quicksort(A, lo, j);
      if (i < hi) quicksort(A, i, hi);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem with qsort and array via calloc
    By Zimbobo in forum C Programming
    Replies: 2
    Last Post: 11-22-2009, 11:25 PM
  2. An interesting problem of qsort()
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 03-05-2008, 11:09 AM
  3. C++ link error with qsort
    By bvnorth in forum C++ Programming
    Replies: 7
    Last Post: 10-24-2003, 02:22 AM
  4. qsort problems... help!
    By Manseed in forum C Programming
    Replies: 5
    Last Post: 06-21-2003, 04:39 PM
  5. Qsort
    By Tombear in forum C Programming
    Replies: 1
    Last Post: 10-28-2001, 08:06 AM

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