Problem Solving with C++ (10th Edition)
10th Edition
ISBN: 9780134448282
Author: Walter Savitch, Kenrick Mock
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Question
Chapter 7, Problem 6PP
Program Plan Intro
Program Plan:
- Include the appropriate headers into program.
- Declare the appropriate functions.
- Define the “main()” function,
- Declare and define the variable “array[]” in type of integer.
- Call the “printArray()” function to print the array values before sorting.
- Call the “selectionSort()” function to sort the array values.
- Print the resultant array values.
- Define the “selectionSort()” with two arguments. One is to get array values and another one is size of the array.
- Declare the variables “i”, “j”, and “t” in type of integer.
- Using “for” loops, check the array values.
- Swap the array values in appropriate position.
- Define the “printArray()” with two arguments. One is to get array values and another one is size of the array.
- Print the array values using “for” loop.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solutionStudents have asked these similar questions
IN C PROGRAMMING LANGUAGE AND COMMENT EVERY LINE PLEASE SO I CAN UNDERSTAND EVERY STEP , The selection sort is one of several techniques for sorting an array. A selection sort compares every element of an array with all the other elements of the array and exchanges their values if they are out of order. After the first pass of a selection sort, the first array element is in the correct position; after the second pass the first two elements of the array are in the correct position, and so on. Thus, after each pass of a selection sort, the unsorted portion of the array contains one less element. Write and test a function that implements this sorting method.
Exercise 1:In this problem, we would like to implement a variation of the Bubble Sort algorithm. The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list. The algorithm is illustrated as in the following figure:
For the first step, we perform bubble sort from the index 1 to n (n is thenumber of elements in the array).
The next step, we perform a reserved bubble sort from the index n to 1.
The process is repeated until all the array is sorted.
Propose a pseudo-code to complete the Bubble Sort algorithm. Implement and test this algorithm in C/C++. Analyze and compute the complexity of this algorithm in the best, average and worst scenarios.Exercise 2:Re-implement Exercise 1 using a linear data structure: List, Stack, Queue. Justify your choice of data structure.
The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sort respectively are,
a) 5 and 4
b) 4 and 5
c) 2 and 4
d) 2 and 5
Chapter 7 Solutions
Problem Solving with C++ (10th Edition)
Ch. 7.1 - Prob. 1STECh. 7.1 - In the array declaration double score(5); state...Ch. 7.1 - Identity any errors in the following array...Ch. 7.1 - What is the output of the following code? char...Ch. 7.1 - What is the output of the following code? double a...Ch. 7.1 - What is the output of the following code? int i,...Ch. 7.1 - Prob. 7STECh. 7.1 - Suppose we expect the elements of the array a to...Ch. 7.1 - Prob. 9STECh. 7.1 - Suppose you have the following array declaration...
Ch. 7.2 - Consider the following function definition: void...Ch. 7.2 - Prob. 12STECh. 7.2 - Write a function definition for a function called...Ch. 7.2 - Consider the following function definition: void...Ch. 7.2 - Insert const before any of the following array...Ch. 7.2 - Write a function named outOfOrder that takes as...Ch. 7.3 - Write a program that will read up to ten...Ch. 7.3 - Write a program that will read up to ten letters...Ch. 7.3 - Following is the declaration for an alternative...Ch. 7.4 - Prob. 20STECh. 7.4 - Write code that will fill the array a (declared...Ch. 7.4 - Prob. 22STECh. 7 - Write a function named firstLast2 that takes as...Ch. 7 - Write a function named countNum2s that takes as...Ch. 7 - Write a function named swapFrontBack that takes as...Ch. 7 - The following code creates a small phone book. An...Ch. 7 - There are three versions of this project. Version...Ch. 7 - Hexadecimal numerals are integers written in base...Ch. 7 - Solution to Programming Project 7.3 Write a...Ch. 7 - Prob. 4PPCh. 7 - Write a program that reads in a list of integers...Ch. 7 - Prob. 6PPCh. 7 - An array can be used to store large integers one...Ch. 7 - Write a program that will read a line of text and...Ch. 7 - Write a program to score five-card poker hands...Ch. 7 - Write a program that will allow two users to play...Ch. 7 - Write a program to assign passengers seats in an...Ch. 7 - Prob. 12PPCh. 7 - The mathematician John Horton Conway invented the...Ch. 7 - Redo (or do for the first time) Programming...Ch. 7 - Redo (or do for the first time) Programming...Ch. 7 - A common memory matching game played by young...Ch. 7 - Your swim school has two swimming instructors,...Ch. 7 - Your swim school has two swimming instructors,...Ch. 7 - Prob. 19PPCh. 7 - The Social Security Administration maintains an...
Knowledge Booster
Similar questions
- Multiply left and right array sum. Basic Accuracy: 54.29% Submissions: 12630 Points: 1 Pitsy needs help in the given task by her teacher. The task is to divide a array into two sub array (left and right) containing n/2 elements each and do the sum of the subarrays and then multiply both the subarrays. Example 1: â€arrow_forwardQuicksort SPLIT (the 2-pointer algorithm covered in class) is applied to the integer array [4,3,5,7,9,2,1], using the first entry as the pivot. Show the series of item swaps that are performed in the split process, and the array after each of these swaps, up to and including the step of placing the pivot at its correct location. You only need to show the split of the original array, you are not required to continue working on the subarrays after the split.arrow_forwardLangauge is python 3arrow_forwardSelection sort is a sorting algorithm, like Bubble sort which you saw in the previous module. Selection sort works as follows: Selection sort divides the input list into two parts: a sublist of sorted items (left part) and a sublist of still unsorted items (right part). Initially, the sorted sublist is empty and the whole input consists of the unsorted sublist. To fill the sorted sublist, the algorithm computes the (index of) the minimum of the unsorted sublist and swaps the first unsorted element and the minimum element (if the minimum is already the first element, nothing happens). Afterward, the sorted sublist is one bigger. This continues until the unsorted sublist is empty and the entire input is sorted. Example: Sorted sublist Unsorted sublist Least element in unsorted list (11, 25, 12, 22, 64) 11 |(11) (25, 12, 22, 64) 12 |(11, 12) (25, 22, 64) 22 |(11, 12, 22) (25, 64) 25 |(11, 12, 22, 25) (64) 64 (11, 12, 22, 25, 64) Implement this algorithm. Implement a function called…arrow_forwardslecetion sort (python) Selection sort is a sorting algorithm, like Bubble sort which you saw in the previous module. Selection sort works as follows: Selection sort divides the input list into two parts: a sublist of sorted items (left part) and a sublist of still unsorted items (right part). Initially, the sorted sublist is empty and the whole input consists of the unsorted sublist. To fill the sorted sublist, the algorithm computes the (index of) the minimum of the unsorted sublist and swaps the first unsorted element and the minimum element (if the minimum is already the first element, nothing happens). Afterward, the sorted sublist is one bigger. This continues until the unsorted sublist is empty and the entire input is sorted. Example: Sorted sublist Unsorted sublist Least element in unsorted list () (11, 25, 12, 22, 64) 11 (11) (25, 12, 22, 64) 12 (11, 12) (25, 22, 64) 22 (11, 12, 22) (25, 64) 25 (11, 12, 22, 25) (64) 64 (11, 12, 22, 25, 64) () Implement this…arrow_forwardLanguage: Python 3 Autocomplete Ready O 1 v import ast 3. Hybrid Sort input() lst %3D 3 lst = ast.literal_eval(lst) 4 Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. In each iteration, insertion sort inserts an element into an already sorted list (on left). The position where the item will be inserted is found through linear search. You decided to improve insertion sort by using binary search to find the position p where the new insertion should take place. 6 print(BinaryInsertionSort(lst)) Algorithm BinarylnsertionSort Input/output: takes an integer array a = {a[0], ..., a[n – 1]} of size n begin BinarylnsertionSort for i =1 to n val = a[i] p = BinarySearch(a, val, 0, i – 1) for j = i-1 to p a[j + 1]= a[i] j= j-1 end for a[p] = val i i+1 end for end BinarylnsertionSort Here, val = a[i] is the current value to be inserted at each step i into the already sorted part a[0], ..., ați – 1] of the array a. The binary search along that part…arrow_forwardSuppose an array has n elements. This _____ sorts to sort and array works as follows: Find the smallest element and place it in the first position. Then find the smallest of the remaining n-1 elements and place it in the second position. Repeat on n-2 elements, n-3 elements, ..., until the array is sorted.arrow_forwardDeletion operation is .…..............with arrays. TFFFFHEarrow_forwardWhat is the time complexity for the following code/program? 1.5 A binary search works like this: in a sorted array, the search algorithm compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. What is the complexity of binary search? Why?arrow_forwardsolve in python coding 3. Selection Sort• The idea in a selection sort is that you locate the largest item out of a set ofunsorted items, and move it into position at the end of the unsorted items. Asorted region grows one item at a time, while an unsorted region shrinks.• As done in Part 1, fill an array with random numbers.• Write a function that locates the largest element in the portion of the arraybeginning at the start of the array, up to a given index, and swaps the largestitem with the item at the given index.• E.g. If searching a[0] to a[7] locates the largest item at a[4], a[4] and a[7] would beswapped.• Write a second function that calls the first function repeatedly, until the entirearray is sorted. (Each time the first function is called, it will search one fewerelement)arrow_forwardBubble sort is used to arrange an array in an ascending or descending order. If we are using this algorithm to sort an array in descending order, then what will be the order of values after complete execution of outer loop 3 times: 9, 1, 4, 5, 2, 8, 6, 11, 7, 0 *arrow_forwardDESIGN YOUR OWN SETTING Task: Devise your own setting for storing and searching the data in an array of non-negative integers redundantly. You may just describe the setting without having to give an explicit algorithm to explain the process by which data is stored. You should explain how hardware failures can be detected in your method. Once you have described the setting, complete the following: Write a pseudocode function to describe an algorithm where the stored data can be searched for a value key: if the data is found, its location in the original array should be returned; -1 should be returned if the data is not found; -2 should be returned if there is a data storage error Include a short commentary explaining why your pseudocode works Describe the worst-case and best-case inputs to your search algorithm Derive the worst-case and best-case running times for the search algorithm Derive the Theta notation for the worst-case and best-case running times Maximum word count…arrow_forwardarrow_back_iosSEE MORE QUESTIONSarrow_forward_ios
Recommended textbooks for you
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
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