1 # Read integers into a list and return the list. 2 def read_nums (): 3 4 5 6 # Output the content of a list, separated by spaces. 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 56 57 58 59 60 61 62 63 64 65 nums input().split() return [int (num) for num in nums] 66 67 68 69 70 71 def print_nums (numbers): for num in numbers: print (num, end-' ') print() def merge(numbers, i, j, k): merged_size = ki + 1 merged_numbers = [] for 1 in range (merged_size): merged_numbers.append(0) merge_pos=0 left_posi right_posj+1 while left_pos <- j and right_pos <= k: if numbers [left_pos] < numbers [right_pos]: merged_numbers [merge_pos] = numbers [left_pos] left_pos=left_pos + 1 else: merged_numbers [merge_pos] = numbers [right_pos] right pos right_pos + 1 merge_pos merge_pos + 1 while left_pos <- j: merged_numbers [merge_pos] = numbers [left_pos] left pos left_pos + 1 merge_pos merge_pos + 1 while right pos <- k: merged_numbers [merge_pos] = numbers [right_pos] right pos right_pos+1 merge_pos merge_pos + 1 47 48 def merge_sort (numbers, i, k): 49 j - 0 50 if i < k: 51 52 53 54 55 merge_pos=0 while merge_pos< merged_size: numbers [i + merge_pos] - merged_numbers [merge_pos] merge_pos= merge_pos + 1 j (i + k) // 2 # Trace output added to code in book print(i, j, "|", j + 1, k) merge_sort (numbers, i, j) merge_sort (numbers, j+1, k) merge (numbers, i, j, k) if_name_ == '___main__': numbers read_nums () print ('unsorted:', end-' ') print_nums (numbers) print() merge_sort (numbers, 0, len(numbers) - 1) print ('\nsorted:', end-' ') print_nums (numbers)
1 # Read integers into a list and return the list. 2 def read_nums (): 3 4 5 6 # Output the content of a list, separated by spaces. 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 56 57 58 59 60 61 62 63 64 65 nums input().split() return [int (num) for num in nums] 66 67 68 69 70 71 def print_nums (numbers): for num in numbers: print (num, end-' ') print() def merge(numbers, i, j, k): merged_size = ki + 1 merged_numbers = [] for 1 in range (merged_size): merged_numbers.append(0) merge_pos=0 left_posi right_posj+1 while left_pos <- j and right_pos <= k: if numbers [left_pos] < numbers [right_pos]: merged_numbers [merge_pos] = numbers [left_pos] left_pos=left_pos + 1 else: merged_numbers [merge_pos] = numbers [right_pos] right pos right_pos + 1 merge_pos merge_pos + 1 while left_pos <- j: merged_numbers [merge_pos] = numbers [left_pos] left pos left_pos + 1 merge_pos merge_pos + 1 while right pos <- k: merged_numbers [merge_pos] = numbers [right_pos] right pos right_pos+1 merge_pos merge_pos + 1 47 48 def merge_sort (numbers, i, k): 49 j - 0 50 if i < k: 51 52 53 54 55 merge_pos=0 while merge_pos< merged_size: numbers [i + merge_pos] - merged_numbers [merge_pos] merge_pos= merge_pos + 1 j (i + k) // 2 # Trace output added to code in book print(i, j, "|", j + 1, k) merge_sort (numbers, i, j) merge_sort (numbers, j+1, k) merge (numbers, i, j, k) if_name_ == '___main__': numbers read_nums () print ('unsorted:', end-' ') print_nums (numbers) print() merge_sort (numbers, 0, len(numbers) - 1) print ('\nsorted:', end-' ') print_nums (numbers)
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
Related questions
Question
Can you help me solve this question with the code i have given
![1 # Read integers into a list and return the list.
2 def read_nums ():
3
4
5
6
7
8
9
15
16
17
18
19
20
21
22
23
24
25
26
10
11
12 def merge(numbers, i, j, k):
merged_size = k - 1 + 1
i
13
14
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
nums = input().split()
return [int (num) for num in nums]
#Output the content of a list,
def print_nums (numbers):
for num in numbers:
print (num, end-' ')
print()
if
if
merged_numbers = []
for 1 in range (merged_size):
merged_numbers.append(0)
merge_pos=0
left_pos= i
right_pos= j + 1
while left_pos <= j and right_pos <= k:
if numbers [left_pos] < numbers [right_pos]:
merged_numbers [merge_pos] = numbers [left_pos]
left_pos=left_pos + 1
else:
separated by spaces.
merged_numbers [merge_pos] = numbers [right_pos]
right_pos= right_pos + 1
merge_pos= merge_pos + 1
while left_pos <= j:
merged_numbers [merge_pos] = numbers [left_pos]
left_pos=left_pos + 1
merge_pos= merge_pos + 1
while right_pos <= k:
merged_numbers [merge_pos] = numbers [right_pos]
right_pos= right_pos + 1
merge_pos= merge_pos + 1
def merge_sort (numbers, i, k):
j = 0
if i < k:
merge_pos= 0
while merge_pos < merged_size:
numbers [i+merge_pos] = merged_numbers [merge_pos]
merge_pos= merge_pos + 1
j = (i + k) // 2
# Trace output added to code in book
print(i, j, "|", j + 1, k)
merge_sort (numbers, i, j)
merge_sort (numbers, j+1, k)
merge(numbers, i, j, k)
__name=
_____main__':
numbers = read_nums ()
print ('unsorted: ', end=' ')
print_nums (numbers)
print()
merge_sort (numbers, 0, len(numbers) - 1)
print ('\nsorted: ', end-' ')
print_nums (numbers)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F72e67566-6965-4009-80e3-e9c4492e1c52%2F9c4ac942-cdb7-4413-aaea-e89087c26108%2Fcjq0kdd_processed.png&w=3840&q=75)
Transcribed Image Text:1 # Read integers into a list and return the list.
2 def read_nums ():
3
4
5
6
7
8
9
15
16
17
18
19
20
21
22
23
24
25
26
10
11
12 def merge(numbers, i, j, k):
merged_size = k - 1 + 1
i
13
14
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
nums = input().split()
return [int (num) for num in nums]
#Output the content of a list,
def print_nums (numbers):
for num in numbers:
print (num, end-' ')
print()
if
if
merged_numbers = []
for 1 in range (merged_size):
merged_numbers.append(0)
merge_pos=0
left_pos= i
right_pos= j + 1
while left_pos <= j and right_pos <= k:
if numbers [left_pos] < numbers [right_pos]:
merged_numbers [merge_pos] = numbers [left_pos]
left_pos=left_pos + 1
else:
separated by spaces.
merged_numbers [merge_pos] = numbers [right_pos]
right_pos= right_pos + 1
merge_pos= merge_pos + 1
while left_pos <= j:
merged_numbers [merge_pos] = numbers [left_pos]
left_pos=left_pos + 1
merge_pos= merge_pos + 1
while right_pos <= k:
merged_numbers [merge_pos] = numbers [right_pos]
right_pos= right_pos + 1
merge_pos= merge_pos + 1
def merge_sort (numbers, i, k):
j = 0
if i < k:
merge_pos= 0
while merge_pos < merged_size:
numbers [i+merge_pos] = merged_numbers [merge_pos]
merge_pos= merge_pos + 1
j = (i + k) // 2
# Trace output added to code in book
print(i, j, "|", j + 1, k)
merge_sort (numbers, i, j)
merge_sort (numbers, j+1, k)
merge(numbers, i, j, k)
__name=
_____main__':
numbers = read_nums ()
print ('unsorted: ', end=' ')
print_nums (numbers)
print()
merge_sort (numbers, 0, len(numbers) - 1)
print ('\nsorted: ', end-' ')
print_nums (numbers)
Transcribed Image Text:The program is the same as shown at the end of the Merge sort section, with the following changes:
Numbers are entered by a user in a separate helper function, read_nums(), instead of defining a specific list.
Output of the list has been moved to the function print_nums().
• An output has been added to merge_sort(), showing the indices that will be passed to the recursive function calls.
Add code to the merge sort algorithm to count the number of comparisons performed.
Add code at the end of the program that outputs "comparisons: " followed by the number of comparisons performed (Ex: "comparisons:
12")
Hint: Use a global variable to count the comparisons.
Note: Take special care to look at the output of each test to better understand the merge sort algorithm.
Ex: When the input is:
3 2 1 5 9 8
the output is:
unsorted: 3 2 1 5 9 8
0
2
3 5
2 2
1 1
0 1
0 0
3 4155
3 3 4 4
sorted: 1 2 3 5 8 9
comparisons: 8
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 4 steps with 4 images
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.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education