i was in the process on implementing a QuickSort in C as an exercise. I think I'm in a pretty good spot by I'm puzzle by why my code seems to sometimes not call the first call of QuickSort.
main.c
#include <stdlib.h>
#include <time.h>
#include "quicksort.h"
#include "utils.h"
//----------------------------------------
void main(int argc, char* argv[]) {
unsigned int SIZE;
int* numbers;
if (argc > 1) {
SIZE = argc-1;
numbers = (int*) malloc(sizeof(unsigned int) * SIZE);
if (numbers == NULL) { exit(1); }
for (unsigned int i = 0; i < SIZE; i++) {
numbers[i] = atoi(argv[i+1]);
}
} else {
SIZE = 100;
numbers = (int*) malloc(sizeof(unsigned int) * SIZE);
if (numbers == NULL) { exit(1); }
srandom(time(NULL));
for (int i = 0; i < SIZE; i++) {
numbers[i] = (random() % 60000) - 30000; // Random numbers between (-30000, 30000)
}
}
printf("Array filled!\n");
quicksort(numbers, 0, SIZE-1);
printf("%s\n", isSorted(numbers, SIZE) ? "Sorted!" : "Not sorted!");
free(numbers);
printf("Memory released\n");
exit(0);
}
quicksort.c
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include "quicksort.h"
#include "utils.h"
//----------------------------------------
unsigned int partition(int* const array, const unsigned int low, const unsigned int high) {
const int pivot = array[(unsigned int)((low + high)/2)];
unsigned int i = low;
unsigned int j = high;
while (1) {
while (array[i] < pivot) { i += 1; }
while (pivot < array[j]) { j += -1; }
if (i == j) { return i; }
swap(array+i, array+j);
}
}
void quicksort(int* const array, const unsigned int low, const unsigned int high) {
unsigned int pivot = partition(array, low, high);
printf(".");
// We only want to recurse if there at least two elements to order.
// Otherwise we simply don't recurse on the subarray because one element is in order with itself.
if (low+1 < pivot) { quicksort(array, low, pivot-1); }
if (pivot+1 < high) { quicksort(array, pivot+1, high); }
}
utils.c
#include <stdio.h>
#include "utils.h"
//----------------------------------------
void print_array(int* const array, const unsigned int size) {
printf("%d", array[0]);
for (unsigned int i = 1; i < size; i++) {
printf(" %d", array[i]);
}
printf("\n");
}
void swap(int* a, int* b) {
const int temp = *a;
*a = *b;
*b = temp;
}
unsigned short isSorted(int* const array, const unsigned int size) {
for (int i = 0; i < size-1; i++) {
if (array[i] > array [i+1]) {
return 0;
}
}
return 1;
}
The issue is that sometimes the first call to quicksort() is ran and I can see the dots of each call on my terminal. Sometimes it gets stuck and I can't see even one single dot.
I'm really puzzled because it's such a random error I don't even know how to start debugging it.
This is one particular instance that always get stuck.
./main -22167 -8962 -12961 -8232 -1118 -22237 -7872 -8654 15744 -28388 -12088 402 17865 3515 -10380 -1672 -6731 24435 14161 14906 -21791 -9593 -2111 -1323 6065 1955 -23011 17216 29229 -8988 21034 -22938 -11598 14425 -24818 -6364 -1460 -2689 14983 -15716 -24725 9247 -8962 23141 -17238 -12989 27821 -17616 -18554 11982 27290 26008 -27611 -28468 -5315 -15194 -20161 -21974 -27977 -20932 -24610 -591 22483 -29856 20186 27665 -6219 25078 -28672 15116 -20638 -23396 -5637 -23247 6097 -16523 -6236 3918 -4139 5210 22252 29504 -22430 994 7388 -21393 15800 17227 -13367 -5825 2647 28375 -64 -28518 28520 26474 5500 28653 21552 6828
Aucun commentaire:
Enregistrer un commentaire