-In-place integer algorithm. Selection sort is suitable for small files. -Repeat finding the minimum value in ascending order (smallest order) and the maximum value in descending order (largest order). -N-1 exchanges are performed to align n elements. N-1 comparisons on pass 1 N-2 comparisons in pass 2 ... (because the data to be compared is reduced by 1) Therefore, (n-1) + (n-2) + ... + 1 = n (n-1) / 2 comparisons are performed.
・ Easy to understand · In-place sort (no additional storage required) ・ Faster than bubble sort
・ Deterioration of computational complexity due to scale: O (n²)
Implement in C language. Display English and math scores in descending order (largest order). Use selection sort to sort the data.
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 | Computational complexity |
|---|---|
| Worst case complexity | O(n²) |
| Best time complexity | O(n) |
| Average complexity | O(n²) |
| Worst spatiotemporal complexity | O(1)Auxiliary area |
I may add it if something happens again
Recommended Posts