Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
(4) 3. Suppose you have an array of ints that has the following contents: [9, 5, 14, 19, 3, 16, 12] Show what the array would be after four passes of the outer for loop for a insertion sort that is sorting the array in descending order. Show the array for each pass.

(4) 3. Suppose you have an array of ints that has the following contents: [9, 5, 14, 19, 3, 16, 12] Show what the array would be after four passes of the outer for loop for a insertion sort that is sorting the array in descending order. Show the array for each pass.

Database System Concepts
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
icon
Related questions
Question

Java Language

**Insertion Sort - Descending Order (Example)** **Problem:** Suppose you have an array of integers with the following contents: `[9, 5, 14, 19, 3, 16, 12]` Show what the array would be after **four** passes of the outer for loop for an **insertion sort** that is sorting the array in descending order. Show the array for **each** pass. **Explanation:** Insertion sort is a simple algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort or merge sort. However, it is more efficient than other more advanced algorithms when the list is mostly sorted. For sorting in descending order, the algorithm works by repeatedly taking the next element from the unsorted portion, comparing it with elements in the sorted portion, and inserting it in the correct position to form a new sorted portion. Let's apply this to the given array: **Initial Array:** `[9, 5, 14, 19, 3, 16, 12]` **Pass 1:** - Start from the second element (5) and compare with previous elements. - Since 9 > 5, no swap for descending order. Array after Pass 1: `[9, 5, 14, 19, 3, 16, 12]` **Pass 2:** - Consider element 14. - Move 5 and 9 to the right because 14 > 9 (for descending order). Array after Pass 2: `[14, 9, 5, 19, 3, 16, 12]` **Pass 3:** - Consider element 19. - Move 5, 9, and 14 to the right because 19 > 14. Array after Pass 3: `[19, 14, 9, 5, 3, 16, 12]` **Pass 4:** - Consider element 3. - Since 3 is less than 5, it stays in the same position for descending order. Array after Pass 4: `[19, 14, 9, 5, 3, 16, 12]` After four passes, the major portion of the array is ordered in descending order
Transcribed Image Text:**Insertion Sort - Descending Order (Example)** **Problem:** Suppose you have an array of integers with the following contents: `[9, 5, 14, 19, 3, 16, 12]` Show what the array would be after **four** passes of the outer for loop for an **insertion sort** that is sorting the array in descending order. Show the array for **each** pass. **Explanation:** Insertion sort is a simple algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort or merge sort. However, it is more efficient than other more advanced algorithms when the list is mostly sorted. For sorting in descending order, the algorithm works by repeatedly taking the next element from the unsorted portion, comparing it with elements in the sorted portion, and inserting it in the correct position to form a new sorted portion. Let's apply this to the given array: **Initial Array:** `[9, 5, 14, 19, 3, 16, 12]` **Pass 1:** - Start from the second element (5) and compare with previous elements. - Since 9 > 5, no swap for descending order. Array after Pass 1: `[9, 5, 14, 19, 3, 16, 12]` **Pass 2:** - Consider element 14. - Move 5 and 9 to the right because 14 > 9 (for descending order). Array after Pass 2: `[14, 9, 5, 19, 3, 16, 12]` **Pass 3:** - Consider element 19. - Move 5, 9, and 14 to the right because 19 > 14. Array after Pass 3: `[19, 14, 9, 5, 3, 16, 12]` **Pass 4:** - Consider element 3. - Since 3 is less than 5, it stays in the same position for descending order. Array after Pass 4: `[19, 14, 9, 5, 3, 16, 12]` After four passes, the major portion of the array is ordered in descending order
**Question:** Suppose you want to use **selection sort** in descending order on the following array: \[8, 18, 17, 19, 4, 11, 5\] Show what the array would be after **four** passes of the outer for loop. Show the array for **each** pass.
Transcribed Image Text:**Question:** Suppose you want to use **selection sort** in descending order on the following array: \[8, 18, 17, 19, 4, 11, 5\] Show what the array would be after **four** passes of the outer for loop. Show the array for **each** pass.
Expert Solution
steps

Step by step

Solved in 5 steps with 5 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Arrays
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
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)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS