Пример K&R Qsort с беспорядком Указателей и Массивов

Это прекрасный фрагмент кода!

Прежде всего, важно, чтобы вы понимали идею быстрой сортировки:

1) Возьмите список чисел.

2) Выберите один, назовите его X.

3) Составьте два списка, один из всех чисел меньше X, а один из всех чисел больше.

4) Сортируйте числа меньше X. Сортируйте числа больше X.

Идея состоит в том, что если нам повезет и мы выберем хорошее значение для X, тогда список чисел меньше X будет того же размера, что и список чисел больше X. Если мы начнем с 2 * N + 1 чисел, то мы получаем два списка из N чисел. Каждый раз мы надеемся разделить на два, но нам нужно отсортировать N чисел. Сколько раз мы можем разделить N на два? Это журнал (N). Итак, мы сортируем N Log (N) раз. Это здорово!

Что касается того, как работает код, вот краткое изложение с небольшим наброском. Мы выберем небольшой массив :)

вот наш массив: [DACBE]

в начале, left = 0, указывает на D. right = 4, теперь указывает на E.

, следуя коду , с вашей маркировкой:

[1] swap (v, 0,2) [DACBE] -> [CADBE]

мы заменили выбранное значение местами и поместили его в начало массива.

[2] last = 0

это немного умно ... мы хотим сохранить счетчик, чтобы мы знали, какие значения были больше, а какие меньше ... вы увидите, как это продвигается

[3] для (i = 1; i <= 4; i ++)

для всех оставшихся элементов в списке ...

[4] if ((* comp) (v [i], 'C') <0)

если значение в i МЕНЬШЕ чем 'C' ...

[5] swap (v, ++ last, i);

поместите его в начало списка!

давайте запустим код для 3,4,

[CADBE]

if ('A' <'C')

swap ('A', 'A') (И УВЕЛИЧЕНИЕ ПОСЛЕДНЕГО!)

[CADBE] -> [CADBE] (без изменений)

last = 1

i = 2:

[CADBE]

, если ('D' <'C')

не удается. двигайтесь дальше.

i = 3:

[CADBE]

if ('B' <'C')

swap ('B', 'D') И приращение последним!

[CADBE] -> [CABDE] (смотрите, это сортировка!)

last = 2

i = 4:

[CABDE]

, если ('E' <'C')

не удается. двигаться дальше.

Хорошо, туз. так что цикл дает [CABDE], last = 2 ('B')

Теперь строка [6] .... swap (left, last) ... это swap ('C', 'B') [CABDE] -> [BACDE]

Теперь волшебство этого ... оно частично отсортировано! BA

Итак, теперь мы сортируем подсписки !!

[7] -> [BA] -> [AB]

так

[BACDE] -> [ABCDE]

[8] -> [DE] -> [DE]

так

[ABCDE] -> [ABCDE]

и готово!

волшебные полезные ключевые слова google: QuickSort

например google: как работает быстрая сортировка показывает это объяснение: http://www.angelfire.com/pq /jamesbarbetti/articles/sorting/001a_HowQuicksortWorks.htm, среди прочего.

По сути, код применяет вариант быстрой сортировки к элементам между указанными левой и правой границами .

Для строк, которые вы определили:

1. поменяйте местами средний элемент с первым ( левым ). он станет «точкой опоры».

2. отслеживайте границу между большими и меньшими элементами. здесь находится точка поворота.

3. для каждого элемента после первого,
4. , если он меньше, чем точка поворота,

5. перемещает его перед первым большим элементом.

6. перемещает точку поворота на место.

7. рекурсивно применяет qsort к элементам перед поворотом. (меньшие)

8. рекурсивно применяют qsort к элементам после поворота. (более крупные)

Попробуйте сами применить код к списку чисел, и посмотрите, имеет ли он больше смысла, тогда ....

K&R quick - это пример отличного кодирования, но не лучший пример того, как работает quicksort. Цель предварительной подмены не интуитивно понятна, а подмена идентичности неэффективна и сбивает с толку. Я написал программу, чтобы прояснить это. Комментарии к коду объясняют проблемы.

Я скомпилировал и протестировал только под Linux, но у Visual Studio не должно быть проблем с этим обычным консольным приложением.

/***************************** QUICK.CPP ***************************************
Author: David McCracken
Updated: 2009-08-14

Purpose: This illustrates the operation of the quicksort in K&R "The C 
Programming Language" (second edition p. 120). Many programmers are frustrated 
when they attempt to understand quicksort in general from this version, which 
was clearly not intended as a tutorial on quicksort but on the use of pointers 
to functions. My program modifies the original to work only on ints in order to 
focus on the sorting process. It can print the global list and recursive 
sublist at each change to trace the sorting decision process. My program also 
clarifies two confusing aspects, both involving unexplained swapping, of the 
original by comparing its operation to that of two further modified versions.

One confusing thing that the original does is to swap an item with itself.
The code (modified for ints only)  is:

last = left;
for( i = left+1 ; i <= right ; i++ )
   if(  v[i] < v[ left ] )
       swap( v[ ++last ], v[ i ]);
Note that left and v[ left ] are loop-invariant. v[ left ] is the pivot. 

A superfluous swap is performed on all values less than the pivot without an 
earlier value greater than the pivot. For example, given  sublist (after 
preswap) 9,8,5,7,4,6, initially i = left + 1, selecting 8. Since this is less 
than 9, last is incremented to point to the same element as i (selecting 8) and 
a superfluous swap is performed. At the next iteration, last selects 8 while i 
selects 5 and 5 is swapped with itself. This continues to the end of the 
sublist. The sorting function krQuick2 is identical to krQuick but tests ++last 
against i to avoid superfluous swapping. This certainly yields better 
performance for practically no cost but, more importantly, helps to clarify 
just what the code is trying to do, which is to find and swap a value that is 
larger than the pivot with one that occurs later and is smaller than the pivot. 

A second source of confusion is the purpose of the preswap, where the midpoint 
value is swapped with the left-most. Since this is done without regard to 
value, it cannot decrease entropy. In fact, it does exactly the opposite in the 
very important case of a sublist that is already sorted, which normally makes 
quicksort perform badly. This action deliberately unsorts a sorted list and 
essentially does nothing to an unsorted one. This simple and cheap action 
substantially improves average and worst case performance, as demonstrated by 
the third variation, quick3, which just removes the preswap from krQuick2. 
quick3 demonstrates that the preswap is not required; in fact that any value 
can be chosen from the list to serve as the pivot. Only in the most unsorted 
cases does quick3 exhibit slightly better performance than krQuick2 by virture 
of skipping the preswap. With increasing initial order, the performance of 
krQuick2 steadily improves over quick3.

Some confusion may also come from the testing of v[i] against v[left]. left and 
v[ left ] are loop-invariant. An optimizing compiler should recognize this and 
hoist the value out of the loop, but this loop-invariance is not immediately 
obvious to someone studying this as an example of quicksort. During the swap 
loop, v[left] serves only to hold the pivot value. An automatic could just as 
easily hold the value and its purpose would be more clear. However, the code is 
an example of indirection. We don't know what the list items are but we can be 
sure that any one of them can fit into v[ left ] and that the swap function can 
put it there. Thus, the one preswap operation does three things; it randomizes 
a sorted sublist; it conveniently copies the pivot to a place where it won't be 
subject to swapping; and it fills the hole in the loop left by extracting the 
pivot. It does all of this without even knowing what the elements are and with 
a function that we already have. This amazing programming feat is well worth 
studying but not in the interest of understanding quicksort.

                         HOW TO USE THIS PROGRAM
There are three general variables, the function, the data to be sorted, and what
to display. 

The simplified K&R original function, krQuick, is function 0. Function 1, 
krQuick2, is krQuick with identity swaps removed. Function 2, quick3, is 
krQuick2 without preswap.

The data to be sorted can be any one of five builtin lists or all of them or
a space-delimited list of decimal ints entered on the command line.

The displayed information affords a trace of the function's operation. In all 
cases, the list is displayed before and after sorting, and executing statistics
are reported. If SHOW_NOTHING then nothing else is reported. If SHOW_GLOBAL, 
the changing full list is displayed at each invocation of the recursive sort 
function. If SHOW_LOCAL1, the sublist passed to the function is displayed before
it is modified. If SHOW_LOCAL, the sublist is displayed after each swap. If 
SHOW_INDEX, the indices involved in swapping and the values at those indices 
are shown before the swap occurs.These selections correspond to the SHOW_ enum 
and are culmulative flags.

By default, all three functions are applied in succession to all five builtin 
data lists, with SHOW_NOTHING. This is useful for comparing the performance of 
the functions. For example, it shows that on the unordered list 11 0 10 1 9 2 8 
3 7 4 6 5 quick3 uses 37 compares and 30 swaps while krQuick2 uses 38 compares 
and 44 swaps. However, on the ordered list 0 1 2 3 4 5 6 7 8 9 10 11 quick3
uses 66 compares and 22 swaps while krQuick2 uses 25 compares and 28 swaps.

Command line arguments alter the content but not the order of operation. In all
cases, each selected function is applied to all selected data lists.
Command arguments are case-insensitive: F function selector, D data selector,
and S show what map. Each is followed without space by a single character.
F0, F1, F2, FA select function 0, 1, or 2 only or all functions.
D0, D1, D2, D3, D4, DA select builtin data list 0, 1, 2, 3, or 4 only or all.
S0 (default) shows no extra information.
S1 (GLOBAL) shows the full list (without "GLOBAL" legend) at each invocation.
S2 (LOCAL1) shows the sublist before processing. 
S3 (GLOBAL+LOCAL1) 
S4 (LOCAL) shows the sublist after each swap. It also shows the sublist before
    processing.
S8 (INDEX) shows indices but these would never be shown without at least LOCAL,
    which can't be combined with 8 in the single-digit argument.
SA (All) 
Note that the Local legend includes a numeric suffix to identify where in the
point in the code that is reporting.
The most useful S formats are S1, S5, and SA (S0 is default).

After any F and S arguments, any space-delimited list of numbers will be taken
as the data list. Any D argument is ignored. For example:
quick 20 21 15 12 40 0
applies all three functions to the data, reporting only the unsorted and sorted
full lists and operational statistics.
quick f0 sa 20 21 15 12 40 0
applies only function 0 krQuick to the data, reporting everything. 

*******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// ======================== DATA AND DECLARATIONS ===============================
#define DIM(A) ( sizeof A / sizeof A[0])
typedef unsigned int UINT;

enum { SHOW_NOTHING, SHOW_GLOBAL = 1, SHOW_LOCAL1 = 2, SHOW_LOCAL = 4, 
       SHOW_INDEX = 8, SHOW_ALL = 0xFF };

int showWhat = SHOW_NOTHING;

int list0[] = { 4,0,2,5,1,3 };
int list1[] = { 0,1,2,3,4,5,6,7,8,9,10,11 };
int list2[] = { 11,10,9,8,7,6,5,4,3,2,1,0 };
int list3[] = { 11,9,7,5,3,1,0,2,4,6,8,10 };
int list4[] = { 11,0,10,1,9,2,8,3,7,4,6,5 };
static struct { int *list; int cnt; } lists[] = 
{ 
    { list0, DIM( list0 )},
    { list1, DIM( list1 )},
    { list2, DIM( list2 )},
    { list3, DIM( list3 )},
    { list4, DIM( list4 )},
};

int total[ 1000 ];
int totalCnt;
int *userData = 0;
int userDataLen = 0;

int recursion;  // Current recursion level.
int calls;      // Number of times the sort function is called.
int depth;      // Maximum recursion level.
int swaps;      // Count of swaps.
int compares;   // Count of list item compares.
int totCalls;
int totDepth;
int totCompares;
int totSwaps;

void (*sortFunc)( int *list, int left, int right );

char dArg = 'A'; // command line argument selects 0,1,2,3,4, or A
int dataList; // If dArg is numeric, this is its int value.

//============================== FUNCTIONS =====================================

// ------------------------------ indent --------------------------------------
// Print two spaces for each level of recursion to indent subsequent print 
// output.
// ............................................................................
void indent( void )
{
    for( int indent = 1 ; indent < recursion ; indent++ )
        printf( "  " );
}

// -------------------------------- show ---------------------------------------
// Print the given int list according to the global control setting showWhat 
// and the given local identification. This may print nothing or the global 
// list or the local sublist. It may or may not print the legend GLOBAL or 
// LOCALx where x is the local ID, which tells at what point in the sort code 
// we are showing the sublist.
// Returns: Nothing
// Arguments:
//- int *ia points to the int list.
//- int cnt is the number of elements in the list.
//- int local tells the local point in the sort routine if greater than 0. 0 
// indicates that this is global. In either case, format is controlled by
// showWhat. If local is -1, the list is printed unconditionally and without
// any legend.
// Global:
//- showWhat bitmapped control word
//-- 0 (SHOW_NOTHING) This is the complete value, not a bit flag.
//-- 1 (SHOW_GLOBAL) Print the list if local is 0. If any other bit is also
// set, the GLOBAL legend is printed before the list.
//-- 2 (SHOW_LOCAL1) Print the list only if local is 1.
//-- 3 (SHOW_LOCAL) Print the list if local is 1 or greater.
//
// ...................... notes .............................................
//                     SHOW_NOTHING
// This exists because the callers don't test showWhat before calling. If we 
// only want to show the initial unsorted list and final sorted version then 
// SHOW_NOTHING blocks all print output from the sort function. The control 
// function calls show with local = -1 to print the list.
// ..........................................................................
void show( int *ia, int cnt, int local )
{
    if( local >= 0 )
    {
        switch( showWhat )
        {
        case SHOW_NOTHING:
            return;
        case SHOW_GLOBAL:   // Only SHOW_GLOBAL
            if( local > 0 )
                return;     // This is a local
            break;          // Print list without legend.
        default: // Some combination of SHOW_GLOBAL, SHOW_LOCAL1, SHOW_LOCAL
            if( local == 0 ) // global
            {
                if( ( showWhat & SHOW_GLOBAL ) == 0 )
                    return;
                printf( "GLOBAL " );
            }
            else if( showWhat & SHOW_LOCAL || ( showWhat & SHOW_LOCAL1 && local == 1 ))
            {
                indent();
                printf( "Local%d: ", local );
            }
            else
                return;
        }
    }
    for( int *end = ia + cnt ; ia < end ; ia++ )
        printf( "%d ", *ia );
    putchar( '\n' );
}

// -------------------------------- swap ---------------------------------------
void swap( int *p1, int *p2 )
{
    int temp = *p2;
    *p2 = *p1;
    *p1 = temp;
    ++swaps;
}

// ------------------------------ krQuick --------------------------------------
// K&R's quick function modified to handle only integers and to use inline 
// numeric comparison instead of an indirect comp function.
// .............................................................................
void krQuick( int *list, int left, int right )
{
    int i, last;

    ++calls;
    if( recursion > depth )
        depth = recursion; // At first call recursion = 0 and depth is 0, i.e. no recursion yet.
    ++recursion;
    show( total, totalCnt, 0 ); // GLOBAL
    show( list + left, right - left + 1, 1 ); // LOCAL
    if( left < right )
    {
        swap( list + left, list + (left + right) / 2 );
        ++swaps;
        show( list + left, right - left + 1, 2 );
        last = left;
        for( i = left + 1 ; i <= right ; i++ )
        {
            ++compares;
            if( list[ i ] < list[ left ])
            {
                if( showWhat & SHOW_INDEX )
                {
                    indent();
                    printf( "i=%d @i=%d left=%d @left=%d last=%d\n", 
                      i, list[i], left, list[ left ], last );
                }
                swap( list + ++last, list + i );
                show( list + left, right - left + 1, 3 );
                ++swaps;
            }
        }
        swap( list + left, list + last );
        show( list + left, right - left + 1, 4 );
        ++swaps;
        krQuick( list, left, last - 1 );
        krQuick( list, last + 1, right );
    }
    --recursion;
}

// ------------------------------- krQuick2 ------------------------------------
// K&R's quick function modified as in krQuick plus elimination of identity 
// swaps.
// .............................................................................
void krQuick2( int *list, int left, int right )
{
    int i, last;

    ++calls;
    if( recursion > depth )
        depth = recursion; // At first call recursion = 0 and depth is 0, i.e. no recursion yet.
    ++recursion;
    show( total, totalCnt, 0 ); // GLOBAL
    show( list + left, right - left + 1, 1 ); // LOCAL
    if( left < right )
    {
        swap( list + left, list + (left + right) / 2 );
        ++swaps;
        show( list + left, right - left + 1, 2 );
        last = left;
        for( i = left + 1 ; i <= right ; i++ )
        {
            ++compares;
            if( list[ i ] < list[ left ] && ++last != i )
            {
                if( showWhat & SHOW_INDEX )
                {
                    indent();
                    printf( "i=%d @i=%d left=%d @left=%d last=%d\n", 
                      i, list[i], left, list[ left ], last );
                }
                swap( list + last, list + i );
                show( list + left, right - left + 1, 3 );
                ++swaps;
            }
        }
        swap( list + left, list + last );
        show( list + left, right - left + 1, 4 );
        ++swaps;
        krQuick2( list, left, last - 1 );
        krQuick2( list, last + 1, right );
    }
    --recursion;
}

// ------------------------------------ quick3 ---------------------------------
// krQuick2 modified to not do the preswap. In the K&R original, the purpose of
// the preswap is to introduce randomness into a presorted sublist. The sorting
// result is not changed by eliminating this but the performance degrades with
// more compares and swaps in all cases between average and worst. Only near the
// best case does eliminating the preswap improve performance.
// ............................................................................
void quick3( int *list, int left, int right )
{
    int i, last;

    ++calls;
    if( recursion > depth )
        depth = recursion; // At first call recursion = 0 and depth is 0, i.e. no recursion yet.
    ++recursion;
    show( total, totalCnt, 0 ); // GLOBAL
    show( list + left, right - left + 1, 1 ); // LOCAL
    if( left < right )
    {
        last = left;
        for( i = left + 1 ; i <= right ; i++ )
        {
            ++compares;
            if( list[ i ] < list[ left ] && ++last != i )
            {
                if( showWhat & SHOW_INDEX )
                {
                    indent();
                    printf( "i=%d @i=%d left=%d @left=%d last=%d\n", 
                      i, list[i], left, list[ left ], last );
                }
                swap( list + last, list + i );
                show( list + left, right - left + 1, 3 );
                ++swaps;
            }
        }
        swap( list + left, list + last );
        show( list + left, right - left + 1, 4 );
        ++swaps;
        quick3( list, left, last - 1 );
        quick3( list, last + 1, right );
    }
    --recursion;
}

static struct { void (*func)( int *list, int left, int right ) ; char *name ; } sortFuncs[] =
{
    { krQuick, (char*)"krQuick" }, 
    { krQuick2, (char*)"krQuick2 (no identity swaps)" },
    { quick3, (char*)"quick3 (no preswaps)" }
};

// ------------------------------------ sortOne --------------------------------
// Set up performance counters, invoke the currently selected sort on the current
// data list, and print the performance (for this one case of selected function
// applied to selected data list).
// .............................................................................
void sortOne( void )
{
    recursion = 0;
    calls = 0;
    depth = 0;
    swaps = 0;
    compares = 0;
    show( total, totalCnt, -1 );
    sortFunc( total, 0, totalCnt - 1 );
    show( total, totalCnt, -1 );
    printf( "Calls = %d, depth = %d, compares = %d, swaps = %d\n", 
      calls, depth, compares, swaps );
    printf( "---------------------------------\n" );
}

// ---------------------------- sortOneSet -------------------------------------
// Purpose: Apply the currently selected sort function to one data list.
void sortOneSet( int idx )
{
    if( idx < 0 )
    {
        totalCnt = userDataLen;
        memcpy( total, userData, totalCnt * sizeof( int ));
    }
    else
    {
        totalCnt = lists[ idx ].cnt;
        memcpy( total, lists[ idx ].list, totalCnt * sizeof( int ));
    }   
    sortOne();
    totCalls += calls;
    totDepth += depth;
    totCompares += compares;
    totSwaps += swaps;
}

// ------------------------- testOneFunc ---------------------------------------
// Purpose: Apply the selected function to one or all data lists.
// Returns: Nothing
// Arguments: int sel is 0,1,or 2, selecting krQuick, krQuick2, or quick3.
// Globals: char dArg is the data list selector command line argument. It is '0',
// '1', '2', or 'A'. 'A' selects all data lists. Otherwise, int dataList is the
// int value of dArg, which has already been translated for us by the command
// line processor.
// .............................................................................
void testOneFunc( int sel )
{
    totCalls = 0;
    totDepth = 0;
    totCompares = 0;
    totSwaps = 0;
    sortFunc = sortFuncs[ sel ].func;
    printf( "====== %s ======\n", sortFuncs[ sel ].name );

    if( userDataLen != 0 )
        sortOneSet( -1 );
    else if( dArg == 'A' )
    {
        for( UINT idx = 0 ; idx < DIM( lists ) ; idx++ )
            sortOneSet( idx );
        printf( "Total: calls = %d, depth = %d, compares = %d, swaps = %d\n",
          totCalls, totDepth, totCompares, totSwaps );
    }
    else 
        sortOneSet( dataList );
}

// --------------------------------- main --------------------------------------
// Purpose: Process command line arguments, set up show (print output) and data 
// list selectors, and invoke testOneFunc either once for the selected function 
// or for each of the three functions.
// .............................................................................
int main( int argc, char **argv )
{
    char    *cp;
    char    fArg = 'A'; // function selector 0,1,2,A
    UINT    idx;

    showWhat = SHOW_NOTHING;
    dArg = 'A';
    for( int cnt = 1 ; cnt < argc ; cnt++ )
    {
        cp = argv[ cnt ];
        switch( toupper( *cp ))
        {
        case 'F':
            fArg = toupper( cp[1] );
            break;
        case 'D':
            dArg = toupper( cp[1] );
            if( dArg != 'A' )
            {
                dataList = dArg - '0';
                if( dataList < 0 || dataList >= (int)DIM( lists ))
                {
                    printf( "Error: bad data list selector %c\n", dArg );
                    return 1;
                }
            }
            break;
        case 'S': // show selector matches bit-mapped showWhat or N or A
            ++cp;
            if( *cp != 0 || toupper( *cp ) != 'N' )
            {
                if( toupper( *cp ) == 'A' )
                    showWhat = SHOW_ALL;
                else
                    showWhat = atoi( cp );
            }
            break;
        default:
            if( !isdigit( *cp ))
            {   
                printf( "Error: There is no option %c\n", *cp );
                return 1;
            }
            for( idx = 0 ; idx < DIM( total ) && cnt < argc ; idx++, cnt++ )
                total[ idx ] = atoi( argv[ cnt ] );
            userData = (int*)malloc( sizeof( int ) * idx );
            if( userData == 0 )
            {
                printf( "Error: Unable to allocate memory for data list\n" );
                return 2;
            }
            memcpy( userData, total, sizeof( int ) * idx );
            userDataLen = idx;
        }
    }
    switch( fArg )
    {
    case 'A':
        for( UINT sfi = 0 ; sfi < DIM( sortFuncs ) ; sfi++ )
            testOneFunc( sfi );
        break;
    case '0':
    case '1':
    case '2':
        testOneFunc( fArg - '0' );
        break;
    default:
        printf( "Error: bad function selector %c\n", fArg );
        return 1;
    }
    return 0;
}

Results of quick
This uses all defaults, which is most useful for comparing the performance
of the three different functions.

====== krQuick ======
4 0 2 5 1 3 
0 1 2 3 4 5 
Calls = 7, depth = 2, compares = 8, swaps = 20
---------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 3, compares = 25, swaps = 48
---------------------------------
11 10 9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 17, depth = 5, compares = 30, swaps = 62
---------------------------------
11 9 7 5 3 1 0 2 4 6 8 10 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 13, depth = 5, compares = 33, swaps = 56
---------------------------------
11 0 10 1 9 2 8 3 7 4 6 5 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 6, compares = 38, swaps = 60
---------------------------------
Total: calls = 67, depth = 21, compares = 134, swaps = 246
====== krQuick2 (no identity swaps) ======
4 0 2 5 1 3 
0 1 2 3 4 5 
Calls = 7, depth = 2, compares = 8, swaps = 16
---------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 3, compares = 25, swaps = 28
---------------------------------
11 10 9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 17, depth = 5, compares = 30, swaps = 52
---------------------------------
11 9 7 5 3 1 0 2 4 6 8 10 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 13, depth = 5, compares = 33, swaps = 46
---------------------------------
11 0 10 1 9 2 8 3 7 4 6 5 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 6, compares = 38, swaps = 44
---------------------------------
Total: calls = 67, depth = 21, compares = 134, swaps = 186
====== quick3 (no preswaps) ======
4 0 2 5 1 3 
0 1 2 3 4 5 
Calls = 7, depth = 3, compares = 10, swaps = 10
---------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 23, depth = 11, compares = 66, swaps = 22
---------------------------------
11 10 9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 23, depth = 11, compares = 66, swaps = 22
---------------------------------
11 9 7 5 3 1 0 2 4 6 8 10 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 7, compares = 46, swaps = 54
---------------------------------
11 0 10 1 9 2 8 3 7 4 6 5 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 19, depth = 6, compares = 37, swaps = 30
---------------------------------
Total: calls = 87, depth = 38, compares = 225, swaps = 138

*******************************************************************************

Results of quick f0 s5 d1
S5 format is best for displaying how the sublist changes during sorting. Since 
LOCAL is displayed only after a swap, superfluous identity swaps (many in this 
example) are readily apparent.

====== krQuick ======
0 1 2 3 4 5 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
Local1: 0 1 2 3 4 5 6 7 8 9 10 11 
Local2: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local4: 0 1 2 3 4 5 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
  Local1: 0 1 2 3 4 
  Local2: 2 1 0 3 4 
  Local3: 2 1 0 3 4 
  Local3: 2 1 0 3 4 
  Local4: 0 1 2 3 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 0 1 
    Local2: 0 1 
    Local4: 0 1 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 1 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 3 4 
    Local2: 3 4 
    Local4: 3 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
  Local1: 6 7 8 9 10 11 
  Local2: 8 7 6 9 10 11 
  Local3: 8 7 6 9 10 11 
  Local3: 8 7 6 9 10 11 
  Local4: 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 6 7 
    Local2: 6 7 
    Local4: 6 7 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 7 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 9 10 11 
    Local2: 10 9 11 
    Local3: 10 9 11 
    Local4: 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 9 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 3, compares = 25, swaps = 48

********************************************************************************

Results of quick f0 sa d1
This is the same as the previous example but shows the additional detail of index
values that lead to the swapping decision. However, the clutter tends to obscure
what is actually happening to the sublist.

====== krQuick ======
0 1 2 3 4 5 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
Local1: 0 1 2 3 4 5 6 7 8 9 10 11 
Local2: 5 1 2 3 4 0 6 7 8 9 10 11 
i=1 @i=1 left=0 @left=5 last=0
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
i=2 @i=2 left=0 @left=5 last=1
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
i=3 @i=3 left=0 @left=5 last=2
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
i=4 @i=4 left=0 @left=5 last=3
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
i=5 @i=0 left=0 @left=5 last=4
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local4: 0 1 2 3 4 5 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
  Local1: 0 1 2 3 4 
  Local2: 2 1 0 3 4 
  i=1 @i=1 left=0 @left=2 last=0
  Local3: 2 1 0 3 4 
  i=2 @i=0 left=0 @left=2 last=1
  Local3: 2 1 0 3 4 
  Local4: 0 1 2 3 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 0 1 
    Local2: 0 1 
    Local4: 0 1 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 1 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 3 4 
    Local2: 3 4 
    Local4: 3 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
  Local1: 6 7 8 9 10 11 
  Local2: 8 7 6 9 10 11 
  i=7 @i=7 left=6 @left=8 last=6
  Local3: 8 7 6 9 10 11 
  i=8 @i=6 left=6 @left=8 last=7
  Local3: 8 7 6 9 10 11 
  Local4: 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 6 7 
    Local2: 6 7 
    Local4: 6 7 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 7 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 9 10 11 
    Local2: 10 9 11 
    i=10 @i=9 left=9 @left=10 last=9
    Local3: 10 9 11 
    Local4: 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 9 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 3, compares = 25, swaps = 48

В вашем коде есть ошибка, строки в конце:

qsort(v, left, last - 1); [7]
qsort(v, last + 1, right);  [8]

должно быть:

qsort(v, left, last - 1, comp); [7]
qsort(v, last + 1, right, comp);  [8]

Или я что-то упустил?

Кроме того, повторное использование имен стандартной библиотеки - плохой стиль, особенно если новая функция имеет подпись, отличную от сигнатуры библиотеки. У функции qsort стандартной библиотеки есть этот прототип:

 void  qsort(void  *base,  size_t  nel,  size_t  width,   int (*compar)(const void *, const void *));

Если ваша программа немного больше (более одного объектного файла), это может дать интересные ошибки. Представьте себе другой модуль, вызывающий стандартную функцию qsort, но поскольку вы ее переопределили, с совместимой сигнатурой, но с другой семантикой, вы получаете неожиданную ошибку.