#include <iostream>
using namespace std;

void cycleSort (int arr[], int n)
{
    // count number of memory writes
    int writes = 0;

    // traverse array elements and put it to on
    // the right place
    for (int cycle_start=0; cycle_start<=n-2; cycle_start++)
    {

        int item = arr[cycle_start];

        cout<<"item 1: "<<arr[cycle_start]<<endl;


        int pos = cycle_start;

        for (int i = cycle_start+1; i<n; i++)
            if (arr[i] < item)
                pos++;

       cout<<"Pos 1 value "<<pos<<" and array value at pos is "<<arr[pos] <<endl;

        if (pos == cycle_start)
            continue;


        while (item == arr[pos])
            pos += 1;

        cout<<"array element at pos 1: "<<arr[pos]<<endl;

        if (pos != cycle_start)
        {
            cout<<"inside first swap"<<endl;
            swap(item, arr[pos]);
            writes++;
        }

        for(int k=0; k<n; k++)
        cout<<arr[k]<<"\t";

        cout<<endl;


        while (pos != cycle_start)
        {

            cout<<"inside while 2"<<endl;

            cout<<"item 2: "<<arr[cycle_start]<<endl;

            pos = cycle_start;


            for (int i = cycle_start+1; i<n; i++)
                if (arr[i] < item)
                    cout<<"Pos 2: "<<pos++;

            cout<<endl;


            while (item == arr[pos])
            {
                 pos += 1;
                 cout<<"inside while 3"<<endl;
            }


            if (item != arr[pos])
            {
                swap(item, arr[pos]);
                cout<<"inside if 2"<<endl;
                writes++;
            }
        }


    }

    // Number of memory writes or swaps
    // cout << writes << endl ;
}

int main()
{
    int arr[] = {7,2,1,3,0,7,-1,7,4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cycleSort(arr,  n) ;

    cout << "After sort : " <<endl;
    for (int i =0; i<n; i++)
        cout << arr[i] << " ";
    return 0;
}