Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Index problem in quick sort.

Posted on 2005-03-07
6
Medium Priority
?
317 Views
Last Modified: 2013-03-25
I'm having trouble with my quick sort function. It seems like it's close to working. I think I may have a problem with the indexs in the partition. Am I close?
HERE IS MY QUICK SORT FUNCTION:
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
void quicksorter(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *));
int partition(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *));
void quick_sort(void *akeys, int n, int size, int (*compare) (const void * , const void *))
{
            char *keys;
        keys= (char *) akeys;
            
            quicksorter(keys, n, size, 0, n-1, compare);                 
}

void quicksorter(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *)){
      register int m;
    char    *keys;
    keys= (char *) akeys;

            if (left < right){
                  m = partition( keys, n, size, left, right, compare);
                  quicksorter( keys, n, size, left, m-1, compare);
                  quicksorter( keys, n, size, m+1, right, compare);            
            }      
}

int partition(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *)){
      char *keys, *swap;
    keys= (char *) akeys;
     
      swap = (char *) malloc(size*sizeof(char));
      int i;
      i = left-1;
      for (int j=left; j < right-1 ;j++){
            if (compare( &keys[j*size], &keys[right*size]) <= 0){
                              i = i+1;
                    memcpy( swap, &keys[j*size], size);  
                    memcpy( &keys[j*size], &keys[i*size], size);
                    memcpy( &keys[i*size], swap, size);        
            }
      }
      return i+1;
}


HERE IS THE TEST FUNCTION:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#include <iostream>
#include <fstream>
#define DEBUG 1
#define      FEW      8
using namespace std;
/* Set DEBUG to 1 to print few element before and after the sort */
/* This piece of code is to assist you. Don't expect comments on what it
   does (it's obvious); If you find it useful use it, otherwise discard it.*/
extern clock_t clock();
void quick_sort(void *, int , int , int (*compare) (const void * , const void *));

int compare(const void  *x,const void  *y)
{
      return(* ((int*)x)-*((int *)y));
}

int main(int argc,char *argv[])
{
      int i,j,n,runs;
      int *ptr,*bptr;
      clock_t t1,t0;
      size_t n_t;
         double elapsed;

      n=1000;runs=1;
        if ( 1 == argc ) {
            cout << "Usage: "  << argv[0] << " size " <<endl;
            exit(1);
      } else {
            n = atoi(argv[1]);
      }
      ptr= (int*) malloc(n*sizeof(int));
      bptr= (int*) malloc(n*sizeof(int));

      n_t =  (size_t) n;

      for(i=0;i<n_t;i++)
          bptr[i]=ptr[i] = (int) (n_t*(random()/((double) INT_MAX)));

      for(i=0;i<n_t;i++)
           ptr[i]=bptr[i] ;
/* Quick Sort sort */
        if (DEBUG) {
        for(i=0;i<FEW;i++)
            cout << ptr[i] << " ";
          cout << "...";
        for(i=n_t-FEW;i<n_t;i++)
            cout << ptr[i] << " ";
          cout << endl;
        }
      elapsed=0.0;
        for(j=0;j<runs;j++){      
         for(i=0;i<n_t;i++) ptr[i] = bptr[i];
         t0=clock();
             quick_sort(ptr,n_t,sizeof(int),compare);
           t1=clock();
         elapsed +=(t1-t0)/((double)CLOCKS_PER_SEC);
      }

        if (DEBUG) {
        for(i=0;i<FEW;i++)
            cout << ptr[i] << " ";
          cout << "...";
        for(i=n_t-FEW;i<n_t;i++)
            cout << ptr[i] << " ";
          cout << endl;
        }
        printf("QuickSort:Elapsed time is %10.8f\n",elapsed/runs);
      for(i=0;i<n_t-1;i++)
           if (ptr[i] > ptr[i+1] )  {
                 cout <<"QuickSort does not sort! \n" <<endl;
        }

      free((void *) ptr);
      free((void *) bptr);
}

0
Comment
Question by:stopher2475
  • 4
  • 2
6 Comments
 
LVL 2

Author Comment

by:stopher2475
ID: 13482709
I forgot to swap the partition element to put the splitter in the middle in partition()
It seems a lot closer now. I think I just have to fix some of the array indexes.

UPDATED QUICKSORT FUNCTION:

#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
void quicksorter(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *));
int partition(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *));
void quick_sort(void *akeys, int n, int size, int (*compare) (const void * , const void *))
{
            char *keys;
        keys= (char *) akeys;
            
            quicksorter(keys, n, size, 0, n-1, compare);                 
}

void quicksorter(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *)){
      register int m;
    char    *keys;
    keys= (char *) akeys;

            if (left < right){
                  m = partition( keys, n, size, left, right, compare);
                  quicksorter( keys, n, size, left, m-1, compare);
                  quicksorter( keys, n, size, m+1, right, compare);            
            }      
}

int partition(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *)){
      char *keys, *swap;
    keys= (char *) akeys;
     
      swap = (char *) malloc(size*sizeof(char));
      int i;
      i = left-1;
      for (int j=left; j < right-1 ;j++){
            if (compare( &keys[j*size], &keys[right*size]) <= 0){
                              i = i+1;
                    memcpy( swap, &keys[j*size], size);  
                    memcpy( &keys[j*size], &keys[i*size], size);
                    memcpy( &keys[i*size], swap, size);        
            }
      }
      memcpy( swap, &keys[(i+1)*size], size);  
      memcpy( &keys[(i+1)*size], &keys[right*size], size);       
      memcpy( &keys[right*size], swap, size);
      
 
      
      return i+1;
}
0
 
LVL 2

Author Comment

by:stopher2475
ID: 13482760
I can't figure out how to reference the arrary to print it in partition.

This gives me memory addresses:
      for (int counter = left; counter < right; counter++){
            cout << (int *)keys[counter];
            cout << endl;
            }
This gives me odd characters:
      for (int counter = left; counter < right; counter++){
            cout << &keys[counter];
            cout << endl;
            }
0
 
LVL 2

Author Comment

by:stopher2475
ID: 13482808
I got it!!!
Finally figured out the indexes. I would have printed the partition during the partition function but I couldn't figure out how to reference them correctly without printing something wierd. If anyone know I would be greatful.
If any one is interested here is the function:

#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <fstream>
using namespace std;
void quicksorter(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *));
int partition(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *));
void quick_sort(void *akeys, int n, int size, int (*compare) (const void * , const void *))
{
            char *keys;
        keys= (char *) akeys;
            
            quicksorter(keys, n, size, 0, n-1, compare);                 
}

void quicksorter(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *)){
      register int m;
    char    *keys;
    keys= (char *) akeys;

            if (left < right){
                  m = partition( keys, n, size, left, right, compare);
                  quicksorter( keys, n, size, left, m-1, compare);
                  quicksorter( keys, n, size, m+1, right, compare);            
            }      
}

int partition(void *akeys, int n, int size, int left, int right, int (*compare) (const void * , const void *)){
      char *keys, *swap;
    keys= (char *) akeys;
      swap = (char *) malloc(size*sizeof(char));      
      int i;
      i = left-1;
      for (int j=left; j < right ;j++){
            if (compare( &keys[j*size], &keys[right*size]) < 0){
                              i = i+1;
                    memcpy( swap, &keys[j*size], size);  
                    memcpy( &keys[j*size], &keys[i*size], size);
                    memcpy( &keys[i*size], swap, size);        
            }
      }
      memcpy( swap, &keys[(i+1)*size], size);  
      memcpy( &keys[(i+1)*size], &keys[right*size], size);       
      memcpy( &keys[right*size], swap, size);
            
      return i+1;
}
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 2000 total points
ID: 13484767
>>>> but I couldn't figure out how to reference them correctly without printing something wierd

Are you using the int arrays from the test program above (brrrr!) ?

If yes, you could print out using the following:

void printArray(const void* keys, int left, int right)
{
     int* pArr = (int*)keys;
     for (int i = left; i <= right; ++i)
          cout << i << ": " << pArr[i] << endl;
}

Note, if you want to be able to print out all kinds of keys you have to pass a function pointer of the printout function - similar to the compare function.

void quicksorter(void *akeys, int n, int size, int left, int right,
                        int (*compare) (const void * , const void *), void (*printout) (const void *, int, int));

You then, would pass the printArray function to quicksorter and partition

Regards, Alex
0
 
LVL 2

Author Comment

by:stopher2475
ID: 13492548
I was trying to add a loop to the partition function so it would print out the sub array in the console and I could see the subarrays and if they were sorting.
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 2000 total points
ID: 13493935
Add a function pointer to a printout function to the argument list of quick_sort, quicksorter and partition:

void quicksorter(void *akeys, int n, int size, int left, int right,
                        int (*compare) (const void * , const void *),void (*printout) (const void *, int, int));

int partition(void *akeys, int n, int size, int left, int right,
                 int (*compare) (const void * , const void *), void (*printout) (const void *, int, int));

void quick_sort(void *akeys, int n, int size,
                       int (*compare) (const void * , const void *), void (*printout) (const void *, int, int));

Then, add the printArray function from above to all calls

     ...
     quick_sort(ptr,n_t,sizeof(int), compare, printArray);
     ...

     ...
     quicksorter(keys, n, size, 0, n-1, compare, printArray);
     ...

     ...
     m = partition( keys, n, size, left, right, compare, printArray);
     quicksorter( keys, n, size, left, m-1, compare, printArray);
     quicksorter( keys, n, size, m+1, right, compare, printArray);          
     ...
 

In partition, you now may use the print function like that:

int partition(void *akeys, int n, int size, int left, int right,
                 int (*compare) (const void * , const void *), void (*printout) (const void *, int, int) )
{
     char *keys, *swap;
    keys= (char *) akeys;
     swap = (char *) malloc(size*sizeof(char));    
     int i;
     i = left-1;
     for (int j=left; j < right ;j++){
          if (compare( &keys[j*size], &keys[right*size]) < 0){
                         i = i+1;
                    memcpy( swap, &keys[j*size], size);  
                    memcpy( &keys[j*size], &keys[i*size], size);
                    memcpy( &keys[i*size], swap, size);        
          }
     }
     memcpy( swap, &keys[(i+1)*size], size);  
     memcpy( &keys[(i+1)*size], &keys[right*size], size);      
     memcpy( &keys[right*size], swap, size);
     
     printout(keys, left, right);    
     return i+1;
}

Regards, Alex
0

Featured Post

Upgrade your Question Security!

Your question, your audience. Choose who sees your identity—and your question—with question security.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses

564 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question