?
Solved

Index problem in quick sort.

Posted on 2005-03-07
6
Medium Priority
?
313 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

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

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
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 additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

800 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