OJ Board

Posted: **Thu Jan 16, 2003 2:41 pm**

Hey all,
I need to know to use the qsort() function.. especially the sort_function(const void *a, const void *b) that is used by qsort()...
Thank you

Posted: **Fri Jan 17, 2003 12:43 am**

go to cplusplus.com/ref and check out what it has about it... what you need to do when you write your compare function is to cast the parameters to the type you use and then make your comparison...

Posted: **Fri Jan 17, 2003 8:41 am**

This is my complete code for 612:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
  char a[55];
  int pos;
  int inv;
} DNA;

int cmp( DNA *a, DNA *b ) {
  if ( a->inv != b->inv ) {
    return a->inv - b->inv;
  }
  return a->pos - b->pos;
}

int main(){
  int N, l, num, i, j, t, k, f = 0;
  DNA list[102];
  int cmp();
  
  scanf("%d", &N );
  while ( N -- ) {
    if ( f ) putchar('\n');
    f = 1;
    scanf("%d %d", &l, &num );
    for ( i = 0; i < num; i++ ) {
      scanf("%s", list[i].a );
      list[i].pos = i;
      t = strlen( list[i].a );
      list[i].inv = 0;
      for ( j = 0; j < t; j++ )
        for ( k = j + 1; k < t; k++ )
          list[i].inv += ( list[i].a[j] > list[i].a[k] );
    }
    qsort( list, num, sizeof( DNA ), cmp );
    for ( i = 0; i < num; i++ )
      printf("%s\n", list[i].a );
  }

  return 0;
}

The man pages are pretty good, but hey, you can never have enough sample code...

Posted: **Tue Jan 21, 2003 8:30 pm**

My advice is to code quick_sort() and Compare() functions as your own style. It's not very diffucult.

I used recursive approach for quick sort implementation. If anybody have done it in iterative way can you share the algorithm with me ???

Posted: **Wed Jan 22, 2003 9:24 am**

I think that qsort() function from standard library is very usefull and we could not code own implementation of this

)

Dominik Michniewski

PS. I think, that quick_sort() (iterative version) could be done with using stack to remember parts of table to sort ... but I think, that recursive version of it is simpler

))

And to compare function. It's header should be:

Code: Select all

int <name>(const void *<param1>,const void *<param2>)

I'm not sure about behaviour other functions (with C), but for C++ I see such line of code:

Code: Select all

qsort(table,size,size_of_element,strcmp)

Maybe in C++ any two parameter function could be compare function

only if it have the same parameters as we sort

))

Posted: **Wed Jan 22, 2003 12:33 pm**

but if you're doing it in C++, you might as well as use the sort() function, or stable_sort().. though they don't use quicksort. I believe sort uses introsort, though not too sure what they use for stable_sort..

Posted: **Fri Jan 24, 2003 1:02 pm**

The standard doens't tell what implementation to use for STL sort() and stable_sort(), but for example SGI's implementation uses (as Larry mentioned) introsort for sort() (earlier versions used a 3-median quicksort) and merge sort for stable_sort().

Attached a quote from the SGI STL site ( http://www.sgi.com/tech/stl/ ):

[2] Earlier versions of sort used the quicksort algorithm (C. A. R. Hoare, Comp. J. 5, 1962), using a pivot chosen by median of three (R. C. Singleton, CACM 12, 1969). Quicksort has O(N log(N)) average complexity, but quadratic worst-case complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.) The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average.

OJ Board

Quick Sort

Quick Sort