This is the code for Quick Sort. The array generated is random, using random() function, with 10,000 as upper limit.
When number of elements exceeded 109, e.g. 110, the program did not complete execution and got stuck.
This is the code:
/*
Program to sort a list of numbers using Quick sort algorithm.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// For runtime calculation
#define BILLION 1000000000
// For random number upper limit
#define UPPER_LIMIT 10000
// For printing array
#define PRINT_ARR printf("Parse %d: ", parseCount); for (int p = 0; p < eltCount; p ) printf("%d ", *(ptrMainArr p)); printf("\n"); parseCount ;
// Declare global parse counter
int parseCount = 0;
// Declare global pointer to array
int *ptrMainArr;
// Number of elements in array
int eltCount;
float calcRunTime(struct timespec start, struct timespec end) {
long double runTime;
if (end.tv_nsec - start.tv_nsec >= 0) {
runTime = (end.tv_sec - start.tv_sec) ((float)(end.tv_nsec - start.tv_nsec) / BILLION);
}
else {
runTime = (end.tv_sec - start.tv_sec - 1 ((float)(end.tv_nsec - start.tv_nsec) / BILLION));
}
return runTime;
}
void swap(int *ptr1, int *ptr2) {
int temp = *ptr1;
*ptr1 = *ptr2;
*ptr2 = temp;
}
void quicksort(int *ptrArr, int numOfElts) {
// Single element in sub-array
if (numOfElts == 1) {
return;
}
// No elements in sub-array
if (numOfElts == 0) {
return;
}
// Print elements in array
PRINT_ARR
// Select pivot element (element in middle)
int pivotIdx;
// Even number of elements in array
if ((numOfElts) % 2 == 0) {
pivotIdx = ((numOfElts) / 2) - 1;
}
// Odd number of elements in array
else {
pivotIdx = (int)((numOfElts) / 2);
}
int pivot = *(ptrArr pivotIdx);
// Initialise left and right bounds
int lb = 0, rb = numOfElts - 2;
// Swap pivot element with last element
swap(ptrArr pivotIdx, ptrArr numOfElts - 1);
while (1) {
while (*(ptrArr lb) < pivot) {
lb ;
}
while (*(ptrArr rb) > pivot && lb <= rb) {
rb--;
}
if (lb > rb) {
break;
}
swap(ptrArr lb, ptrArr rb);
}
swap(ptrArr lb, ptrArr (numOfElts - 1));
// Sort left sub-array
quicksort(ptrArr, lb);
// Sort right sub-array
quicksort(ptrArr (lb 1), numOfElts - lb - 1);
}
int main() {
printf("*** Quick Sort *** \n");
printf("Enter number of elements: ");
scanf("%d", &eltCount);
int arr[eltCount];
for (int i = 0; i < eltCount; i ) {
arr[i] = random() % UPPER_LIMIT 1;
}
// Assign array to global pointer variable (to print array after each parse)
ptrMainArr = arr;
// Note: arr -> Pointer to array's first element
// Start clock
struct timespec start, end;
clock_gettime(CLOCK_REALTIME, &start);
// Sort array using quicksort
quicksort(arr, eltCount);
// End clock
clock_gettime(CLOCK_REALTIME, &end);
printf("Quick sort time taken is %f s.\n", calcRunTime(start, end));
return 0;
}
I ran this code for values under 110, and the code worked. Included is a Macro Function 'PRINT_ARR' to print the array after every parse.
I want to know the cause for the error, and how to sort an array of size > 10,000.
CodePudding user response：
The partitioning function fails for any couple of equal numbers. It can be fixed just by adding an =. Moreover after swapping you can increase lb and decrease rb:
while (1) {
while (*(ptrArr lb) < pivot) {
lb ;
}
while (*(ptrArr rb) > pivot && lb <= rb) {
rb--;
}
if (lb >= rb) { // <--------------------------------------------------
break;
}
swap(ptrArr lb , ptrArr rb--); // <------------------------------
}
Then additional suggestions:
- remove the console input and use a fixed number for testing.
- your
calcRunTimefunction is broken. Just use your first equation:
long double calcRunTime(struct timespec start, struct timespec end) {
return (end.tv_sec - start.tv_sec) ((float)(end.tv_nsec - start.tv_nsec) / BILLION);
}
- don't use a VLA.
mallocit, so you can grow without the risk of a stack overflow.
CodePudding user response：
First I reproduced the issue by compiling your program and running it with 109 (ok) and 110 (doesn't terminate). Then I hard-coded eltCount to 110 so the program no longer requires interactive input. Removed irrelevant functionality. Modified the PRINT_ARR to take an array and len. Printed array before it's sorted paying particular attention to the last element:
#define PRINT_ARR(arr, len) for (unsigned i = 0; i < (len); i ) printf("%d ", arr[i]); printf("\n")
int main() {
unsigned eltCount = 110;
int arr[eltCount];
for (unsigned i = 0; i < eltCount; i ) {
arr[i] = random() % UPPER_LIMIT 1;
}
PRINT_ARR(arr, eltCount);
quicksort(arr, eltCount);
PRINT_ARR(arr, eltCount);
return 0;
}
and found:
9384 887 2778 6916 7794 8336 5387 493 6650 1422 2363 28 8691 60 7764 3927 541 3427 9173 5737 5212 5369 2568 6430 5783 1531 2863 5124 4068 3136 3930 9803 4023 3059 3070 8168 1394 8457 5012 8043 6230 7374 4422 4920 3785 8538 5199 4325 8316 4371 6414 3527 6092 8981 9957 1874 6863 9171 6997 7282 2306 926 7085 6328 337 6506 847 1730 1314 5858 6125 3896 9583 546 8815 3368 5435 365 4044 3751 1088 6809 7277 7179 5789 3585 5404 2652 2755 2400 9933 5061 9677 3369 7740 13 6227 8587 8095 7540 796 571 1435 379 7468 6602 98 2903 3318 493
Nothing particular special about the last number other than it's a duplicate as @RetiredNinja noted above.
As the problem is an infinite loop, I looked the loops and particular their exit conditions. From our hint from the above, I changed it to only exist if two bounds are equal:
if(lb >= rb) break;
and the program now terminates.