C qsort () против C ++ sort ()

Опубликовано: 1 Января, 2022

Стандартная библиотека C предоставляет функцию qsort, которую можно использовать для сортировки массива. Ниже приведен прототип функции qsort ().

// Сортируем массив любого типа. Параметры, базовые
// адрес массива, размер массива и указатель на
// функция компаратора
void qsort (void * base, size_t num, size_t size, 
            int (* компаратор) (const void *, const void *));

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

Стандартная библиотека C ++ предоставляет аналогичную функцию sort (), которая возникла в STL. Мы обсудили здесь сортировку C ++. Ниже приведены прототипы функции sort () C ++.

// Сортировать по умолчанию или по возрастанию.
шаблон
пустая сортировка (Т первая, Т последняя);

// Сортировать в соответствии с указанным порядком
// по комп.
шаблон
void sort (T first, T last, Compare comp);

Сохранение порядка равных элементов не гарантируется. C ++ предоставляет std :: stable_sort, который можно использовать для сохранения порядка.

Сравнение с qsort и sort ()
1. Детали реализации:
Как следует из названия, функция qsort использует алгоритм QuickSort для сортировки данного массива, хотя стандарт C не требует, чтобы он реализовывал быструю сортировку.

Функция сортировки C ++ использует внутреннюю сортировку, которая является гибридным алгоритмом. В разных реализациях используются разные алгоритмы. Библиотека GNU Standard C ++, например, использует трехкомпонентный гибридный алгоритм сортировки: сначала выполняется внутренняя сортировка (сама внутренняя сортировка является гибридом быстрой сортировки и сортировки кучей), а затем сортировка вставкой по результату.

2. Сложность:
Стандарт C не говорит о сложности qsort. Новый стандарт C ++ 11 требует, чтобы сложность сортировки в худшем случае составляла O (Nlog (N)). Предыдущие версии C ++, такие как C ++ 03, допускают наихудший сценарий O (N ^ 2). Только средняя сложность должна была быть O (N log N).

3. Продолжительность:
Сортировка STL выполнялась быстрее, чем qsort C, потому что шаблоны C ++ генерируют оптимизированный код для определенного типа данных и конкретной функции сравнения.

Сортировка в STL выполняется на 20–50% быстрее, чем ручная сортировка, и на 250–1000% быстрее, чем функция библиотеки C qsort. C может быть самым быстрым языком, но qsort очень медленный.

Когда мы пытались отсортировать один миллион целых чисел на C ++ 14, время, затраченное C qsort (), составляло 0,247883 секунды, а время, затраченное C ++ sort (), составляло всего 0,086125 секунды.

 // C++ program to demonstrate performance of
 // C qsort and C++ sort() algorithm
 #include <bits/stdc++.h>
 using namespace std;
 
// Number of elements to be sorted
 #define N 1000000
 
// A comparator function used by qsort
 int compare( const void * a, const void * b)
 {
    return ( *( int *)a - *( int *)b );
 }
 
// Driver program to test above functions
 int main()
 {
    int arr[N], dupArr[N];
 
    // seed for random input
    srand ( time (NULL));
 
    // to measure time taken by qsort and sort
    clock_t begin, end;
    double time_spent;
 
    // generate random input
    for ( int i = 0; i < N; i++)
        dupArr[i] = arr[i] = rand ()%100000;
 
    begin = clock ();
    qsort (arr, N, sizeof ( int ), compare);
    end = clock ();
 
    // calculate time taken by C qsort function
    time_spent = ( double )(end - begin) / CLOCKS_PER_SEC;
 
    cout << "Time taken by C qsort() - "
         << time_spent << endl;
 
    time_spent = 0.0;
 
    begin = clock ();
    sort(dupArr, dupArr + N);
    end = clock ();
 
    // calculate time taken by C++ sort
    time_spent = ( double )(end - begin) / CLOCKS_PER_SEC;
 
    cout << "Time taken by C++ sort() - "
         << time_spent << endl;
 
    return 0;
 }

Выход :

Время, затраченное C qsort () - 0.247883
Время, затраченное C ++ sort () - 0,086125

С ++ sort () невероятно быстрее, чем qsort () для эквивалентных данных из-за встраивания. sort () в контейнере целых чисел будет скомпилирован для использования std :: less :: operator () по умолчанию, который будет встроен, а sort () будет сравнивать целые числа напрямую. С другой стороны, qsort () будет делать косвенный вызов через указатель функции для каждого сравнения, которое компиляторы не могут оптимизировать.

4. Гибкость:
Сортировка STL работает для всех типов данных и для различных контейнеров данных, таких как массивы C, векторы C ++, deques C ++ и т. Д. И другие контейнеры, которые могут быть написаны пользователем. Такой гибкости довольно сложно добиться в C.

5. Безопасность:
По сравнению с qsort, шаблонная сортировка более безопасна по типу, поскольку не требует доступа к элементам данных через небезопасные указатели void, как это делает qsort.

Использованная литература:
http://theory.stanford.edu/~amitp/rants/c++-vs-c
https://en.wikipedia.org/wiki/Sort_(C%2B%2B)

Эта статья предоставлена Адитьей Гоэлем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

C++ Олимпиады по программированию C

C qsort () против C ++ sort ()

РЕКОМЕНДУЕМЫЕ СТАТЬИ