Question
Write a program of the Selection Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:
1 2 3 4 5 6 7 |
SelectionSort(A) 1 for i = 0 to A.length-1 2 mini = i 3 for j = i to A.length-1 4 if A[j] < A[mini] 5 mini = j 6 swap A[i] and A[mini] |
Note that, indices for array elements are based on 0-origin.
Your program should also print the number of swap operations defined in line 6 of the pseudocode in the case where i ≠ mini.
Input
The first line of the input includes an integer N, the number of elements in the sequence.
In the second line, N elements of the sequence are given separated by space characters.
Output
The output consists of 2 lines.
In the first line, please print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.
In the second line, please print the number of swap operations.
Constraints
1 ≤ N ≤ 100
Sample Input 1
6
5 6 4 2 1 3
Sample Output 1
1 2 3 4 5 6
4
Sample Input 2
6
5 2 4 6 1 3
Sample Output 2
1 2 3 4 5 6
3
Meaning
Solution
简单选择排序,每次在第二层无序区中找出一个最小的数,放到第一层的下标i处。但是小标i也有可能是最小的数,所以也要来进行比较。
Coding
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 |
#include<iostream> using namespace std; void SelectionSort(int a[], int n ,int &sum) { int i, j, min; for ( i = 0; i < n-1; i++) { //第一层循环为无序区 min = i;//k记录当前的下标,到时需要交换 for ( j = i + 1; j < n; j++) { //第二层循环为有序区 if (a[j] < a[min]) min = j; //此时min便是最小的数 } if (min != i) { //为了防止最小数有两个,即最外层for循环i是最小数,无序区也有一个最小数,这样交换过来排序便不再稳定 swap(a[min], a[i]); sum++; } } } void Print(int a[], int n) { for (int i = 0; i < n; i++) { if (i > 0) cout << " "; cout << a[i]; } } int main() { int n, sum = 0; cin >> n; int a[105]; for (int i = 0; i < n; i++) cin >> a[i]; SelectionSort(a, n, sum); Print(a, n); cout << endl << sum << endl; } |