#### Part 1 Write a Python function (`insertion_sort`) that implements the insertion sort algorithm, discussed in the lectures. This function will take exactly one list argument, and will return a list. The argument (`values`) is a list of integers to be sorted. You will return a new list which has been sorted in ascending order. Below, you will find some code to test your insertion sort: ```python unsorted = [4,3,7,1,8,2] sorted = insertion_sort(unsorted) print(sorted) ``` #### Part 2 Modify your `insertion_sort` function to count the number of comparisons (==, <, <=, >, or >=). The function will now return both the number of comparisons made and the sorted list (in that order). _**Note:** For simplicity, since counting these comparisons won't improve the accuracy of your count very much, we'll ignore the comparisons made in the final iteration of the loop. One or both of these comparisons may actually be made, so determining the exact number of comparisons would be more challenging. Thus, you can just count the comparisons made within the body of the loop._ The code below calls your function, and creates a simple ASCII bar chart of the number of comparisons (divided by 10, to account for small differences): ```python max_elements = 30 for length in range(1, max_elements): unsorted = list(range(length, 0, -1)) sorted, num_comparisons = insertion_sort(unsorted) print(f'{num_comparisons:03d}', '*' * (num_comparisons // 10)) ``` The output of the test code has been provided, below: ``` 000 002 006 012 * 020 ** 030 *** 042 **** 056 ***** 072 ******* 090 ********* 110 *********** 132 ************* 156 *************** 182 ****************** 210 ********************* 240 ************************ 272 *************************** 306 ****************************** 342 ********************************** 380 ************************************** 420 ****************************************** 462 ********************************************** 506 ************************************************** 552 ******************************************************* 600 ************************************************************ 650 ***************************************************************** 702 ********************************************************************** 756 *************************************************************************** 812 ********************************************************************************* ```

#### Part 1 Write a Python function (`insertion_sort`) that implements the insertion sort algorithm, discussed in the lectures. This function will take exactly one list argument, and will return a list. The argument (`values`) is a list of integers to be sorted. You will return a new list which has been sorted in ascending order. Below, you will find some code to test your insertion sort: ```python unsorted = [4,3,7,1,8,2] sorted = insertion_sort(unsorted) print(sorted) ``` #### Part 2 Modify your `insertion_sort` function to count the number of comparisons (==, <, <=, >, or >=). The function will now return both the number of comparisons made and the sorted list (in that order). _Note: For simplicity, since counting these comparisons won't improve the accuracy of your count very much, we'll ignore the comparisons made in the final iteration of the loop. One or both of these comparisons may actually be made, so determining the exact number of comparisons would be more challenging. Thus, you can just count the comparisons made within the body of the loop._ The code below calls your function, and creates a simple ASCII bar chart of the number of comparisons (divided by 10, to account for small differences): ```python max_elements = 30 for length in range(1, max_elements): unsorted = list(range(length, 0, -1)) sorted, num_comparisons = insertion_sort(unsorted) print(f'{num_comparisons:03d}', '' (num_comparisons // 10)) ``` The output of the test code has been provided, below: ``` 000 002 006 012 * 020 030 * 042 ** 056 * 072 * 090 * 110 * 132 * 156 * 182 210 * 240 272 * 306 342 380 420 462 506 552 * 600 650 * 702 756 * 812 ******************************************* ```

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

Question

#### Part 1

Write a Python function (`insertion_sort`) that implements the insertion sort algorithm, discussed in the lectures.

This function will take exactly one list argument, and will return a list. The argument (`values`) is a list of integers to be sorted. You will return a new list which has been sorted in ascending order.

Below, you will find some code to test your insertion sort:

```python

unsorted = [4,3,7,1,8,2]

sorted = insertion_sort(unsorted)

print(sorted)

```

#### Part 2

Modify your `insertion_sort` function to count the number of comparisons (==, <, <=, >, or >=). The function will now return both the number of comparisons made and the sorted list (in that order).

_**Note:** For simplicity, since counting these comparisons won't improve the accuracy of your count very much, we'll ignore the comparisons made in the final iteration of the loop. One or both of these comparisons may actually be made, so determining the exact number of comparisons would be more challenging. Thus, you can just count the comparisons made within the body of the loop._

The code below calls your function, and creates a simple ASCII bar chart of the number of comparisons (divided by 10, to account for small differences):

```python

max_elements = 30

for length in range(1, max_elements):

unsorted = list(range(length, 0, -1))

sorted, num_comparisons = insertion_sort(unsorted)

print(f'{num_comparisons:03d}', '*' * (num_comparisons // 10))

```

The output of the test code has been provided, below:

```

000

002

006

012 *

020 **

030 ***

042 ****

056 *****

072 *******

090 *********

110 ***********

132 *************

156 ***************

182 ******************

210 *********************

240 ************************

272 ***************************

306 ******************************

342 **********************************

380 **************************************

420 ******************************************

462 **********************************************

506 **************************************************

552 *******************************************************

600 ************************************************************

650 *****************************************************************

702 **********************************************************************

756 ***************************************************************************

812 *********************************************************************************

```

Expert Solution

Step by step

Solved in 3 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.