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?

0 0
Add a comment Improve this question Transcribed image text
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.

Add a comment
Know the answer?
Add Answer to:
4. (10 points) Suppose we are given a sequence S of n elements, each of which...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • 3 Quicksort 10 points (5 points each) 1. Suppose that you are given an array A[1..n]...

    3 Quicksort 10 points (5 points each) 1. Suppose that you are given an array A[1..n] and that you want to sort it using quicksort. Further suppose that your algorithm could consult an oracle to predict what element to use as the pivot. Which element would it pick so that your algorithm would run as fast as possible? What is the running time given your pivot? 2. Run the partition algorithm to partition the array A (6,7,2,4, 10,8, 1,9)

  • Hi, I need help with the following question: Let S be a sequence of N elements...

    Hi, I need help with the following question: Let S be a sequence of N elements on which a total order relation is defined. Recall that an inversion in S is a pair of elements x and y such that x appears before y in S but x > y. Describe an algorithm running in O(n log n) time for determining the number of inversions in S.

  • Problem 1 (5+15 points) Consider the set P of n points and suppose we are given...

    Problem 1 (5+15 points) Consider the set P of n points and suppose we are given the points of P one point at a time. After receiving each point, we compute the convex hull of the points seen so far. (a) As a naive approach, we could run Graham’s scan once for each point, with a total running time of O(n2 log n). Write down the pesuedocode for this algorithm. (b) Develop an O(n2) algorithm to solve the problem. Write...

  • An array A[1,2,... ,n is unimodal if its consists of an increasing sequence followed by sequence...

    An array A[1,2,... ,n is unimodal if its consists of an increasing sequence followed by sequence a decreasing sequence. More precisely, there exists an index k є {1,2,… ,n} such that there exists an indes . AlE]< Ali1 for all 1 i< k, and Ai]Ali 1 for all k< i< n A1,2,..,n] in O(logn) time the loop invariant (s) that your algorithm maintains and show why they lead to the correctness Give an algorithm to compute the maximum element of...

  • (20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of...

    (20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of size 5. So n/5 groups. (b) Find the median of each group. (c) Find the median x of the n/5 medians by a recursive call to Select. (d) Call Partition with x as the pivot. (e) Make a recursive call to Select either on the smaller elements or larger elements (de- pending on the situation); if the pivot is the answer we are done....

  • 5. Answer the following. (a) (5 points) Suppose you are given a maxheap of n unique...

    5. Answer the following. (a) (5 points) Suppose you are given a maxheap of n unique numbers. Explain where will the smallest of these n numbers be located in the maxheap. Explain where will the second largest number be located on this maxheap. Please be specific. (b) (5 points) Suppose you are given an array A of n numbers, where all the elements of the array are already sorted in decreasing order. Is this a max-heap? Explain. (c) (5 points)...

  • Suppose you have an array of n elements containing three distinct keys, true, false, and maybe....

    Suppose you have an array of n elements containing three distinct keys, true, false, and maybe. Give an O(n) algorithm to rearrange the list so that all false elements precede the maybe elements, which in turn precede all true elements. You may use only constant extra space.

  • 1. (10 points) Write an efficient iterative (i.e., loop-based) function Fibonnaci(n) that returns the nth Fibonnaci...

    1. (10 points) Write an efficient iterative (i.e., loop-based) function Fibonnaci(n) that returns the nth Fibonnaci number. By definition Fibonnaci(0) is 1, Fibonnaci(1) is 1, Fibonnaci(2) is 2, Fibonnaci(3) is 3, Fibonnaci(4) is 5, and so on. Your function may only use a constant amount of memory (i.e. no auxiliary array). Argue that the running time of the function is Θ(n), i.e. the function is linear in n. 2. (10 points) Order the following functions by growth rate: N, \N,...

  • Suppose we are given two n-element sorted sequences A and B that may contain duplicate entries....

    Suppose we are given two n-element sorted sequences A and B that may contain duplicate entries. Describe an O(n)-time method for computing a sequence representing all elements in A or B with no duplicates.

  • 4) [15 points total (5 points each)] Assume you are given a sorted array A of n numbers, where A is indexed from 1 up t...

    4) [15 points total (5 points each)] Assume you are given a sorted array A of n numbers, where A is indexed from 1 up to n, anda number num which we wish to insert into A, in the proper sorted position. The function Search finds the minimum index i such that num should be inserted into Ali]. It searches the array sequentially until it finds the location i. Another function MakeRoom moves A[i], .., AIn] to Ali+1]...AIn+1] same sort...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT