def insertion_sort(a): n = len(a) i=1 while i= 0 and a[j] >x: a[j+1] = a[i] j=j-1 a[j+1] = x i=i+1 One way to recognize that this is an imperative function is that it does not even return anything. We call it only for its side effect of moving the elements in a around so they are arranged in sorted order. Question 1: Towards Functional Programming In this question, you are asked to implement Insertion Sort as a pure function. To qualify as a pure function, your insertion_sort function has to satisfy the following conditions: It does not modify the input array a as the above implementation does. Instead, it should return a new array containing the sorted elements. It may create and initialize variables but not modify them. In the above insertion_sort implementation, the assignments n = len(a), i = 1, x = a[i+1], and j = i are all fine because they create new variables and specify their values. The assignments j =j +1, a[i+1] = a[j], alj + 1] = x, and i=i+1 are not because they overwrite i, j or an element of the array a. If you are tempted to write a for-loop for x in a: this is also inherently imperative because it assigns a new value to x in each iteration. So loops are simply not possible. You should implement insertion_sort as a recursive function. It is okay (and necessary) to implement a helper function that insertion_sort can use to implement the process of inserting x in the right position among the already sorted elements. This helper function needs to satisfy the same conditions: no modification of the function arguments or local variables.
def insertion_sort(a): n = len(a) i=1 while i= 0 and a[j] >x: a[j+1] = a[i] j=j-1 a[j+1] = x i=i+1 One way to recognize that this is an imperative function is that it does not even return anything. We call it only for its side effect of moving the elements in a around so they are arranged in sorted order. Question 1: Towards Functional Programming In this question, you are asked to implement Insertion Sort as a pure function. To qualify as a pure function, your insertion_sort function has to satisfy the following conditions: It does not modify the input array a as the above implementation does. Instead, it should return a new array containing the sorted elements. It may create and initialize variables but not modify them. In the above insertion_sort implementation, the assignments n = len(a), i = 1, x = a[i+1], and j = i are all fine because they create new variables and specify their values. The assignments j =j +1, a[i+1] = a[j], alj + 1] = x, and i=i+1 are not because they overwrite i, j or an element of the array a. If you are tempted to write a for-loop for x in a: this is also inherently imperative because it assigns a new value to x in each iteration. So loops are simply not possible. You should implement insertion_sort as a recursive function. It is okay (and necessary) to implement a helper function that insertion_sort can use to implement the process of inserting x in the right position among the already sorted elements. This helper function needs to satisfy the same conditions: no modification of the function arguments or local variables.
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
Please solve this problem in C++/ C language. Send me answer within 10 min!! I will rate you good for sure!! Read the question carefully!!
![insertion_sort(a):
n = len(a)
i=1
while i<n:
x = a[i]
j=i-1
while j >= 0 and a[i] > x:
def
a[j+1] = a[j]
j=j-1
aj + 1] = x
i=i+1
One way to recognize that this is an imperative function is that it does not even return anything. We call it only for its side
effect of moving the elements in a around so they are arranged in sorted order.
Question 1: Towards Functional Programming
In this question, you are asked to implement Insertion Sort as a pure function. To qualify as a pure function, your
insertion_sort function has to satisfy the following conditions:
It does not modify the input array a as the above implementation does. Instead, it should return a new array containing the
sorted elements.
444
It may create and initialize variables but not modify them. In the above insertion_sort implementation, the assignments n =
len(a), i = 1, x = a[i+1], and j = i are all fine because they create new variables and specify their values. The assignments j =j
+1, a[j+1] = a[j], alj + 1] = x, and i=i+1 are not because they overwrite i, j or an element of the array a. If you are tempted
to write a for-loop
for x in a:
this is also inherently imperative because it assigns a new value to x in each iteration. So loops are simply not possible.
You should implement insertion_sort as a recursive function. It is okay (and necessary) to implement a helper function that
insertion_sort can use to implement the process of inserting x in the right position among the already sorted elements. This
helper function needs to satisfy the same conditions: no modification of the function arguments or local variables.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Feb8c0a31-07e2-4f77-9347-b13ce2efb783%2F4f53026d-21c0-468f-93b6-79fa4e9f894b%2Fy8r2ga_processed.jpeg&w=3840&q=75)
Transcribed Image Text:insertion_sort(a):
n = len(a)
i=1
while i<n:
x = a[i]
j=i-1
while j >= 0 and a[i] > x:
def
a[j+1] = a[j]
j=j-1
aj + 1] = x
i=i+1
One way to recognize that this is an imperative function is that it does not even return anything. We call it only for its side
effect of moving the elements in a around so they are arranged in sorted order.
Question 1: Towards Functional Programming
In this question, you are asked to implement Insertion Sort as a pure function. To qualify as a pure function, your
insertion_sort function has to satisfy the following conditions:
It does not modify the input array a as the above implementation does. Instead, it should return a new array containing the
sorted elements.
444
It may create and initialize variables but not modify them. In the above insertion_sort implementation, the assignments n =
len(a), i = 1, x = a[i+1], and j = i are all fine because they create new variables and specify their values. The assignments j =j
+1, a[j+1] = a[j], alj + 1] = x, and i=i+1 are not because they overwrite i, j or an element of the array a. If you are tempted
to write a for-loop
for x in a:
this is also inherently imperative because it assigns a new value to x in each iteration. So loops are simply not possible.
You should implement insertion_sort as a recursive function. It is okay (and necessary) to implement a helper function that
insertion_sort can use to implement the process of inserting x in the right position among the already sorted elements. This
helper function needs to satisfy the same conditions: no modification of the function arguments or local variables.
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 3 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