#include <iostream>
#include <vector>
using namespace std;

int selectionSort(vector<int>& arr) {
	int n = arr.size();
	int opcount = 0;
	int temp; // for swaps

	// Treat the array like 2 subarrays, a sorted part and an unsorted part.
	// On the first iteration, move the minimum value to the beginning of the array.
	// This single item is the sorted subarray.
	// Move the boundary of unsorted subarray each iteration.
	for (int i = 0; i < n - 1; i++) {
		// Find the minimum element in unsorted array
		int min_idx = i;
		// start at the next element each time, moving the boundary.
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < arr[min_idx]) {
				min_idx = j;
			}
		}

		// Swap the found minimum element with the first element of the unsorted part
		if (min_idx != i) {
			temp = arr[i];
			arr[i] = arr[min_idx];
			arr[min_idx] = temp;
			opcount++;
		}

		// Output the state of the partially sorted array:
		cout << "\nPartially sorted array:\n";
		for (int x = 0; x < n; x++) {
			cout << "[" << x << "]: " << arr[x] << endl;
		}
	}
	return opcount;
}

int main() {
	vector<int> data = {64, 32, 16, 128, 2, 8, 4, 1}; // compile with: -std=c++11
	int opcount = 0;

	cout << "Original vector:\n";
	for (int x = 0; x < data.size(); x++) {
		cout << "[" << x << "]: " << data[x] << endl;
	}

	opcount = selectionSort(data);
	cout << "\nSwap operations performed: " << opcount << endl;

	cout << "\nSorted array:\n";
	for (int x = 0; x < data.size(); x++) {
		cout << "[" << x << "]: " << data[x] << endl;
	}

	return 0;
}