[C++] Быстрая сортировка ( QuickSort )

allenhere

Регистрация
30 Май 2018
Сообщения
30
Реакции
33
Хоть и данная сортировка была разработана более 40 лет назад, но она является самой применяемой и одна из самых эффективных. P.S. Часто применяется на олимпиадном программировании ( Проверил сам )

Код:
void quickSortR( T* a, long N ) { // На входе - массив a[], a[N] - его последний элемент.
 
    long i = 0, j = N;      // поставить указатели на исходные места
    T temp, p;
 
    p = a[ N>>1 ];      // центральный элемент
    // процедура разделения
    do {
        while ( a[i] < p ) i++;
        while ( a[j] > p ) j--;
 
        if (i <= j) {
            temp = a[i]; a[i] = a[j]; a[j] = temp;
            i++;
            j--;
        }
    } while ( i<=j );  // рекурсивные вызовы, если есть, что сортировать
    if ( j > 0 ) quickSortR( a, j );
    if ( N > i ) quickSortR( a+i, N-i );
}
 

allenhere

Регистрация
30 Май 2018
Сообщения
30
Реакции
33
c++ появился 35 лет назад o_O
Быстрая сортировка, сортировка Хоара (
Пожалуйста войдите или зарегистрируйтесь чтобы просматривать скрытый текст.
quicksort), часто называемая qsort (по имени в
Пожалуйста войдите или зарегистрируйтесь чтобы просматривать скрытый текст.
) — широко известный
Пожалуйста войдите или зарегистрируйтесь чтобы просматривать скрытый текст.
, разработанный английским информатиком
Пожалуйста войдите или зарегистрируйтесь чтобы просматривать скрытый текст.
во время его работы в
Пожалуйста войдите или зарегистрируйтесь чтобы просматривать скрытый текст.
в
Пожалуйста войдите или зарегистрируйтесь чтобы просматривать скрытый текст.
.
 

Похожие темы

Сверху Снизу