Partition Array

cpp.sh

// Example program
#include <iostream>
#include <string>
#include <vector>

using namespace std;


void print(vector<int> A)
{
    for(int tmp : A)
    {
        cout<<tmp<<" ";   
    }
    cout<<endl;
}

int partition(vector<int>& A, int s, int e)
{
    int l = s;
    int r = e;
    int pivot = A[s];

    while(l < r)
    {
        while(l<r && A[r] >= pivot)
        {
            r--;   
        }
        A[l] = A[r];
        print(A);

        while(l<r && A[l] <= pivot)
        {
            l++;   
        }
        A[r] = A[l];
        print(A);
        cout<<l<<" "<<r<<endl;
    }

    A[l] = pivot;
    return l;
}

int main()
{
  vector<int> A = {4, 8, 4, 7, 4, 1, 1, 9};
  int pos = partition(A, 0, 7);
  for(int tmp : A)
  {
        cout<<tmp<<" ";   
  }
  cout<<endl;
  cout<<pos<<endl;

  return 1;
}