UH ID: Consider the in-place sorting algorithm MySort. Algorithm MySort 1: function MYSORT(arr) Input An array arr of n elements. Output > None for i+1 to n- 1 do j+i-1 2: 3: while j 20 and arr[j] > arr[j+ 1] do 4: temp + arrlj) arrlj] + arrlj + 1] + 1] + temp j+j-1 5: 6: 7: 8: (1) Consider your 7-digit UH ID. How many comparisons (among array elements) does MySort perform to sort the digits in your UH ID? Justify your answer. (ii) If the input array has n elements, how many comparisons does the algorithm perform in the worst case? What is the input that achieves this worst case? Justify your answer. (iii) If the input array has n elements, how many comparisons does the algorithm perform in the best case? What is the input that achieves this best case? Justify your answer. (iv) A stable sorting algorithm is one in which elements with the same value remain in the same relative order after the sort is complete. For example, if A = [2,5, 4, 5, 1). a stable sort would output [1, 2, 4, 5, 5]. Notice that the red 5 and the blue 5 occur in the same relative order before and after the array is sorted. Is MySort a stable sorting algorithm? Justify your answer. (v) Prove the correctness of MySort using mathematical induction.
UH ID: Consider the in-place sorting algorithm MySort. Algorithm MySort 1: function MYSORT(arr) Input An array arr of n elements. Output > None for i+1 to n- 1 do j+i-1 2: 3: while j 20 and arr[j] > arr[j+ 1] do 4: temp + arrlj) arrlj] + arrlj + 1] + 1] + temp j+j-1 5: 6: 7: 8: (1) Consider your 7-digit UH ID. How many comparisons (among array elements) does MySort perform to sort the digits in your UH ID? Justify your answer. (ii) If the input array has n elements, how many comparisons does the algorithm perform in the worst case? What is the input that achieves this worst case? Justify your answer. (iii) If the input array has n elements, how many comparisons does the algorithm perform in the best case? What is the input that achieves this best case? Justify your answer. (iv) A stable sorting algorithm is one in which elements with the same value remain in the same relative order after the sort is complete. For example, if A = [2,5, 4, 5, 1). a stable sort would output [1, 2, 4, 5, 5]. Notice that the red 5 and the blue 5 occur in the same relative order before and after the array is sorted. Is MySort a stable sorting algorithm? Justify your answer. (v) Prove the correctness of MySort using mathematical induction.
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
assuming ID is 1542553
![UH ID:
Consider the in-place sorting algorithm MySort.
Algorithm MySort
1: function MYSORT(arr)
Input An array arr of n elements.
Output > None
for i +1 to n- 1 do
2:
j+i-1
while j 2 0 and arr[j] > arr[j+ 1] do
temp + arr[j]
arrlj] + arrlj + 1]
arr[j + 1] + temp
j+j-1
3:
4:
5:
6:
7:
8:
(i) Consider your 7-digit UH ID. How many comparisons (among array elements) does
MySort perform to sort the digits in your UH ID? Justify your answer.
(ii) If the input array has n elements, how many comparisons does the algorithm perform
in the worst case? What is the input that achieves this worst case? Justify your
answer.
(iii) If the input array has n clements, how many comparisons does the algorithm perform
in the best case? What is the input that achieves this best case? Justify your
answer.
(iv) A stable sorting algorithm is one in which elements with the same value remain in
the same relative order after the sort is complete. For example, if A = [2,5, 4, 5, 1].
a stable sort would output [1, 2, 4, 5, 5). Notice that the red 5 and the blue 5 occur
in the same relative order before and after the array is sorted.
Is MySort a stable sorting algorithm? Justify your answer.
(v) Prove the correctness of MySort using mathematical induction.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F646a794d-e587-473e-a1b8-2a8879d17700%2F42751cc0-82fb-437e-aebe-cab52940ca66%2Fw961vfb_processed.png&w=3840&q=75)
Transcribed Image Text:UH ID:
Consider the in-place sorting algorithm MySort.
Algorithm MySort
1: function MYSORT(arr)
Input An array arr of n elements.
Output > None
for i +1 to n- 1 do
2:
j+i-1
while j 2 0 and arr[j] > arr[j+ 1] do
temp + arr[j]
arrlj] + arrlj + 1]
arr[j + 1] + temp
j+j-1
3:
4:
5:
6:
7:
8:
(i) Consider your 7-digit UH ID. How many comparisons (among array elements) does
MySort perform to sort the digits in your UH ID? Justify your answer.
(ii) If the input array has n elements, how many comparisons does the algorithm perform
in the worst case? What is the input that achieves this worst case? Justify your
answer.
(iii) If the input array has n clements, how many comparisons does the algorithm perform
in the best case? What is the input that achieves this best case? Justify your
answer.
(iv) A stable sorting algorithm is one in which elements with the same value remain in
the same relative order after the sort is complete. For example, if A = [2,5, 4, 5, 1].
a stable sort would output [1, 2, 4, 5, 5). Notice that the red 5 and the blue 5 occur
in the same relative order before and after the array is sorted.
Is MySort a stable sorting algorithm? Justify your answer.
(v) Prove the correctness of MySort using mathematical induction.
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 2 steps
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