Standard C library provides qsort function that can be used for sorting an array. Following is the prototype of qsort() function. // Sort an array of any type. The parameters are base // address of array size of array and pointer to // comparator function void qsort (void* base size_t num size_t size int (*comparator)(const void* const void*));
It requires a pointer to the array the number of elements in the array the size of each element and a comparator function. We have discussed qsort comparator in detail 여기 . C ++ 표준 라이브러리는 STL에서 시작된 유사한 함수 정렬 ()을 제공합니다. 우리는 C ++ 정렬에 대해 논의했습니다 여기 . Following are prototypes of C++ sort() function. // To sort in default or ascending order. template void sort(T first T last); // To sort according to the order specified // by comp. template void sort(T first T last Compare comp);
The order of equal elements is not guaranteed to be preserved. C++ provides std::stable_sort that can be used to preserve order. Qsort 및 Sort ()와 비교 1. 구현 세부 사항 : 이름에서 알 수 있듯이 Qsort 함수는 QuickSort 알고리즘을 사용하여 C 표준이 QuickSort를 구현할 필요는 없지만 주어진 배열을 정렬합니다. C ++ 정렬 함수는 하이브리드 알고리즘 인 introsort를 사용합니다. 다른 구현은 다른 알고리즘을 사용합니다. 예를 들어 GNU 표준 C ++ 라이브러리는 3 부 하이브리드 분류 알고리즘을 사용합니다. introsort가 먼저 수행됩니다 (interrosort 자체는 QuickSort 및 힙 정렬의 하이브리드입니다). 2. 복잡성 : C 표준은 QSORT의 복잡성에 대해서는 이야기하지 않습니다. 새로운 C ++ 11 표준은 최악의 경우 종류의 복잡성이 O (nlog (n))이어야합니다. C ++ 03과 같은 C ++의 이전 버전은 O (n^2)의 최악의 시나리오를 허용합니다. O (n log n)이 되려면 평균 복잡성 만 필요했습니다. 3. 실행 시간 : STL’s sort ran faster than C’s qsort because C++’s templates generate optimized code for a particular data type and a particular comparison function. STL’s sort runs 20% to 50% faster than the hand-coded quicksort and 250% to 1000% faster than the C qsort library function. C might be the fastest language but qsort is very slow. When we tried to sort one million integers on C++14 Time taken by C qsort() was 0.247883 sec and time taken by C++ sort() was only 0.086125 sec CPP // C++ program to demonstrate performance of // C qsort and C++ sort() algorithm #include 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; }
Time taken by C qsort() - 0.247883 Time taken by C++ sort() - 0.086125
C++ sort() is blazingly faster than qsort() on equivalent data due to inlining. sort() on a container of integers will be compiled to use std::less::operator() by default which will be inlined and sort() will be comparing the integers directly. On the other hand qsort() will be making an indirect call through a function pointer for every comparison which compilers fails to optimize. 4. 유연성 : STL의 정렬은 모든 데이터 유형 및 C 배열 C ++ 벡터 C ++ Deques 등과 같은 다른 데이터 컨테이너 및 사용자가 작성할 수있는 기타 컨테이너에 대해 작동합니다. 이런 종류의 유연성은 C에서 달성하기가 다소 어렵다. 5. 안전 : QSORT와 비교하여 템플 된 정렬은 QSORT와 같이 안전하지 않은 빈 공간 포인터를 통해 데이터 항목에 액세스 할 필요가 없기 때문에 유형 안전합니다. 참조 : http://theory.stanford.edu/~amitp/rants/c++-vs-c/ https://en.wikipedia.org/wiki/sort_(C%2B%2B)
