Пример K&R Qsort с путаницей указателей и массивов

Question

Пример K&R Qsort с путаницей указателей и массивов

Мне трудно понять следующий фрагмент кода. Я понимаю указатель на функцию маньеризма, но я нахожу путаницу в указанных строках.

void qsort(void **v, int left, int right, int (*comp) (void *, void *))
{
    int i, last;
    void swap(int **v, int i, int j);

    if (left >= right)   /* do nothing if array contains */
        return;           /* fewer than two elements */
    swap(v, left, (left + right)/2);   /* move partition elem */ [1]
    last = left;                       /* to v[0] */ [2]
    for (i = left + 1; i <= right; i++) /* partition */ [3]
        if ((*comp) (v[i], v[left]) < 0) [4]
            swap(v, ++last, i); [5]
    swap(v, left, last);        /* restore partition elem */ [6]
    qsort(v, left, last - 1); [7]
    qsort(v, last + 1, right);  [8]

}

Может ли кто-нибудь объяснить мне эту процедуру, особенно указанные строки, просто скажите мне, что она делает, потому что я не могу понять этот qsort, руководство по эскимосу, которое я прочитал, читая k&r, сказав, что процедура qsort - мусор и чрезмерно сложна. Мне просто нужно понять, почему это написано так, потому что это не имеет смысла для меня.

Спасибо, если даром, за то, что прочитал это.

8

c kr-c

Источник

05 авг '09 в 04:52

5 ответов

Другие вопросы по тегам c kr-c

user133758 05 авг '09 в 05:17 2009-08-05 05:17 · Answer 1 · 2009-08-05 05:17

Это красивый кусок кода!

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

1) Взять список номеров.

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

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

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

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

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

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

в начале слева =0, указывая на D. справа =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,5

= 1:

[CADBE]

если ('A'<'C')

своп ('A', 'A') (И ПОСЛЕДНЕЕ ВКЛЮЧЕНИЕ!)

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

последняя = 1

=2:

[CADBE]

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

выходит из строя. двигаться дальше.

I = 3:

[CADBE]

если ('B'<'C')

поменять местами ('B', 'D') и увеличить в последнюю очередь!

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

последний =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]

и мы сделали!

14 авг '09 в 18:21 2009-08-14 18:21 · Answer 2 · 2009-08-14 18:21

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

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

/ ***************************** QUICK.CPP ***************** ********************** Автор: David McCracken Обновлено: 2009-08-14 Цель: Это иллюстрирует работу быстрой сортировки в K&R "Язык программирования C" (второе издание, стр. 120). Многие программисты разочарованы, когда пытаются понять краткую сортировку в целом из этой версии, которая явно была предназначена не как учебник по быстрой сортировке, а как использовать указатели на функции. Моя программа модифицирует оригинал, чтобы работать только с целыми числами, чтобы сосредоточиться на процессе сортировки. Он может печатать глобальный список и рекурсивный подсписок при каждом изменении, чтобы отслеживать процесс принятия решения о сортировке. Моя программа также проясняет два запутанных аспекта, оба из которых включают необъяснимую замену оригинала, сравнивая его работу с работой двух других модифицированных версий. Единственное, что сбивает с толку оригинала - это поменять предмет с собой. Код (измененный только для целых):

last = left;
for( i = left+1; i <= right; i++)
   if(  v[i]  #include  #include  #include  // ======================== ДАННЫЕ И ДЕКЛАРАЦИИ ===============================
#define DIM(A) (размер A / размер 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 }; статическая структура { 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 рекурсия;  // Текущий уровень рекурсии. Int звонки;  // Количество вызовов функции сортировки. в глубину;  // Максимальный уровень рекурсии.
int swaps;      // Количество свопов. int сравнивает;  // Количество элементов списка сравнивается.
int totCalls;
int totDepth;
int totCompares;
int totSwaps;

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

char dArg = 'A'; // аргумент командной строки выбирает 0,1,2,3,4, или A
int dataList; // Если dArg является числовым, это его значение int.

//============================== ФУНКЦИИ =====================================

// ----------------------------- отступ --------------------------------------
// Вывести два пробела для каждого уровня рекурсия для отступа последующей печати // вывод.
// ............................................................................
void indent( void)
{
    for( int indent = 1; indent <рекурсия; indent ++) printf (" "); } // -------------------------------- шоу -------------- ------------------------- // Распечатать заданный список int в соответствии с настройкой глобального управления showWhat // и заданной локальной идентификацией. Это может ничего не печатать, либо глобальный // список, либо локальный подсписок. Он может или не может печатать легенду GLOBAL или // LOCALx, где x - локальный идентификатор, который сообщает, в какой точке кода сортировки // мы показываем подсписок. // Возвращает: Ничего // Аргументы: // - int * ia указывает на список int. // - int cnt - количество элементов в списке. // - int local сообщает локальной точке в процедуре сортировки, если больше 0. 0 // указывает, что это глобально. В любом случае формат контролируется // showWhat. Если local равен -1, список печатается без каких-либо условных обозначений. // Global: // - showWhat bitmap control word // - 0 (SHOW_NOTHING) Это полное значение, а не битовый флаг. // - 1 (SHOW_GLOBAL) Печатать список, если local равен 0. Если любой другой бит также // установлен, легенда GLOBAL печатается перед списком. // - 2 (SHOW_LOCAL1) Печатать список, только если local равен 1. // - 3 (SHOW_LOCAL) Печатать список, если local равен 1 или больше. // //...................... заметки............................................. // SHOW_NOTHING // Это существует, потому что вызывающие не проверяют showWhat перед вызовом. Если // мы хотим показать только начальный несортированный список и окончательную отсортированную версию, то // SHOW_NOTHING блокирует весь вывод на печать из функции сортировки. // Функция control вызывает show с local = -1 для печати списка. //.......................................................................... void show (int * ia, int cnt, int local) {if (local> = 0)
    {
        switch( showWhat)
        {
        case SHOW_NOTHING: возврат;
        case SHOW_GLOBAL:   // Только SHOW_GLOBAL
            if( local > 0)
                return;     // Это локальный перерыв;  // Распечатать список без легенды.
        default: // Некоторая комбинация 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);
            } еще возврат;
        }
    }
    for( int *end = ia + cnt; ia  глубина) глубина = рекурсия;  // При первом вызове рекурсия = 0, а глубина равна 0, т.е. рекурсии пока нет.
    ++ рекурсию;
    show( total, totalCnt, 0); // GLOBAL
    show(список + слева, справа - слева + 1, 1); // ЛОКАЛЬНЫЙ if( left  глубина) глубина = рекурсия;  // При первом вызове рекурсия = 0, а глубина равна 0, т.е. рекурсии пока нет.
    ++ рекурсию;
    show( total, totalCnt, 0); // GLOBAL
    show(список + слева, справа - слева + 1, 1); // ЛОКАЛЬНЫЙ if( left  глубина) глубина = рекурсия;  // При первом вызове рекурсия = 0, а глубина равна 0, т.е. рекурсии пока нет.
    ++ рекурсию;
    show( total, totalCnt, 0); // GLOBAL
    show(список + слева, справа - слева + 1, 1); // ЛОКАЛЬНЫЙ if( left  = (int)DIM( lists))
                {
                    printf( "Ошибка: неверный селектор списка данных%c\n", dArg); возврат 1;
                }
            } перерыв;
        case 'S': // show selector соответствует растровому отображению showWhat или N или A
            ++cp;
            if( *cp!= 0 || toupper( *cp)!= 'N')
            {
                if( toupper( *cp) == 'A')
                    showWhat = SHOW_ALL; иначе покажите, что = atoi( cp);
            } перерыв; по умолчанию:
            if(!isdigit( *cp))
            {   
                printf( "Ошибка: нет опции%c\n", *cp); возврат 1; } для ( idx = 0; idx Результаты быстрого
При этом используются все значения по умолчанию, что наиболее полезно для сравнения производительности.
из трех разных функций.

====== krQuick ======
4 0 2 5 1 3 
0 1 2 3 4 5 
Звонки = 7, глубина = 2, сравнение = 8, обмены = 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 
Звонки = 15, глубина = 3, сравнение = 25, обмен = 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 
Звонки = 17, глубина = 5, сравнение = 30, обмен = 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 
Звонки = 13, глубина = 5, сравнение = 33, обмен = 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 
Звонки = 15, глубина = 6, сравнение = 38, обмен = 60
---------------------------------
Итого: коллы = 67, глубина = 21, сравнение = 134, свопы = 246
====== krQuick2 (без смены личных данных) ======
4 0 2 5 1 3 
0 1 2 3 4 5 
Звонки = 7, глубина = 2, сравнение = 8, обмен = 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 
Звонки = 15, глубина = 3, сравнение = 25, обмен = 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 
Звонки = 17, глубина = 5, сравнение = 30, обмен = 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 
Звонки = 13, глубина = 5, сравнение = 33, обмен = 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 
Звонки = 15, глубина = 6, сравнение = 38, обмен = 44
---------------------------------
Итого: колл = 67, глубина = 21, сравнение = 134, своп = 186
====== quick3 (без предварительной перестановки) ======
4 0 2 5 1 3 
0 1 2 3 4 5 
Звонки = 7, глубина = 3, сравнение = 10, обмен = 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 
Звонки = 23, глубина = 11, сравнение = 66, обмен = 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 
Звонки = 23, глубина = 11, сравнение = 66, обмен = 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 
Звонки = 15, глубина = 7, сравнение = 46, обмен = 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 
Звонки = 19, глубина = 6, сравнение = 37, обмен = 30
---------------------------------
Итого: коллы = 87, глубина = 38, сравнения = 225, свопы = 138

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

Результаты быстрого f0 s5 d1
Формат S5 лучше всего подходит для отображения того, как изменяется подсписок во время сортировки. поскольку 
LOCAL отображается только после перестановки, избыточные перестановки идентификаторов (многие в этом 
пример) очевидны.

====== krQuick ======
0 1 2 3 4 5 6 7 8 9 10 11 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
Местный 1: 0 1 2 3 4 5 6 7 8 9 10 11 
Местный2: 5 1 2 3 4 0 6 7 8 9 10 11 
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
Местный4: 0 1 2 3 4 5 6 7 8 9 10 11 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
Local1: 0 1 2 3 4 
  Local2: 2 1 0 3 4 
  Местный3: 2 1 0 3 4 
  Местный3: 2 1 0 3 4 
  Местный4: 0 1 2 3 4 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 0 1 
    Местный2: 0 1 
    Местный4: 0 1 
ГЛОБАЛЬНЫЙ 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 
      Local1: 1 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 3 4 
    Local2: 3 4 
    Local4: 3 4 
ГЛОБАЛЬНЫЙ 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 
      Local1: 4 
ГЛОБАЛЬНЫЙ 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 
  Местный3: 8 7 6 9 10 11 
  Местный3: 8 7 6 9 10 11 
  Местный4: 6 7 8 9 10 11 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 6 7 
    Local2: 6 7 
    Местный4: 6 7 
ГЛОБАЛЬНЫЙ 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 
      Local1: 7 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
    Местный 1: 9 10 11 
    Local2: 10 9 11 
    Местный3: 10 9 11 
    Local4: 9 10 11 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
      Местный 1: 9 
ГЛОБАЛЬНЫЙ 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 
Звонки = 15, глубина = 3, сравнение = 25, обмен = 48

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

Результаты быстрого f0 sa d1
Это то же самое, что и в предыдущем примере, но показывает дополнительные детали индекса
значения, которые приводят к решению об обмене. Тем не менее, беспорядок имеет тенденцию скрывать
что на самом деле происходит с подсписком.

====== krQuick ======
0 1 2 3 4 5 6 7 8 9 10 11 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
Местный 1: 0 1 2 3 4 5 6 7 8 9 10 11 
Местный2: 5 1 2 3 4 0 6 7 8 9 10 11 
я =1 @ я = 1 слева =0 @ слева = 5 последний = 0
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
я =2 @ я = 2 слева =0 @ слева = 5 последний = 1
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
я =3 @ я = 3 слева =0 @ слева = 5 последний = 2
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
я =4 @ я = 4 слева =0 @ слева = 5 последний = 3
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
я =5 @ я = 0 слева =0 @ слева = 5 последний = 4
Местный3: 5 1 2 3 4 0 6 7 8 9 10 11 
Местный4: 0 1 2 3 4 5 6 7 8 9 10 11 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
Local1: 0 1 2 3 4 
  Local2: 2 1 0 3 4 
  я =1 @ я = 1 слева =0 @ слева = 2 последний = 0
  Местный3: 2 1 0 3 4 
  я =2 @ я = 0 слева =0 @ слева = 2 последний = 1
  Местный3: 2 1 0 3 4 
  Местный4: 0 1 2 3 4 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 0 1 
    Местный2: 0 1 
    Местный4: 0 1 
ГЛОБАЛЬНЫЙ 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 
      Local1: 1 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 3 4 
    Local2: 3 4 
    Local4: 3 4 
ГЛОБАЛЬНЫЙ 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 
      Local1: 4 
ГЛОБАЛЬНЫЙ 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 
  я =7 @ я = 7 слева =6 @ слева = 8 последний = 6
  Местный3: 8 7 6 9 10 11 
  я =8 @ я = 6 слева =6 @ слева = 8 последний = 7
  Местный3: 8 7 6 9 10 11 
  Местный4: 6 7 8 9 10 11 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 6 7 
    Local2: 6 7 
    Местный4: 6 7 
ГЛОБАЛЬНЫЙ 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 
      Local1: 7 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
    Местный 1: 9 10 11 
    Local2: 10 9 11 
    я =10 @ я =9 слева =9 @ слева = 10 последний =9
    Местный3: 10 9 11 
    Local4: 9 10 11 
ГЛОБАЛЬНЫЙ 0 1 2 3 4 5 6 7 8 9 10 11 
      Местный 1: 9 
ГЛОБАЛЬНЫЙ 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 
Звонки = 15, глубина = 3, сравнение = 25, обмен = 48

user43452 05 авг '09 в 05:16 2009-08-05 05:16 · Answer 3 · 2009-08-05 05:16

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

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

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

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

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

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

user254583 09 сен '11 в 03:48 2011-09-09 03:48 · Answer 4 · 2011-09-09 03:48

Привет, я сделал пример со страницы 87. Может быть, кто-то поймет из этого. Но прежде чем переходить к этому коду, просмотрите быструю сортировку

/**
 * qsort.c
 * Quick sort using recursion
 */

#include <stdio.h>

void qsort(int v[], int left, int right);

int main()
{
    int v[] = {9, 3, 4, 6, 7, 3, 1};
    qsort(v, 0, 6);

    int i;

    for (i = 0; i < 7; i++)
        printf(" %d ", v[i]);

    printf("\n");

    return 0;
}

void qsort(int v[], int left, int right)
{
    int i, last; /* last is pivot */

    void swap(int v[], int i, int j);

    if (left >= right)
        return;

    swap(v, left, (left + right) / 2); // swap mid element to front
    last = left;                       // set this position as pivot

    for (i = left + 1; i <= right; i++) { 
        /*loop through every other element 
          swap elements less than pivot i.e bigger to right, smaller to left
        */ 

        if (v[i] < v[left])
            swap(v, ++last, i);     // when swapping lesser element, record
                                    // where our pivot moves
        /*
           we don't swap elements that are bigger than pivot, and are to right.
           However we swap elements those are less than pivot.
           With ++pivot we are essentially going to find out, where our
           pivot will fit to be at the position, where all the elements
           before it are less than it and all after it greater.
        */
    }

    // swap left(our pivot) to last(where pivot must go
    // i.e all elements before pivot are less than it
    // and all elements above it are greater
    // remember they are lesser and greater 
    // but may not be sorted still
    // this is called partition
    swap(v, left, last);

    // Do same(qsort) for all the elements before our pivot
    // and above our pivot
    qsort(v, left, last - 1);   // last is our pivot position
    qsort(v, last + 1, right);

    // Each of above two qsort will use middle element as pivot and do
    // what we did above, because same code will be executed by recursive
    // functions

}                                       

void swap(int v[], int i, int j)
{
    int temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

Самая важная часть - это поворот (поставьте свои ноги на место, а другие свободно двигайте). Мы выбираем средний элемент как опорный, выводим его на передний план, сравниваем со всеми остальными элементами. Если они меньше нашего центра, мы меняем их местами и увеличиваем только нашу позицию центра (будьте осторожны, наш элемент центра все еще лежит сначала). После того, как мы закончим цикл, мы переносим элемент поворота (который сначала) в это место (место поворота). После цикла у нас все элементы перед шарниром меньше, чем шарнир, и все элементы выше шарнира больше, чем шарнир. На первом цикле они не отсортированы. Таким образом, вы должны снова применить один и тот же алгоритм сортировки рекурсивно ко всем элементам ниже и выше, чтобы отсортировать их.

user146377 17 авг '09 в 11:31 2009-08-17 11:31 · Answer 5 · 2009-08-17 11:31

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

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]

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

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

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

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