Swap a Number with 0

/***

Imagine you have a parking place with n slots and n-1 cars numbered from 1..n-1.

The free slot is represented by 0 in the problem. If you want to rearrange the cars,

you can only move one car at a time into the empty slot, which is equivalent to “swap a number with 0”.

Example:

src={1,0,3,2}; tgt={0,1,2,3};

1230

0123

IDEA:

src[i] = 0;

int target = tgt[i];

find target in src and swap with 0;

if zero is at ideal position, find the next wrong position and swap

if all number is at the ideal position, finish

***/

#include<iostream>

using namespace std;

void swap(int *a, int *b) {

       int t = *a;

       *a = *b;

       *b = t;

}

int check(int *src, int *tgt, int sz) {

       for(int i=0; i<sz; i++) {

              if(src[i] != tgt[i]) return i;

       }

       return sz;

}

int find_zero(int *src, int *tgt, int sz) {

       for(int i = 0; i<sz; i++) {

              if(src[i] == 0) return i;

       }

       return -1;

}

int find_index(int *src, int t, int sz) {

       for(int i = 0; i<sz; i++) {

              if(src[i] == t) return i;

       }

}

void getTarget(int *src, int *tgt, int sz) {

       int t = find_zero(src, tgt, sz);

       while(true) {

              if(tgt[t] == 0) {

                     int id = check(src, tgt, sz); //O(n)

                     if(id != sz) {

                           swap(&src[t], &src[id]);

                           t = id;

                     }

                     else return;

              } else {

                     int idx = find_index(src, tgt[t], sz); //O(n)

                     swap(&src[t], &src[idx]);

                     t = idx;

              }

       }

}

void main() {

       int src[] = {1,0,3,2};

       int tgt[] = {0,1,2,3};

       int sz = sizeof(src) / sizeof(int);

       getTarget(src, tgt, sz);

       for (int i = 0; i<sz; i++) cout<<src[i]<<endl;

}