Je suis débutant et j'essaye maintenant pour le deuxième jour d'implémenter SelectionSort à des fins de pratique. L'algorithme que j'ai fonctionne la plupart du temps mais pas toujours. Malheureusement, je ne comprends pas du tout pourquoi cela ne fonctionne pas toujours. L'exemple en est un où cela ne fonctionne pas.
#include <stdio.h>
int* selectionSort(int a_count, int *a);
int main(void)
{
int a[] = {4,2,3,4,4,9,98,98,3,3,3,4,2,98,1,98,98,1,1,4,98,2,98,3,9,9,3,1,4,1,98,9,9,2,9,4,2,2,9,98,4,98,1,3,4,9,1,98,98,4,2,3,98,98,1,99,9,98,98,3,98,98,4,98,2,98,4,2,1,1,9,2,4};
int i, a_count = 73;
int *result = selectionSort(a_count, a);
for(i = 0; i < a_count; i++){
printf("%i ", result[i]);
}
return 0;
}
int* selectionSort(int a_count, int* a) {
int i, j, min = 0, tmp;
for(i = 0; i < a_count - 1; i++){
min = i;
printf("min_i = %i\n", min);
for(j = i + 1; j < a_count; j++){
printf("j = %i ", j);
if(a[j] < a[min]){
printf("%i < %i\n", a[j], a[min]);
printf("min is changed: ");
min = j;
printf("min_j = %i\n", min);
}
tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
return a;
}
Merci beaucoup pour votre aide!
4 Réponses :
Vous échangez l'élément i avec l'élément min à chaque itération de votre boucle sur j . C'est à la fois incorrect et inefficace. Effectuez l'échange une fois la boucle interne terminée, de sorte que min contienne en fait l'index de la valeur minimale du sous-tableau actuel, pas pendant que vous essayez toujours de déterminer où se trouve cet élément.
Il y a une erreur simple, c'est que vous n'attendez pas la fin de la boucle interne pour faire le swap.
int* selectionSort(int a_count, int* a) {
int i, j, min = 0, tmp;
for(i = 0; i < a_count - 1; i++){
min = i;
printf("min_i = %i\n", min);
for(j = i + 1; j < a_count; j++){
printf("j = %i ", j);
if(a[j] < a[min]){
printf("%i < %i\n", a[j], a[min]);
printf("min is changed: ");
min = j;
printf("min_j = %i\n", min);
}
}
tmp = a[i]; // three lines moved out of the loop
a[i] = a[min]; //
a[min] = tmp; //
}
return a;
}
La sortie est maintenant correcte.
Vous avez deux boucles, dans la boucle externe, vous définissez d'abord min, puis dans la boucle interne, le min a changé, ce qui a gâché la valeur min et rend votre code d'échange erroné. Vous pouvez supprimer tout le code sur min, utiliser directement i, j, puis cela devrait fonctionner. changement si (a [j]
public static class SelectionSort
{
static int min;
public static void Sort(int[] data)
{
for (int i = 0; i < data.Length; i++)
{
for (int j = 0; j < data.Length; j++)
{
min = j;
if (data[i] < data[j])
Swap(x: ref data[i], y: ref data[min]);
}
}
}
private static void Swap(ref int x, ref int y)
{
int temp = x;
x = y;
y = temp;
}
}
pouvez-vous donner un peu d'explication?
Est-ce toujours le même résultat pour les mêmes données? Ou un ensemble de données ne fonctionne-t-il pas toujours?
@WeatherVane Il semble que ce soit toujours la même chose.