Rearrange using Another Approach

Software Development
#1

Another Approach:

  1. Nav­i­gate through the array.
  2. Check if a[i] = -1, if yes then ignore it.
  3. If a[i] != -1, Check if element a[i] is at its cor­rect posi­tion (i=A[i]) . If yes then ignore it.
  4. If a[i] != -1 and ele­ment a[i] is not at its cor­rect posi­tion (i!=A[i]) then place it to its correct posi­tion, but there are two conditions:
  • Either A[i] is vacate , means A[i] = -1 , then just put A[i] = i .
  • OR A[i] is not vacate , means A[i] = x , then int y=x put A[i] = i . Now, we need to place y to its cor­rect place, so repeat from step 3.

Below is the implementation for the above approach:

  • C++

// C++ program for rearrange an

// array such that arr[i] = i.

#include <bits/stdc++.h>

using namespace std;

// Function to rearrange an array

// such that arr[i] = i.

void fixArray( int A[], int len)

{

`` for ( int i = 0; i < len; i++)

`` {

`` if (A[i] != -1 && A[i] != i)

`` {

`` int x = A[i];

`` // check if desired place

`` // is not vacate

`` while (A[x] != -1 && A[x] != x)

`` {

`` // store the value from

`` // desired place

`` int y = A[x];

`` // place the x to its correct

`` // position

`` A[x] = x;

`` // now y will become x, now

`` // search the place for x

`` x = y;

`` }

`` // place the x to its correct

`` // position

`` A[x] = x;

`` // check if while loop hasn't

`` // set the correct value at A[i]

`` if (A[i] != i)

`` {

`` // if not then put -1 at

`` // the vacated place

`` A[i] = -1;

`` }

`` }

`` }

}

// Driver code

int main()

{

`` int A[] = { -1, -1, 6, 1, 9,

`` 3, 2, -1, 4, -1 };

`` int len = sizeof (A) / sizeof (A[0]);

`` // Function Call

`` fixArray(A, len);

`` // Print the output

`` for ( int i = 0; i < len; i++)

`` cout << A[i] << " " ;

}

Output

-1 1 2 3 4 -1 6 -1 -1 9