oladushkiSort

#include <iostream>

int main()
{
    const int arrSize{10};
    int arr[arrSize]{5,7,9,8,1,3,2,4,6,1};
    //int arr[arrSize]{1,2,3,4,5,6,7,8,9,10};
    //int arr[arrSize]{10,9,8,7,6,5,4,3,2,1};
    //int arr[arrSize]{};
    int tmp;

    for (int i{0} ; i<arrSize; ++i){std::cout << arr[i] << ' '; }; std::cout << '\n';

    for (int tail{arrSize - 1}; tail >=0; --tail)
    {
        int maxIdx{tail}; // Find max element from tail to head
        for (int maxTail{tail}; maxTail>=0; --maxTail)
        {
            if (arr[maxTail] > arr[maxIdx]) {maxIdx = maxTail;}
        }
        std::cout << "Max: " << arr[maxIdx] << '\n';
        if (maxIdx != tail)//If max element already at tail position no need to move anything
        {
            if (maxIdx !=0) //If max element not at the head position, need turn stack from max element
            {
                for (int turnTail{maxIdx}, turnHead=0; turnTail > turnHead; --turnTail, ++turnHead)
                {
                    tmp = arr[turnHead];
                    arr[turnHead] = arr[turnTail];
                    arr[turnTail] = tmp;
                }
                for (int i{0} ; i<arrSize; ++i){std::cout << arr[i] << ' '; }; std::cout << '\n';
            }
            for (int turnTail{tail}, turnHead{0}; turnTail > turnHead; --turnTail, ++turnHead) //Turn stack again from tail position, so max element apear at tail
            {
                tmp = arr[turnHead];
                arr[turnHead] = arr[turnTail];
                arr[turnTail] = tmp;
            }
            for (int i{0} ; i<arrSize; ++i){std::cout << arr[i] << ' '; }; std::cout << '\n';
        }

    }
    for (int i{0} ; i<arrSize; ++i){std::cout << arr[i] << ' '; }; std::cout << '\n';
}