Given code that reads user IDs (until -1), complete the quicksort() and partition() functions to sort the IDs in ascending order using the Quicksort algorithm. Increment the global variable num_calls in quicksort() to keep track of how many times quicksort() is called. The given code outputs num_calls followed by the sorted IDs. Ex: If the input is: kaylasimms julia myron1994 kaylajones -1 the output is: 7 julia kaylajones kaylasimms myron1994 I am having issues getting the count correct. What should I be looking at to adjust the count?
Given code that reads user IDs (until -1), complete the quicksort() and partition() functions to sort the IDs in ascending order using the Quicksort algorithm. Increment the global variable num_calls in quicksort() to keep track of how many times quicksort() is called. The given code outputs num_calls followed by the sorted IDs. Ex: If the input is: kaylasimms julia myron1994 kaylajones -1 the output is: 7 julia kaylajones kaylasimms myron1994 I am having issues getting the count correct. What should I be looking at to adjust the count?
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Given code that reads user IDs (until -1), complete the quicksort() and partition() functions to sort the IDs in ascending order using the Quicksort
Ex: If the input is:
kaylasimms
julia myron1994
kaylajones
-1
the output is:
7
julia
kaylajones
kaylasimms
myron1994
I am having issues getting the count correct. What should I be looking at to adjust the count?
Transcribed Image Text:7
browneliza
jamessusan
jonessteve
smithamy
smythjune
9
browneliza
jamessusan
jonessteve
smithamy
smythjune
![1 # Global variable
2 num_calls = 0
3 # TODO: Write the partitioning algorithm - pick the middle element as the
pivot, compare the values using two index variables 1 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
4
5 #
6 #
7 def partition (user_ids, i, k):
low = (i-1)
mid = (i + k) //2
pivot = user_ids[mid]
user_ids[mid], user_ids[k] = user_ids[k], user_ids[mid]
for j in range (i ,k):
if user_ids[j] <= pivot:
8
9
10
11
12
13
14
low = low + 1
15
user_ids[low],user_ids[j] = user_ids[j],user_ids[low]
user_ids[low+1],user_ids[k] = user_ids[k],user_ids[low+1]
return ( loW+1 )
16
17
18 # TODO: Write the quicksort algorithm that recursively sorts the low and
high partitions. Add 1 to num_calls each time quisksort() is called
19 #
20 def quicksort(user_ids, i, k):
global num_calls
num_calls = num_calls + 1
if ikk:
pivot_index = partition(user_ids,i,k)
quicksort (user_ids, i, pivot_index-1)
quicksort (user_ids, pivot_index+1, k)
21
22
23
24
25
26
27 if
main ":
name
user_ids = []
user_id = input()
while user id != "-1":
user_ids.append(user_id)
user_id = input ()
# Initial call to quicksort
quicksort (user_ids, 0, len(user_ids) - 1)
# Print number of calls to quicksort
print(num_calls)|
28
29
30
31
32
33
34
35
36
37
# Print sorted user ids
for user id in user ids:
print (user_id)
38
39
40](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F2bc2a3ad-b0fb-46d0-8be8-5188cce94b42%2F1d333ece-2326-471c-9f50-21f8fe09f678%2Ffegs12p_processed.png&w=3840&q=75)
Transcribed Image Text:1 # Global variable
2 num_calls = 0
3 # TODO: Write the partitioning algorithm - pick the middle element as the
pivot, compare the values using two index variables 1 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
4
5 #
6 #
7 def partition (user_ids, i, k):
low = (i-1)
mid = (i + k) //2
pivot = user_ids[mid]
user_ids[mid], user_ids[k] = user_ids[k], user_ids[mid]
for j in range (i ,k):
if user_ids[j] <= pivot:
8
9
10
11
12
13
14
low = low + 1
15
user_ids[low],user_ids[j] = user_ids[j],user_ids[low]
user_ids[low+1],user_ids[k] = user_ids[k],user_ids[low+1]
return ( loW+1 )
16
17
18 # TODO: Write the quicksort algorithm that recursively sorts the low and
high partitions. Add 1 to num_calls each time quisksort() is called
19 #
20 def quicksort(user_ids, i, k):
global num_calls
num_calls = num_calls + 1
if ikk:
pivot_index = partition(user_ids,i,k)
quicksort (user_ids, i, pivot_index-1)
quicksort (user_ids, pivot_index+1, k)
21
22
23
24
25
26
27 if
main ":
name
user_ids = []
user_id = input()
while user id != "-1":
user_ids.append(user_id)
user_id = input ()
# Initial call to quicksort
quicksort (user_ids, 0, len(user_ids) - 1)
# Print number of calls to quicksort
print(num_calls)|
28
29
30
31
32
33
34
35
36
37
# Print sorted user ids
for user id in user ids:
print (user_id)
38
39
40
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!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 2 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY