HELP me with my Qsort Program

This is a discussion on HELP me with my Qsort Program within the C Programming forums, part of the General Programming Boards category; Code: #include <stdio.h> #define maxsize 10 void quicksort (int a, int b); //void mergesort (); float ES26[11]; int i, j, ...

  1. #1
    Registered User
    Join Date
    Sep 2010
    Posts
    5

    HELP me with my Qsort Program

    Code:
    #include <stdio.h>
    #define maxsize 10
    
    void quicksort (int a, int b);
    //void mergesort ();
    
    float ES26[11];
    int i, j, k, x=1, mean, median, mode;
    float *ptr, sum;
    
    int main ()
    {
        printf("Input at most 10 floating point numbers, each entry followed by ENTER. \nInput 0 if you want to stop:\n");
        for (i=1, j=1; j==1 || i==10; i++)
        {  
            printf("%d) ", i);
            scanf("%f", &ES26[i]);
            ptr=&ES26[i];
            
            if (*ptr==0)
            {
                x=i-1;
                j=2;
            }
            if (i==10)
            {
                x=i;
                j=2;
            }
        }
        
        if (x==2 || x==4 || x==6 || x==8 || x==10)
        {
        printf("\nYou entered %i valid entries.", x);
        ptr = &ES26[i];
        quicksort(0, x-1);
        
        printf("\nSupposed to Quicksort.");
        }
    
        if (x==1 || x==3 || x==5 || x==7 || x==9)
        {
        printf("\nYou entered %i valid entries.", x);
        //meregesort
        
        printf("\nSupposed to Mergesort.");
        }
        
        //ptr = &ES26[i];
        
        for (i=1; i<=x; i++) //for printing
        {
            ptr=&ES26[i];
            printf("\nEntry %i is %f", i, *ptr);
            sum = sum + *ptr;
        }
            printf("\nThe mean is %f", sum/x);
        
        getchar();
        getchar();
        getchar();
        getchar();
    }
    
    
    void quicksort(int a, int b)
    {
      ptr=&ES26[a];
      //*ptr=ES26[a];
      int rtidx=0, ltidx=0, k=a, l=0;
      float leftarr[maxsize], rtarr[maxsize];
      //float pivot = ES26[a];
      
      if (a==b) return;
      while (k<b)
      {
        ++k;
        
    	 if(ptr[k] < ptr[a])
    	 {
    	  leftarr[ltidx] = ptr[k];
    	  ltidx++;
    	  }
    	  
    		else
    		{
    		rtarr[rtidx] = ptr[k];
    		rtidx++;
            }
      }
     
    	 k=a; //reset k to a
    	 
    	 *ptr=ES26[a];
    	 for(l=0; l<ltidx; ++l)
    	 
         ptr[k++] = leftarr[l];
    	 ptr[k++] = *ptr;
    	 
    	 for(l=0; l<rtidx; ++l)
         ptr[k++] = rtarr[l];
    	 
    	 if(ltidx>0)
         quicksort(a, a+ltidx-1);
    	 
         if(rtidx>0)
         quicksort(b-rtidx+1, b);
    	 }
    here is an example of what I get if i run my program:

    Input at most 10 floating point numbers, each entry followed by ENTER.
    Input 0 if you want to stop:
    1> 11.23
    2> 43.553
    3> 196.4673
    4> 0.8874
    5> 23.67
    6> 90.5
    7> 0

    You entered 6 valid entries.
    Supposed to Quicksort.
    Entry 1 is 11.230000
    Entry 2 is 11.230000
    Entry 3 is 23.670000
    Entry 4 is 11.230000
    Entry 5 is 196.467300
    Entry 6 is 90.500000

    Can somebody help me point out where the mistake is? Thanks a lot!

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Let's start with a nice Quicksort example, and I strongly suggest you use this as a template for any Quicksort program you use, in the future. It's clear, it's FAST, and easy to optimize further, if you desire.

    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--;
                 /*swap(A, i, j);   //this line works fine, if you want a separate swap function.
                  Oddly, on large N, using swap() gives the same time, as
                 using the swap code below 
                 */
        if (i<=j) {        //we need to swap two values
            temp= A[i];
            A[i]= A[j];
            A[j]=temp;
          i++;
          j--;
        }
      } while (i<=j);
    
      /* select the smaller sub array to finish sorting, first - prevents stack overflow */    
      if (lo < j) quicksort(A, lo, j);
      if (i < hi) quicksort(A, i, hi);
    }
    What do you notice, right off - there are very few variables involved:

    i, j, pivot, and temp, and that's it. Just the required 3 parameters for the function.

    There are no pointers involved - other than the array name, which is being passed in (so it's always a pointer). The compiler will handle the pointer conversions that are used by C, "under the hood". For heaven's sake, as a beginner, don't go there!

    You don't need (and shouldn't use), auxiliary arrays (left and right arrays in your code), in Quicksort. That just throws more data, out of the fast cache memory, and again, make the programming waters, murky. You're thinking of a version of Merge sort - and this is no Merge sort.

    << This is Sparta!! >>


    OK, back to the program.

    Try this Quicksort template, and you'll soon have it working for you. Glad to assist there.
    Last edited by Adak; 09-30-2010 at 07:42 PM.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    You'll no doubt learn the most by stepping through your own code.
    Start learning to use your debugger. You cant get very far in programming without learning how to use a debugger.

    If you have trouble doing that, tell us what you're using and what the problem is.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Issue with program that's calling a function and has a loop
    By tigerfansince84 in forum C++ Programming
    Replies: 9
    Last Post: 11-12-2008, 12:38 PM
  2. Need help with a program, theres something in it for you
    By engstudent363 in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 12:41 PM
  3. Replies: 4
    Last Post: 02-21-2008, 09:39 AM
  4. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM

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