4.9 LAB: Insertion sort The script has four steps: Read a list of integers (no duplicates). Output the numbers in the list. Perform an insertion sort on the list. Output the number of comparisons and swaps performed during the insertion sort. Steps 1 and 2 are provided in the script. Implement step 3 based on the insertion sort algorithm in the book. Modify insertion_sort() to: Count the number of comparisons performed. Count the number of swaps performed. Output the list during each iteration of the outside loop. Implement step 4 at the end of the script. Hints: In order to count comparisons and swaps, modify the while loop in insertion_sort(). Use global variables for comparisons and swaps. The script includes three helper functions: read_nums() # Read and return a list of integers. print_nums(nums) # Output the numbers in nums swap(nums, n, m) # Exchange nums[n] and nums[m] Code I have so far: def read_nums(): return [int(num) for num in input().split()] def print_nums(nums): print(' '.join([str(n) for n in nums]), end='') def swap(nums, n, m): nums[n], nums[m] = nums[m], nums[n] def insertion_sort(numbers): comparisons = 0 swaps = 0 for i in range(1, len(numbers)): comparisons += 1 j = i while j > 0 and numbers[j] < numbers[j - 1]: swap(numbers, j, j - 1) swaps += 1 j -= 1 print('comparisons:', comparisons) print('swaps:', swaps) if name == 'main': numbers = read_nums() print_nums(numbers); print(end='\n\n') insertion_sort(numbers) print() Error I am getting: Input 3 2 1 5 9 8 Your output 3 2 1 5 9 8 comparisons: 5 swaps: 4 Expected output 3 2 1 5 9 8 2 3 1 5 9 8 1 2 3 5 9 8 1 2 3 5 9 8 1 2 3 5 9 8 1 2 3 5 8 9 comparisons: 7 swaps: 4

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

14.9 LAB: Insertion sort

The script has four steps:

Read a list of integers (no duplicates).
Output the numbers in the list.
Perform an insertion sort on the list.
Output the number of comparisons and swaps performed during the insertion sort.

Steps 1 and 2 are provided in the script.

Implement step 3 based on the insertion sort algorithm in the book. Modify insertion_sort() to:

Count the number of comparisons performed.
Count the number of swaps performed.
Output the list during each iteration of the outside loop.

Implement step 4 at the end of the script.

Hints: In order to count comparisons and swaps, modify the while loop in insertion_sort(). Use global variables for comparisons and swaps.

The script includes three helper functions:

read_nums() # Read and return a list of integers.
print_nums(nums) # Output the numbers in nums
swap(nums, n, m) # Exchange nums[n] and nums[m]

Code I have so far:

def read_nums():
return [int(num) for num in input().split()]

def print_nums(nums):
print(' '.join([str(n) for n in nums]), end='')

def swap(nums, n, m):
nums[n], nums[m] = nums[m], nums[n]

def insertion_sort(numbers):
comparisons = 0
swaps = 0
for i in range(1, len(numbers)):
comparisons += 1
j = i
while j > 0 and numbers[j] < numbers[j - 1]:
swap(numbers, j, j - 1)
swaps += 1
j -= 1
print('comparisons:', comparisons)
print('swaps:', swaps)

if __name__ == '__main__':
numbers = read_nums()

print_nums(numbers);
print(end='\n\n')

insertion_sort(numbers)
print()
Error I am getting:

Input

3 2 1 5 9 8

Your output

3 2 1 5 9 8 comparisons: 5 swaps: 4

Expected output

3 2 1 5 9 8 2 3 1 5 9 8 1 2 3 5 9 8 1 2 3 5 9 8 1 2 3 5 9 8 1 2 3 5 8 9 comparisons: 7 swaps: 4

1: Compare output
Output differs. See highlights below. Special character legend
Input
Your output
output
2: Compare output
3 2 1 5 98
3 2 1 5 98
comparisons:
swaps: 4
3 2 1 5 98
2 3 1
1 2 3
1 2 3
5 9 8
1 2 3 5
1 2 3
5
5
5
9 8
9
8
9 8
8 9
5
comparisons: 7
swaps: 4
Output differs. See highlights below. Special character legend
0/2
0/2

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 1 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