Given a main() that reads user IDs (until -1), complete the Quicksort() and Partition() functions to sort the IDs in ascending order using theQuicksort algorithm, and output the sorted IDs one per line.Ex. If the input is:kaylasimmsjuliamyron1994kaylajones-1the output is:juliakaylajoneskaylasimmsmyron1994 1 # include 2 #include 3 #include 45 using namespace std;67 // TODO: Write the partitioning algorithm - pick the middle element as the8 //9 //10 //11 int Partition (vector &userIDs, int i, int k) {1213}1415 // TODO: Write the quicksort algorithm that recursively sorts the Low and16 //high partitions17 void Quicksort (vector &userIDs, int i, int k) {18pivot, compare the values using two index variables L and h (Low and high),initialized to the left and right sides of the current elements being sorted,and determine if a swap is necessary19}2021 int main() {22 vector userIDList;23string userID;2425cin >> userID;26while (userID != "-1") {2728293031}// Initial call to quicksort32 Quicksort (userIDList, 0, userIDList.size() - 1);mm muserIDList.push_back(userID);cin >> userID;3334 for (size_t i = 0; i < userIDList.size(); ++i) {35cout << userIDList.at (i) << endl;;36 }373839}mmmmreturn 0;

Name: Given a main() that reads user IDs (until -1), complete the Quicksort
Uploaded: 2024-03-20T06:51:23.000Z
Channel: Bartleby
Description: Given a main() that reads user IDs (until -1), complete the Quicksort() and Partition() functions to sort the IDs in ascending order using theQuicksort algorithm, and output the sorted IDs one per line.Ex. If the input is:kaylasimmsjuliamyron1994kay

Input: A list of user IDs terminated by "-1."Output: The sorted user IDs, one per line.1. Include…

Engineering

Computer Science

Given a main() that reads user IDs (until -1), complete the Quicksort() and Partition() functions to sort the IDs in ascending order using the Quicksort algorithm, and output the sorted IDs one per line. Ex. If the input is: kaylasimms julia myron1994 kaylajones -1 the output is: julia kaylajones kaylasimms myron1994

Given a main() that reads user IDs (until -1), complete the Quicksort() and Partition() functions to sort the IDs in ascending order using the Quicksort algorithm, and output the sorted IDs one per line. Ex. If the input is: kaylasimms julia myron1994 kaylajones -1 the output is: julia kaylajones kaylasimms myron1994

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: The program is the same as shown at the end of the Merge sort section, with the following changes:…

A: code is given below in CPP along with output and code screenshots

Q: Develop a merging implementation based on the following idea to reduce the required extra space to…

A: The goal of this question is to implement a merge sort algorithm with a reduced space requirement.…

Q: Overview To demonstrate you can implement the microservices architecture, write software comprised…

A: Hello student Answer will be in next step

Q: You are the sysadmin for a big tech company, and you have to estimate the amount of servers you need…

A: In Java:-Step-1: StartStep-2: Define a class Solution Step-2.1: Define function minMeetingRooms,…

Q: Consider the following BinaryTrie. Which nodes would have to change their jump pointers on add(0010)…

A: we need to find who will change their jump poiner.

Q: Write a C program mexp that multiplies a square matrix by itself a specified number of times. mexp…

A: #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { if (argc != 2)…

Q: Define a Python function which creates a dictionary where the keys are between the letters “a” and…

A: Please find the answer to the above question below:

Q: Create a merging implementation based on the following concept that lowers the additional space need…

A: The goal of the merging technique shown here is to maximise the usage of extra space while merging.…

Q: Develop a merge implementation that reduces the extra space requirement to max(M, N/M), based on the…

A: The goal of this question is to implement a merge sort algorithm with a reduced space requirement.…

Q: Figure 9-25 Flowchart for the binarysearch function binarySearch (Integer array[ ], Integer value,…

Q: Modify the FindBestPlan(S) function to create a function FindBestPlan(S, O), where O is a desired…

A: Define is_order_satisfied(S, O) Function:This function checks whether the current order of the input…

Topic Video

Question

Given a main() that reads user IDs (until -1), complete the Quicksort() and Partition() functions to sort the IDs in ascending order using the
Quicksort algorithm, and output the sorted IDs one per line.
Ex. If the input is:
kaylasimms
julia
myron1994
kaylajones
-1
the output is:
julia
kaylajones
kaylasimms
myron1994

1 # include <string>
2 #include <vector>
3 #include <iostream>
4
5 using namespace std;
6
7 // TODO: Write the partitioning algorithm - pick the middle element as the
8 //
9 //
10 //
11 int Partition (vector<string> &userIDs, int i, int k) {
12
13}
14
15 // TODO: Write the quicksort algorithm that recursively sorts the Low and
16 //
high partitions
17 void Quicksort (vector<string> &userIDs, int i, int k) {
18
pivot, compare the values using two index variables L and h (Low and high),
initialized to the left and right sides of the current elements being sorted,
and determine if a swap is necessary
19}
20
21 int main() {
22 vector<string> userIDList;
23
string userID;
24
25
cin >> userID;
26
while (userID != "-1") {
27
28
29
30
31
}
// Initial call to quicksort
32 Quicksort (userIDList, 0, userIDList.size() - 1);
mm m
userIDList.push_back(userID);
cin >> userID;
33
34 for (size_t i = 0; i < userIDList.size(); ++i) {
35
cout << userIDList.at (i) << endl;;
36 }
37
38
39}
mmmm
return 0;

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1: Providing the algorithm

VIEW

Step 2: Providing the source code

VIEW

Step 3: Providing the code screenshot

VIEW

Solution

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 3 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Implement external sort: for sort phase use normal sort, for merge phase use two way merge to merge n sorted files (merge2way(n)), for array sort use heapsort. Also write merge(f1, f2, f3) to merge two sorted files f1 and f2 into f3.. Write mergenway(n) method and print execution time of both merges for initial input file over 10MB data. A sample input is as follow:Note:First input is max array size for sort 10 84 82 52 80 96 85 75 75 82 87 92 89 57 94 93 92 63 99 87 72 73 56 74 50 84 62 72 55 86 75 74 100 83 60 53 68 89 67 66 65 72 94 73 54 98 96 85 75 75 82 87 92 89
The best case behaviour occurs for quick sort when the partition function splits the sequence of size n into subarrays of size: Select one: a.n/4 : 3n/4 b.n/4 : 3n/2 c.3n/8 : (5n/8) d.n/2 : (n/2)-1 e.n/2 : n/3
Using Java, 1. Implement external sort: for sort phase use normal sort, for merge phase use two way merge to merge n sorted files (merge2way(n)), for array sort use heapsort. Also write merge(f1, f2, f3) to merge two sorted files f1 and f2 into f3.. Write mergenway(n) method and print execution time of both merges for initial input file over 10MB data. A sample input is as follow:Note:Fist input is max array size for sort 10 84 82 52 80 96 85 75 75 82 87 92 89 57 94 93 92 63 99 87 72 73 56 74 50 84 62 72 55 86 75 74 100 83 60 53 68 89 67 66 65 72 94 73 54 98 96 85 75 75 82 87 92 89
JAVA Task, by using ArrayList The program reads manatee names from the standard input stream and from time to time prints a sorted portion of the list of names. All the manatee names in the input are given in the order in which the necropsy was performed. You can imagine a unique timestamp associated with each necropsy. The names are not necessarily unique (many of the manatees have the same name). Interspered in the standard input stream are queries that begin with the question mark character. Queries ask for an alphabetical list of manatee names to be printed to the standard output stream. The list depends only on the names upto that point in the input stream and does include any manatee names that appear in the input stream after the query. The list does not contain all the names of the previous necropsies, but only a selection of them. A query provides the names of two manatees, say A and B. The response to the query drops necropsies performed before the first named A and all the…
Question 8: (a) ' Implement the Merge function in Python. (b) Implement the MSort function in Python. (c) Implement the Partition function in Python. (d) Implement the Qsort function in Python. Test your functions with the below code. #Testing Sorts import random for x in range (0, 10) : L = [random.randint (0, 100) for k in range (0, 10) ] print ("Merge Input:", L) L = msort (L) print ("Result after Merge Sort:", L) x in range (0, 10) : L = [random.randint (0, 100) for k in range (0,10) ] print ("Quick Sort Input:", L) qsort (L, 0, len (L) -1) print ("Result After Quick Sort:", L)
Write a python program that stores current grades in a dictionary, with course codes as keys and percent grades as values. Start with an empty dictionary and then use a while loop to enable input of course codes and percent grades from the keyboard. Enter data for at least five courses. After entering the data, use a for loop and the keys to show the current status of all courses. This same loop should include code that enables determination of the worst course and the average of all courses. Both of these findings should be printed when the loop ends. The worst course should be dropped and reported. This being done, the program should use another loop and the items method to display the revised courses and grades and report the revised term average.
Consider a situation of a boarding gate of a plane where passengers are allowed to board on the place based on their age. All passengers are on a line (queue) to board on the place, however, the oldest one is always allowed to board first no matter when he/she got in the line (queue). In this case, you cannot sort the passengers by their age, however, you know that oldest ones are always at the top of the line. This is an example of a priority queue where data will be accessed and processed based on their level of priority. Suppose you need to organize such type of data so that the data in highest priority can be accessed in a constant time, O(1). What type of data structure would you use in such cases? Justify your answer.