Question

4. (10 points) Suppose we are given a sequence S of n elements, each of which is colored red or blue. Assuming S is represented by an array, give a linear-time in-place algorithm for ordering S so that all the blue elements are listed before all the red elements. What is the running time of your method?

Answer 1

COPY TO CODE HERE:

To segregate all the blue and red elements, we can devise a linear time algortihm using the below given method. For this algorithm let us assume, 0 represents Blue color and 1 represents Red color. Here are the steps of the algorithm:

Step 1: Let left_index = 0 and right_index = n-1

Step 2: Do the following steps while left_index < right_index

Step 3: If S[left_index] has 0 in it, then increment left_index by 1.

Step 4: If S[right_index] has 1 in it, then decrement right_index by 1.

Step 5: If left_index < right_index, then swap S[left_index] with S[right_index].

Here is the implementation of the following algorithm in C++:

#include<iostream>

#include<vector>

#include<algorithm>

int main()

{

std::vector<int> S = {0, 1, 0, 1, 1, 1};

int n = S.size();

std::size_t left_index = 0;

std::size_t right_index = n-1;

while (left_index < right_index)

{

while (S[left_index] == 0 && left_index < right_index)

left_index++;

while (S[right_index] == 1 && left_index < right_index)

right_index--;

if (left_index < right_index)

{

std::swap(S[left_index], S[right_index]);

left_index++;

right_index--;

}

}

for (std::size_t i = 0; i < S.size(); i++)

std::cout << S[i];

return 0;

}

The time complexity of the above algorithm is O(n) and space complexity is O(1)

THANK YOU.