Given an an unsorted array, sort the given array. You are allowed to do only following operation on array:

{

int start = 0;

while(start < i)

{

swap(arr[start], arr[i]);

--i;

++start;

}

}

int findMaxIndex(int *arr, int n)

{

int max = 0;

for(int i = 0; i < n; ++i)

{

if(arr[i] > arr[max])

max = i;

}

return max;

}

void panCakeSort(int *arr, int n)

{

for(int currSize = n; currSize > 1; --currSize)

{

int mi = findMaxIndex(arr, currSize);

if(mi != currSize - 1)

{

rev(arr, mi);

rev(arr, currSize - 1);

}

}

}

**rev(arr, i): Reverse arr from 0 to i****Implementation:****void rev(int *arr, int i)**

{

int start = 0;

while(start < i)

{

swap(arr[start], arr[i]);

--i;

++start;

}

}

int findMaxIndex(int *arr, int n)

{

int max = 0;

for(int i = 0; i < n; ++i)

{

if(arr[i] > arr[max])

max = i;

}

return max;

}

void panCakeSort(int *arr, int n)

{

for(int currSize = n; currSize > 1; --currSize)

{

int mi = findMaxIndex(arr, currSize);

if(mi != currSize - 1)

{

rev(arr, mi);

rev(arr, currSize - 1);

}

}

}

## No comments:

## Post a Comment