J'ai un souci assez particulier en implémentant un QuickSort : un stack overflow. Le but de ce projet est de ne trier que des void* pour lesquels on a un comparateur passé en argument.

Voici mon code (pour le partitionnement, mon ancienne version est restée en commentaire, mais elle produit le même problème) :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
void swap(const void** arr, size_t firstIndex, size_t secondIndex)
{
  const void* tmp = arr[firstIndex];
  arr[firstIndex] = arr[secondIndex];
  arr[secondIndex] = tmp;
}
 
// Choix du pivot : on choisit arbitrairement de renvoyer le dernier élément
const void* quickPivot(const void** arr, size_t beginning, size_t end, int (*comparator)(const void*, const void*)) {
	// printf("%d", ((const Event *)arr[end - 1])->start); 
	return arr[end]; 
}
 
// Algorithme de partitionnement : on place les éléments inférieurs à gauche, 
// les supérieurs à droite. 
const size_t quickPartition(const void** arr, size_t beginning, size_t end, const void* pivot, int (*compare)(const void*, const void*)) {
	size_t i = beginning - 1; 
 
	for(size_t j = beginning; j < end - 1; ++j) {
		if(compare(arr[j], pivot) <= 0) {
			++i; 
			swap(arr, i, j); 
		}
	}
 
	swap(arr, i, end); 
	return i;
	/*
	size_t left  = beginning;// - 1;
    size_t right = end;// + 1;
    while(1) {
        do { 
			right--;
		} while(comparator(arr[right], pivot) > 0);// && right > beginning);
		// while(array[right] - pivot > 0);
 
        do {
			left++;
		} while(comparator(arr[left], pivot) < 0);// && left < end);
		// while(array[left] - pivot < 0);
 
        if(left - right < 0) {
            swap(arr, left, right);
        } else {
			return right;
		}
    }
	*/
}
 
// Applique l'algorithme du tri rapide sur le tableau array entre les éléments 
// beginning et end. Par souci de généralité, on passe les foncteurs de 
// comparaison d'éléments, de choix de pivot et de partitionnement. 
void quickSort(const void** arr, size_t beginning, size_t end, int (*compare)(const void*, const void*))
{
    if(beginning >= end)
        return;
 
	// S'il ne reste que deux éléments, inutile de lancer toute la procédure
	// somme toute très coûteuse : si nécessaire, on les inverse. 
	if(beginning - end == 1) {
		if(compare(arr[end], arr[beginning]) < 0) {
			swap(arr, end, beginning); 
		}
		return;
	}
 
	// Utilisation de foncteurs, sachant qu'on peut vouloir changer à l'envi 
	// le choix du pivot ou de l'algorithme de partitionnement. 
    const void* pivot = quickPivot(arr, beginning, end, compare);
	const size_t cut = quickPartition(arr, beginning, end, pivot, compare);
 
    quickSort(arr, beginning, cut-1, compare);
    quickSort(arr, cut+1, end, compare);
}
 
void Sort(const void** arr, size_t length, int (*comparator)(const void*, const void*)) {
    quickSort(arr, 0, length-1, comparator);//, quickPivot, quickPartition); 
}
Je l'appelle comme ceci :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int main(void)
{
  size_t numEvents = 10;
  printf("Num. Events: %d\n", (int)numEvents);
  //Event** events = createArrayOfEvents(numEvents);
  int** events = (int**) malloc(numEvents * sizeof(int*));
  for(size_t i = 0; i < numEvents; i++) {
	  events[i] = (int*) malloc(sizeof(int)); 
	  *(events[i]) = rand(); 
  }
 
  const double sec = cpuTimeUsedToSort((const void**)events, numEvents, compare); //EventByStartTime);
  printf("CPU Time: %f\n", sec);
 
  for(size_t i = 0; i < numEvents; ++i) {
	//printEvent(events[i]); 
	printf("%d\n", *(events[i])); 
  }
 
  //freeArrayOfEvents(events, numEvents);
 
  scanf("%d");
  return 0;
}
 
double cpuTimeUsedToSort(const void** array, size_t length, int (*comparator)(const void*, const void*))
{
  clock_t start = clock();
  Sort(array, length, comparator);
  return ((double)(clock() - start)) / CLOCKS_PER_SEC;
}
 
int compareEventByStartTime(const void* a, const void* b)
{
  return ((Event*)a)->start - ((Event*)b)->start;
}
La structure de données utilisée est :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
typedef struct Event_t Event;
 
struct Event_t
{
  time_t start;
  time_t end;
  size_t value;
};
Tous mes problèmes apparaissent lors de comparaisons effectuées dans le partitionnement, en utilisant le débogueur de Visual Studio. Cependant, je n'arrive pas à en trouver la cause ou à la corriger. Cela semble être un problème en faisant le cut-1, puisqu'on joue avec des size_t (0 - 1 = 0xffffff, ce qui fait foirer le tout), mais, que je mets un quickSort(arr, beginning, cut, compare); à la fin du quicksort, ça plante en stack overflow au niveau de l'échange d'éléments...