Friday, February 13, 2015

Pancake sorting

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);
             }
     }

}

No comments:

Post a Comment