Arrange elements in an array in a specific order

Question

Found this interview question on Careercup

Given an array A with n integers. Rearrange array such that A[0]<=A[1]>=A[2]<=A[3]>=A[4]<=A[5] and so on

Edit: Array is not sorted and You have to do it in linear time O(N)

I am unable to find a solution in linear time, the closest I get is sort the array and then rearrange elements. Anyone has idea how it can be done in linear time? Can this be even done in linear time?

My proposed solution is to sort the array in nlogn time and then rearrange every odd element i with i-1 and i+1 alternatively.

Answer 1

Use quickselect to find the median of the array in O(n). This will allow you to divide the array in two equal (or almost equal) parts: those who are less than or equal to the median (A) up to n/2 elements, and the rest (B), that will be, by definition, greater than or equal to the median.

Arrange the array using this two halves like the following:

A B A B A B A

This will be correct, because every item A will be less than or equal to every B, by definition.

Answer 2

You can use this function (the code is in Swift) to arrange the array in a Wave Form in time O(n).

func wave(inout list: [Int]) {
    let evenIndexes = (0..<list.count).filter { $0 % 2 == 0 }

    for index in evenIndexes {
        if index > 0 && list[index] > list[index-1] {
            swap(&list[index], &list[index-1])
        }

        if index < list.count - 1 && list[index] > list[index+1] {
            swap(&list[index], &list[index+1])
        }
    }
}

This solution is based on the algorithm described here.

Test

var test0 = [1,2,3,4,5,6]
wave(&test0)
print(test0) // [1, 3, 2, 5, 4, 6]

var test1 = [4, 6, 2, 1, 3, 7]
wave(&test1)
print(test1) // [4, 6, 1, 3, 2, 7]

var test2 = [20, 9, 4, 2, 0]
wave(&test2)
print(test2) // [9, 20, 2, 4, 0]

Time complexity

The function has a for loop executed n/2 times (only for the even indexes). So the for loop has time complexity O(n).

Inside the for loop we found a couple of if then statement, both are executed in constante time so O(1).

So the time complexity is O(n) * O(1) = O(n) where n is the number of elements in the input array.

Answer 3

C# implementation of O(n) solution with usage of NthElement algorithm:

public void WaveSortTest(int[] a)
{
    var nthElement = NthElement(a, a.Length / 2);
    var element = a[nthElement];

    var odd = 1;
    var even = 0;
    var r = new int[a.Length];
    for (int i = 0; i < a.Length; i++)
    {
        if (a[i] <= element)
        {
            r[even] = a[i];
            even += 2;
        }
        else
        {
            r[odd] = a[i];
            odd += 2;
        }
    }

    PrintArray(r);
}

private static readonly Random _rnd = new Random((int)DateTime.Today.ToFileTimeUtc());

private static int NthElement(int[] arr, int k)
{
    return NthElement(arr, 0, arr.Length, k);
}

private static int NthElement(int[] arr, int low, int high, int k)
{
    var pos = low + _rnd.Next(high - low);
    Swap(arr, pos, high - 1);

    var i = Partition(arr, low, high);

    if (k < i)
    {
        return NthElement(arr, low, i, k);
    }
    if (k > i)
    {
        return NthElement(arr, i + 1, high, k);
    }
    return i;
}

private static int Partition(int[] arr, int low, int high)
{
    var i = low - 1;
    for (var j = low; j < high; j++)
    {
        if (arr[j] <= arr[high - 1])
        {
            i++;
            Swap(arr, i, j);
        }
    }
    return i;
}

private static void Swap<T>(T[] a, int first, int second)
{
    var t = a[first];
    a[first] = a[second];
    a[second] = t;
}

private static void PrintArray(IEnumerable<int> arr)
{
    foreach (var item in arr)
    {
        Console.Write(item + " ");
    }
    Console.WriteLine();
}