Implémentation généraliste du QuickSort

**biloubi** · 15/03/2012, 22h45

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...

**Trademark** · 16/03/2012, 00h09

Salut,

Le stack overflow est produit parce que tu fais trop d'appel récursif de fonction. C'est donc parce que ton algorithme n'est pas bien implémenté, tu "boucles" dans la récursivité ce qui fait que la fonction s'appelle elle-même indéfiniment. Conclusion : revoit l'algo !

**biloubi** · 16/03/2012, 21h49

Après avoir repassé le code au peigne fin, je n'ai pas réussi à trouver la zone du problème... J'ai donc refait tout un code, qui fonctionne (ouf). A posteriori, je suppose un problème avec le size_t.

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
void quickSort(const void** arr, int beginning, int end,
			   int (*compare)(const void*, const void*))
{
	if (beginning < end) {
		int q = quickPartition(arr, beginning, end, arr[end], compare);
		quickSort(arr, beginning, q - 1, compare, partition, pivot);
		quickSort(arr, q + 1, end, compare, partition, pivot);
	}
}
 
size_t quickPartition(const void** arr, int beginning, int end, const void* pivot, int (*compare)(const void*, const void*))
{
	int i = beginning - 1;
 
	for (int j = beginning; j < end; j++) {
		if (compare(arr[j], pivot) <= 0) {
			i++;
			swap(arr, i, j);
		}
	}
 
	swap(arr, i + 1, end);
	return i + 1;
}