|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Maxim Lanovoy 2:463/1124.6 11 Dec 2001 11:54:30
To : Igor Grigoriev
Subject : Дайте алгоритм быстрой сортировки
--------------------------------------------------------------------------------
IG> Hужен алгоритм быстрой сортировки, желательно реализованный на С,
IG> чтобы сортировал любые элементы, как стандартный qsort. Только,
IG> желательно, не рекурсивный.
Сортировка Хоаре по определению рекурсивная.
/* QSORT.C
* =======
* Quick sort routine from Dr. Dobb's Journal #102 April 1985.
*/
#define STAND 1
#include <stdio.h>
#if STAND
#define MAX_PTRS 500
static char *pp[ MAX_PTRS ];
static int Lev = 0; /* Recusion level */
static int Maxlev = 0; /* Maximum */
#endif
typedef int (* PFI)(); /* Pointer to a function that */
/* returns an int. */
static PFI Comp; /* Pointer to comparsion routine */
static int Width; /* Width of an object in bytes */
/* ------------------------------------------------------------------ */
int argvcmp( slp, s2p )
char **slp,
**s2p;
/* Comparsion routine for sorting an argv like list of pointers
* to strings. Just remove one level of indirection and call strcmp
* to do the comparsion.
*/
{
return( strcmp( *slp, *s2p ) );
}
qsort( base, nel, width, compare )
char *base;
int nel,
width,
(*compare)();
/* Perform a quick sort on an array starting at base.
*/
{
Width = width;
Comp = ( compare == (PFI)0 ) ? &argvcmp : compare ;
if ( nel > 1 )
rqsort( base, base + ( ( nel - 1 ) * width ) );
#if STAND
ptext( nel, base );
#endif
}
/* ------------------------------------------------------------------ */
static rqsort( low, high )
register char *low,
*high;
/* Workhorse function called by the access routine, qsort().
*/
{ char *pivot,
*base;
static char *a, /* Used for exchange, will not be needed */
*b; /* during recusion, so they can be static.*/
static int tmp, /* That way they will not take up stack */
i; /* space. */
base = low ; /* Remember base address of array. */
pivot = high ; /* Partition off the pivot. */
high -= Width;
do
{ while ( low < high && (*Comp)(low, pivot) <= 0 )
low += Width;
while ( low < high && (*Comp)(high, pivot) >= 0 )
high -= Width;
if ( low < high ) /* Exchange low & high */
{
/*
printf( "lev = %d: exchangeing high: <%s> & low <%s>\n",
Lev, *((char **)high), *((char **)low));
*/
for ( b = low, a = high, i = Width; --i >= 0; a++, b++ )
{ tmp = *b; /* Exchange *low and *high */
*b = *a;
*a = tmp;
}
}
} while ( low < high );
if ( low < pivot && (*Comp)(low, pivot) > 0 )
for ( b = low, a = pivot, i = Width; --i >= 0; a++, b++ )
{ tmp = *b; /* Exchange *low and *pivot */
*b = *a;
*a = tmp;
}
low += Width;
if ( high - base < pivot - low )
{
if ( low < pivot )
rqsort( low, pivot );
if ( base < high )
rqsort( base, high );
}
else
{
if ( base < high )
rqsort( base, high );
if ( low < pivot )
rqsort( low, pivot );
}
}
/* ------------------------------------------------------------------ */
#if STAND
static ptext( argc, argv )
int argc;
char **argv;
/* Print out argv, one element per line */
{ register int i;
for ( i = 1; --argc >= 0; i++ )
printf( "%s\n", *argv++ );
}
main( argc, argv )
int argc;
char **argv;
{ char *malloc(),
*wk;
if ( argc > 1 )
qsort( ++argv, --argc, sizeof(PFI), 0 );
else
{ argc = 0;
while ( 1 )
{ if ( ( wk = malloc( 80 ) ) == 0 )
{ printf( "\nUnable to Malloc\n" );
exit( 0 );
}
if ( gets( wk ) == NULL )
break;
pp[ argc++ ] = wk ;
if ( argc > MAX_PTRS )
{ printf( "\nToo many items for QSORT\n" );
exit( 0 );
}
}
printf("\r\n" );
qsort( pp, argc, sizeof(PFI), 0 );
}
}
#endif
НННННННННН Конец qsort1.c НННННННННН
---
С уважением, Максим Лановой (*mailto:* maxim(_*at_*)lanovoy.kiev.ua)
lanovoy(_*at_*)ln.ua
--- np: Iron Maiden - Childhood's End [Fear of the Dark]
* Origin: [*Ария*] [*Hаутилус*] [*Blind Guardian*] [*Queen*] (2:463/1124.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Дайте алгоритм быстрой сортировки 
