SwapSort1 on array A = [7,6, 5, 4, 3 f the above two algorithms is correc the worst-case number of comparis and is sorted in reverse order?
SwapSort1 on array A = [7,6, 5, 4, 3 f the above two algorithms is correc the worst-case number of comparis and is sorted in reverse order?
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
![(b) Consider the two sorting algorithms below, which each take as input array A] indexed from s to
f.
SwapSort2(A, s, f)
SwapSort1(A, s, f)
swapped = true
while (swapped)
swapped = false
for i = s to f-2
swapped = true
while (swapped)
swapped = false
for i = s to f-2
if A[i] > A[i+2]
Swap A[i] and A[i+2]
swapped = true
if A[i] > Ali+2]
Swap A[i] and A[i+2]
swapped = true
swapped = true
while (swapped)
swapped = false
for i = s to f-1
if A[i] > A[i+1]
Swap A[i] and A[i+1]
swapped = true
• Execute SwapSort1 on array A = [7,6, 5, 4, 3, 2, 1] indexed from s = 1 to f = 7.
• Which of the above two algorithms is correct?. Justify your answer.
• What is the worst-case number of comparisons are made by SwapSort2 when the input array A has
length n and is sorted in reverse order?
• Does your result from above represent the worst-case number of comparisons made by SwapSort2?
Justify your answer.
• Justify that the worst-case runtime of SwapSort2 is of the form T(n)
a, b, c.
= an? + bn +c for constants](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F0ac78e14-45fa-42b2-86c0-47e5eaac311c%2Fea189dc9-c3c7-448c-ae7c-9ab551276e3f%2Fv3i6nlo_processed.jpeg&w=3840&q=75)
Transcribed Image Text:(b) Consider the two sorting algorithms below, which each take as input array A] indexed from s to
f.
SwapSort2(A, s, f)
SwapSort1(A, s, f)
swapped = true
while (swapped)
swapped = false
for i = s to f-2
swapped = true
while (swapped)
swapped = false
for i = s to f-2
if A[i] > A[i+2]
Swap A[i] and A[i+2]
swapped = true
if A[i] > Ali+2]
Swap A[i] and A[i+2]
swapped = true
swapped = true
while (swapped)
swapped = false
for i = s to f-1
if A[i] > A[i+1]
Swap A[i] and A[i+1]
swapped = true
• Execute SwapSort1 on array A = [7,6, 5, 4, 3, 2, 1] indexed from s = 1 to f = 7.
• Which of the above two algorithms is correct?. Justify your answer.
• What is the worst-case number of comparisons are made by SwapSort2 when the input array A has
length n and is sorted in reverse order?
• Does your result from above represent the worst-case number of comparisons made by SwapSort2?
Justify your answer.
• Justify that the worst-case runtime of SwapSort2 is of the form T(n)
a, b, c.
= an? + bn +c for constants
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 6 steps with 6 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