Thread: quicksort problem

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    9

    Unhappy quicksort problem

    Hi,

    I have a problem that I'm really stumped on. The problem is this:

    Suppose that a[] is an array of integers of size 100, and that for each i
    a. the element a[i] has value i
    b. the element a[i] has value 99-i
    If quicksort(a, a + 99) is invoked, how many function calls to quicksort() are made? Write your program which will test quicksort(), and compute and print the number of recursive calls to quicksort() for a. and b.

    Can anyone help me figure this out/explain it to me?

  2. #2
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    Start by incrementing a counter inside quicksort every time it's called:
    Code:
    #include <stdio.h>
    
    static int number_of_calls;
    
    void f()
    {
        static int i;
    
        if (i++ == 10)
            return;
    
        number_of_calls++;
        f();
    }
    
    int main(void)
    {
        f();
        printf("%d calls to f()\n", number_of_calls);
    
        return 0;
    }
    p.s. What the alphabet would look like without q and r.

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    9

    Question still a little confused

    Ok, thanks. That helped a bit but I'm still a little confused. I still need to write quicksort(a, a + 99). Do I just declare an array of size 100 in the number_of_calls function or should I create a new file altogether? Please bare with me, I'm still new to C. Thanks!

  4. #4
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    It appears as if you want an array of size 100.
    p.s. What the alphabet would look like without q and r.

  5. #5
    Registered User
    Join Date
    Apr 2003
    Posts
    9
    *bangs head on desk*
    I must be stupid or something, lol!

    I tried a few things (what is commented out):

    #include <stdio.h>
    //#define N 100
    //int A[] = {100};
    //quicksort(list, 0, 99);
    //void quicksort (int *, int, int);
    static int number_of_calls;

    void f()
    {
    static int i;

    if (i++ == 10)
    return;

    number_of_calls++;
    f();
    }

    int main(void)
    {
    f();
    printf("%d calls to f()\n", number_of_calls);

    return 0;
    }

    Unfortunately the book I have doesn't really help me much. What am I doing wrong?

  6. #6
    eh ya hoser, got a beer? stumon's Avatar
    Join Date
    Feb 2003
    Posts
    323
    What is the size of the array? are there supposed to be 100 elements, or does every element have to be set to 100? - edit - if every element has to be 100, how many elements are there supposed to be?
    The keyboard is the standard device used to cause computer errors!

  7. #7
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    It sounds similar to this.
    Code:
    #include<stdio.h> 
    #include<stdlib.h> 
    #include<time.h> 
    
    int compares = 0;
    
    int mycmp(const void *a, const void *b)
    {
       const int *x = a;
       const int *y = b;
       ++compares;
       if ( *x < *y )
       {
          return -1;
       }
       if ( *x > *y )
       {
          return 1;
       }
       return 0;
    }
    
    void fill(int *array, int size)
    {
       int i;
       for ( i = 0; i < size; ++i )
       {
          *array++ = rand() % size;
       }
    }
    
    void show(const int *array, int size)
    {
       int i;
       for ( i = 0; i < size; ++i )
       {
          printf(" %2d%c", *array++, i % 16 == 15 ? '\n' : ',');
       }
       puts("\n");
    }
    
    int main(void) 
    {
       int a[100];
       srand(time(NULL));
       fill(a, sizeof(a)/sizeof(*a));
       show(a, sizeof(a)/sizeof(*a));
       qsort(a, sizeof(a)/sizeof(*a), sizeof(*a), mycmp);
       show(a, sizeof(a)/sizeof(*a));
       printf("compares = %d\n", compares);
       return 0; 
    } 
    
    /* my output 
     33, 82, 91, 36, 24, 22, 54, 81, 44, 24, 33, 28, 71, 69, 57, 90
     99,  9, 14, 56,  8, 72, 63, 13, 37, 48,  8,  8, 60, 41, 91, 64
     12, 46, 23, 14, 58, 89, 70, 63, 27, 74, 46,  3, 24, 76,  2, 28
     63, 28, 65, 78, 45, 78, 71, 31,  4,  9,  7, 38, 47, 98, 88, 17
     91, 23, 19, 11, 60, 85, 93, 47, 36, 28, 29, 58, 87, 74, 24, 14
     35, 98, 20, 12, 62, 65, 78, 75, 46, 46, 48, 94, 72, 18, 78, 59
     87, 59,  8, 16,
    
      2,  3,  4,  7,  8,  8,  8,  8,  9,  9, 11, 12, 12, 13, 14, 14
     14, 16, 17, 18, 19, 20, 22, 23, 23, 24, 24, 24, 24, 27, 28, 28
     28, 28, 29, 31, 33, 33, 35, 36, 36, 37, 38, 41, 44, 45, 46, 46
     46, 46, 47, 47, 48, 48, 54, 56, 57, 58, 58, 59, 59, 60, 60, 62
     63, 63, 63, 64, 65, 65, 69, 70, 71, 71, 72, 72, 74, 74, 75, 76
     78, 78, 78, 78, 81, 82, 85, 87, 87, 88, 89, 90, 91, 91, 91, 93
     94, 98, 98, 99,
    
    compares = 594
    */
    If you want help doing this to your quicksort code, post the code that you have.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  8. #8
    Registered User
    Join Date
    Apr 2003
    Posts
    9
    Well I have this code but I don't think it's correct:

    #define N 100 /* size of array, and four macros below */
    #define swap(x, y) { int t; t = x; x = y; y = t;}
    #define order(x, y) if (x > y) swap(x, y)
    #define o2(x, y) order(x, y)
    #define o3(x, y, z) o2(x, y); o2(x, z); o2(y, z)

    typedef enum {yes, no} yes_no; /*enumeration type yes_no */
    static yes_no find_pivot(int *left, int *right,
    int *pivot_ptr);
    static int *partition(int * left, int *right, int pivot);
    /* static functions - known only in this file */
    int i;

    int main(void)
    {
    double a[N];
    for(i = 0; i < N; i++);
    scanf("%f", &a[i]);
    quicksort(a, a + N -1);
    for (i = 0; i < N, i++) printf("%f", a[i]);
    putchar('\n');
    return 0;
    }

    void quicksort(int *left, int *right) /* recursive algorithm */
    {
    int *p, pivot;
    if (find_pivot(left, right, &pivot) == yes) {
    p = partition(left, right, pivot);
    /* moving all elements < pivot to left partition, */
    /* and >= 0 to right partition */
    quicksort(left, p - 1);
    quicksort(p, right);
    }
    }

    static yes_no find_pivot(int *left, int *right,
    int *pivot_ptr)
    /* pivot is attempted to be different than the smallest value of 3 args */
    {
    int a, b, c, *p;
    a = *left; /* left value */
    b = *(left + (right - left) / 2); /* middle value */
    c = *right; /* right value */
    o3(a, b, c); /* order a, b, c */
    if (a < b) { /* pivot will be b */
    *pivot_ptr = b;
    return yes;
    }
    if (b < c) { /* a == b, pivot will be c */
    *pivot_ptr = c;
    return yes;
    }
    for (p = left +1; p <= right; ++p)
    /* trying to find another pivot != left */
    if (*p != * left) {
    *pivot_ptr = (*p < *left) ? *left : *p;
    return yes;
    }
    return no; /* all elements of an array have the same value */
    }

    static int *partition(int *left, int *right, int pivot)
    {
    while (left <= right) {
    while (*left < pivot)
    ++left; /* no action */
    while (*right >= pivot)
    --right;
    if (left < right) { /* exchanging value to keep < ordering */
    swap(*left, *right);
    ++left;
    --right;
    }
    }
    return left;
    }

  9. #9
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    I just took a quick pass through this.
    Code:
    #include<stdio.h>
    
    #define N 100 /* size of array, and four macros below */
    
    #define swap(x, y)   { int t; t = x; x = y; y = t;} 
    #define order(x, y)  if (x > y) swap(x, y)
    #define o2(x, y)     order(x, y)
    #define o3(x, y, z)  o2(x, y); o2(x, z); o2(y, z)
    
    typedef enum
    {
       yes, no
    } yes_no; /*enumeration type yes_no */
    
    /* pivot is attempted to be different than the smallest value of 3 args */
    static yes_no find_pivot(int *left, int *right, int *pivot_ptr)
    {
       int a, b, c, *p;
       a = *left; /* left value */
       b = *(left + (right - left) / 2); /* middle value */
       c = *right; /* right value */
    
       o3(a, b, c); /* order a, b, c */
       if ( a < b )
       {  /* pivot will be b */
          *pivot_ptr = b;
          return yes;
       }
       if ( b < c )
       {  /* a == b, pivot will be c */
          *pivot_ptr = c;
          return yes;
       }
       for ( p = left +1; p <= right; ++p )
       {  /* trying to find another pivot != left */
          if ( *p != * left )
          {
             *pivot_ptr = (*p < *left) ? *left : *p;
             return yes;
          }
       }
       return no; /* all elements of an array have the same value */
    }
    
    static int *partition(int *left, int *right, int pivot)
    {
       while ( left <= right )
       {
          while ( *left < pivot )
          {
             ++left; /* no action */
          }
          while ( *right >= pivot )
          {
             --right;
          }
          if ( left < right )
          {  /* exchanging value to keep < ordering */
             swap(*left, *right); 
             ++left;
             --right;
          }
       }
       return left;
    }
    
    int count = 0;
    
    void quicksort(int *left, int *right) /* recursive algorithm */
    {
       int *p, pivot;
       ++count;
       if ( find_pivot(left, right, &pivot) == yes )
       {
          p = partition(left, right, pivot); 
          /* moving all elements < pivot to left partition, */
          /* and >= 0 to right partition */
          quicksort(left, p - 1);
          quicksort(p, right);
       }
    }
    
    int main(void)
    {
       int i;
       int a[N] =
       {
          33, 82, 91, 36, 24, 22, 54, 81, 44, 24, 33, 28, 71, 69, 57, 90,
          99,  9, 14, 56,  8, 72, 63, 13, 37, 48,  8,  8, 60, 41, 91, 64,
          12, 46, 23, 14, 58, 89, 70, 63, 27, 74, 46,  3, 24, 76,  2, 28,
          63, 28, 65, 78, 45, 78, 71, 31,  4,  9,  7, 38, 47, 98, 88, 17,
          91, 23, 19, 11, 60, 85, 93, 47, 36, 28, 29, 58, 87, 74, 24, 14,
          35, 98, 20, 12, 62, 65, 78, 75, 46, 46, 48, 94, 72, 18, 78, 59,
          87, 59,  8, 16,
       };
       quicksort(a, a + N -1);
       for ( i = 0; i < N; i++ )
       {
          printf("%2d,%c", a[i], i % 16 == 15 ? '\n' : ' ');
       }
       putchar('\n');
       printf("count = %d\n", count);
       return 0;
    }
    
    /* my output
     2,  3,  4,  7,  8,  8,  8,  8,  9,  9, 11, 12, 12, 13, 14, 14,
    14, 16, 17, 18, 19, 20, 22, 23, 23, 24, 24, 24, 24, 27, 28, 28,
    28, 28, 29, 31, 33, 33, 35, 36, 36, 37, 38, 41, 44, 45, 46, 46,
    46, 46, 47, 47, 48, 48, 54, 56, 57, 58, 58, 59, 59, 60, 60, 62,
    63, 63, 63, 64, 65, 65, 69, 70, 71, 71, 72, 72, 74, 74, 75, 76,
    78, 78, 78, 78, 81, 82, 85, 87, 87, 88, 89, 90, 91, 91, 91, 93,
    94, 98, 98, 99, 
    count = 125
    */
    [edit]
    I had made a number of changes from int to double (since your array was doubles, but the code appeared to be sorting ints). And then I decided to just sort ints instead.
    [/edit]

    I didn't feel like manually entering in 100 values. And [code] [/code] tags make things look nice.
    Last edited by Dave_Sinkula; 05-03-2003 at 04:34 PM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  10. #10
    Registered User
    Join Date
    Apr 2003
    Posts
    9
    Ok, thanks for that, it's helped me out alot!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM