-Algorithme entier en place. Le tri sélectif convient aux petits fichiers. -Répétez la recherche de la valeur minimale dans l'ordre croissant (ordre le plus petit) et la valeur maximale dans l'ordre décroissant (ordre le plus grand). -N-1 échanges sont effectués pour aligner n éléments. Comparaisons N-1 à la passe 1 Comparaisons N-2 au passage 2 ... (car les données à comparer sont réduites de 1) Par conséquent, (n-1) + (n-2) + ... + 1 = n (n-1) / 2 comparaisons sont effectuées.
· Facile à comprendre · Tri sur place (aucun stockage supplémentaire requis) ・ Plus rapide que le tri à bulles
・ Détérioration du montant du calcul due à l'échelle: O (n²)
Implémenter en langage C. Afficher les scores en anglais et en mathématiques par ordre décroissant (le plus grand). Utilisez le tri sélectif pour trier les données.
selection_sort.c
#include <stdio.h>
#define NMAX 1000
int main(){
int eigo[NMAX], math[NMAX], gokei[NMAX], n, max, work;
printf("data="); scanf("%d", &n);
for (int i = 0; i <n ; ++i) {
printf("[%3dbanme]=", i); scanf("%d %d", &eigo[i], &math[i]);
gokei[i]=eigo[i]+math[i];
}
for (int i = 0; i <n-1 ; ++i) {
max=i;
for (int j = i+1; j <n ; ++j) {
if (gokei[j]>gokei[max]) max=j;
}
if(i!=max) {
work=eigo[i];eigo[i]=eigo[max];eigo[max]=work;
work=math[i];math[i]=math[max];math[max]=work;
work=gokei[i];gokei[i]=gokei[max];gokei[max]=work;
}
}
printf("*** RESULTS ***\n");
printf("RANK ENGLISH MATH TOTAL\n");
for (int i = 0; i <n ; ++i) {
printf("%4d%6d%6d%6d\n", i, eigo[i], math[i], gokei[i]);
}
}
| type | Montant du calcul |
|---|---|
| Montant de calcul dans le pire des cas | O(n²) |
| Meilleur calcul du temps | O(n) |
| Montant moyen du calcul | O(n²) |
| Pire calcul spatio-temporel | O(1)Zone auxiliaire |
Je peux l'ajouter si quelque chose se produit à nouveau
Recommended Posts