#include <iostream>
using namespace std;

int main() {
    int arr[] = {2, 3, 4, 1, 9, 5, 1, 2, 6, 8, 1, 3};
    int arrLength = 12;
    for (int i = 0; i < arrLength; i++)
    {
       int minPos = -1;
       for (int j = i; j < arrLength; j++)
          // either it's the first element, or it's greater than the last element
          //   and either it's the first such element we find, or smaller than the best one
          if ((i == 0 || arr[j] > arr[i-1]) && 
              (minPos == -1 || arr[j] < arr[minPos]))
          {
             minPos = j;
          }

       // no more elements to sort
       if (minPos == -1)
          break;

       int temp = arr[i];
       arr[i] = arr[minPos];
       arr[minPos] = temp;
    }
    for (int i = 0; i < arrLength; i++)
       cout << arr[i] << " ";
	return 0;
}