Ada has an array of n toys, each of which is either a ball, squeaker, or stuffed. She wants to sort all the toys in the array so that all the balls come before all the squeakers, which come before all the stuffeds. Find an algorithm that will sort the toys in linear time and with constant additional space.

Ada has an array of n toys, each of which is either a ball, squeaker, or stuffed. She wants to sort all the toys in the array so that all the balls come before all the squeakers, which come before all the stuffeds. Find an algorithm that will sort the toys in linear time and with constant additional space.

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter8: Arrays And Strings

Section: Chapter Questions

Problem 24PE

See similar textbooks

Similar questions

Write a program that randomly fills in 0s and 1s into a 6 * 6 matrix, prints the matrix, and finds the first row and first column with the least 1s.
The Sieve of Eratosthenes is an algorithm that finds all prime numbers up to a given limit, n. It works by creating an array of Booleans, flag, of size n+1, initializing the array to true (assuming every number is a prime number in the beginning), and iteratively traversing the numbers from 2 to n, setting the values of indices that are multiples of other numbers to false. Write a program using the algorithm above, and display all the prime numbers up to 50.
Consider a group of balls where each ball is one of k colors. You can assume that there is an equal number of balls of each color. Each ball, aside from its color, has a written integer on it. The numbers are in no way associated with the color. a) Devise an algorithm that orders all the balls according to colors in a way that no ball comes before a ball of a lighter color. In other words, how do you order balls from lightest to darkest, however, inside one group (i. e., one color), balls can be ordered in any way with respect to the number written on the ball. Design an algorithm and analyze it. b) Now take the output from (a), and also order balls within the color. How much time is needed for this step?
Isabel has an interesting way of summing up the values in an array A of n integers, where n is a power of two. She creates an array B of half the size of A and sets B[i] = A[2i] + A[2i + 1], for i = 0, 1,..., (n/2) – 1. If B has size 1, then she outputs B[0]. Otherwise, she replaces A with B, and repeats the process. What is the running time of her algorithm?
In this project, a matrix of integers is given where each cell represents a weight. You are asked to write a program thatfinds a continuous path that combines any element of the first row with any element of the last row in the matrix. Thus,the sum of items along the way is minimized. When the matrix is drawn in the usual way, the path goes absolutely down.As shown in the table below, it's legal to switch from each cell directly to one of the three cells below it. Can you make a program in c language ?
Given an array of integers of even length, your task is to split it into two arrays of equal length such that all the numbers are unique in each of them.There may be more than one possible answer, in which case you may return any of them. If there are no possible answers, return an empty array. Hint: Count the number of occurrences of each integer in a. If there are integers occurring more than twice, then there is no solution. Next, put the integers occurring twice into both answer arrays. Finally, put all other numbers in the answer arrays, following the condition that they should have equal sizes. Example For a = [2, 1, 2, 3, 3, 4], the output can be divideArray(a) = [[2, 1, 3], [2, 3, 4]]. Answers like [[1, 2, 3], [2, 3, 4]] or [[4, 2, 3], [3, 2, 1]] would also be considered correct. For a = [1, 2, 2, 1], the output can be divideArray(a) = [[1, 2], [2, 1]]. Again, there are other possible answers. For a = [2, 2, 3, 3, 2, 2], the output should be divideArray(a) = []. No matter how…
You are a movie theater manager. You are given a two-dimensional array with 6 rows and 6 columns - 36 elements with O value, that represent empty theater seats. All 36 tickets for session were sold, so you need to identify all of the seats with value 1. Write a program that replaces all O values in the given array, by 1 and outputs the resulting matrix. Use nested for-loops to iterate over two-dimensional matrix.
Write a program that prints an mxn matrix whose dimensions are specified by the user. Let the matrix values be random variables. You must use it within the repetition cycle. Example format: Enter dimension of matrix mxn: 2 4 The 2x4 matrix is : 1 2 3 4 5 6 7 8
Write a program that generates a 6-by-6 two-dimensionalmatrix filled with 0s and 1s, displays the matrix, and checks if every row andevery column have an even number of 1s.
Write a Java program to find continuous sub array of the given array whose sum is equal to a given number. For example, If {12, 5, 31, 9, 21, 8} is the given array and 45 is the given number, then you have to find continuous sub array in this array such that whose elements add up to 45. In this case, {5, 31, 9} is such sub array whose elements add up to 45.
solve with java?? We are given ages of 10 people from a random sample of population. The task is to find the sum of three eldest ages in the given sample of population u Input An Array consists of ages of 10 citizens. uOutput A number consist of sum of ages of three eldest citizens. Sample Input u55, 82, 54, 60, 15, 98, 38, 29, 13, 90 uSample Output 270
Let A={1,2,3...,10}. How many subsets B of A where B = │4│and the smallest element in B is 4? Write a computer program or develop an algorithm that lists all subsets according to the part (a). (Please display the all subsets).