Count Minimum Number of Move-to-Front Moves to Sort an Array in C++

We are given with an array of numbers between 1 to n. The goal here is to find the no. of ‘move to front’ operations required to sort the given array. The array has no repetition. The ‘move to front’ operation picks an element and places at first position, here at index 0.

We will traverse the array from end, if element is at the correct position then no move else move is required. For elements from 1 to n, the correct position in the array of element arr[i] should be at index i+1. arr[0] should be 1, arr[1] should be 2 and…….arr[n-1] should be n.

Input

Arr[]= { 4,3,2,1 }

Output

Minimum move-to-front operations: 3

Explanation

Pull 3, 3,4,2,1 count=1
Pull 2, 2,3,4,1 count=2
Pull 1, 1,2,3,4 count=3

Input

Arr[]= { 6,1,2,5,4,3 }

Output

Minimum move-to-front operations: 5

Explanation

Pull 5, 5,6,1,2,4,3 count=1
Pull 4, 4,5,6,1,2,3 count=2
Pull 3, ,4,5,6,1,2 count=3
Pull 2, 2,3,4,5,6,1 count=4
Pull 1, 1,2,3,4,5,6 count=5

Approach used in the below program is as follows

• Integer array Arr[] stores the numbers 1 to n.

• Integer variable size stores the length of array Arr[]

• Function movetoFront(int arr[], int n) takes an array and its length as input and returns the minimum number of ‘move-to-front’ operations required to sort that given array.

• Count variable is initialized with size of array as all elements can be moved in case of decreasing order array.

• Start traversing from the last index and moving towards the front, if element value is the same as count, (for sorted elements between 1 to n, n is last, n-1 is second last and so on) then decrement count as that element is at the correct position.

• In this way at the end of the loop, count has the desired result.

Example

 Live Demo

#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int movetoFront(int arr[], int n){
   //take count as all elements are correctly placed
   int count = n;
   // Traverse array from end
   for (int i=n-1; i >= 0; i--){
      // If current item is at its correct position,
         //decrement the count
      //range is 1 to n so every arr[i] should have value i+1
      //1 at 0 index, 2 at 1 index........
      if (arr[i] == count)
         count--;
   }
   return count;
}
int main(){
   int Arr[] = {5, 3, 4, 7, 2, 6, 1};
   int size = 7;
   cout <<"Minimum 'move-to-front' to sort array:"<< movetoFront(Arr, size);
   return 0;
}

Output

Minimum 'move-to-front' to sort array:6