Selection Sort

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:

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.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 110;
int a[MAX];
int sum;
void SelectionSort(int a[], int n)
{
	int mini;
	for(int i = 0; i < n; ++ i)
	{
		mini = i;
		for(int j = i; j < n; ++ j)
		{
			if(a[j] < a[mini])
			{
				mini = j;
			}
		}
		swap(a[i], a[mini]);
		if(i != mini)
		{
			sum ++;
		}
	}
}
int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; ++ i)
	{
		cin >> a[i];
	}
	
	SelectionSort(a, n);
	
	for(int i = 0; i < n; ++ i)
	{
		if(i == n - 1)
			cout << a[i];
		else
			cout << a[i] << " ";
	}
	cout << endl;
	cout << sum << endl;
	
	return 0;
}

　　

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄