Given an an unsorted array, sort the given array. You are allowed to do only following operation on array:
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);
}
}
}
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