mid1 prac sol
.pdf
keyboard_arrow_up
School
University of Maryland, College Park *
*We aren’t endorsed by this school
Course
351
Subject
Computer Science
Date
Dec 6, 2023
Type
Pages
4
Uploaded by DeanBaboonPerson1023 on coursehero.com
Kruskal
CMSC351: Practice Midterm 1
Fall 2023
These are practice problems for the upcoming midterm exam. You will be given a sheet of notes
for the exam.
Also, go over your homework assignments.
Warning:
This does not necessarily
reflect the length, difficulty, or coverage of the actual exam.
Problem 1. Assume that you are sorting an array of size
n
using Bubble Sort, where
n
= 2
k
−
1.
Assume that the smallest element is in the first location. The next two smallest elements are
in the next two locations in some order. The next four smallest elements are in the next four
locations in some order.
The next eight smallest elements are in the next eight locations in
some order. Etc. For example, assume
n
= 7 (and
k
= 3), the input might look like
10, 30, 20, 50, 70, 40, 60
The algorithm does not know this, and executes without this extra information.
(a) Assume that the elements within each group are in reverse order. For example, if
n
= 7
(and
k
= 3), the input will look like
10, 30, 20, 70, 60, 50, 40
What is the number of exchanges? Get the exact answer as a function of
k
, and the exact
high order term as a function of
n
. Show your work.
Solution:
Since
n
= 2
k
−
1, we know that
k
= lg(
n
+ 1).
We know from class that the worst case number of exchanges for Bubble Sort on a list
of size
m
is (
m
−
1)
m/
2. We can treat each group as an independent Bubble Sort.
This gives
k
−
1
X
i
=0
(2
i
−
1)2
i
2
=
1
2
4
k
−
1
4
−
1
−
1
2
(2
k
−
1) =
1
2
(2
k
)
2
−
1
3
−
1
2
(2
k
−
1)
=
1
2
(
n
+ 1)
2
−
1
3
−
1
2
((
n
+ 1)
−
1) =
n
(
n
−
1)
6
(b) Assume that the elements within each group are in random order. What is the average
number of exchanges? Get the exact answer as a function of
k
, and the exact high order
term as a function of
n
. Show your work.
Solution:
We know from class that the average case number of exchanges for Bubble
Sort on a list of size
m
is (
m
−
1)
m/
4. We can treat each group as an independent
Bubble Sort. This gives
k
−
1
X
i
=0
(2
i
−
1)2
i
4
=
1
4
4
k
−
1
4
−
1
−
1
4
(2
k
−
1) =
1
4
(2
k
)
2
−
1
3
−
1
4
(2
k
−
1)
=
1
4
(
n
+ 1)
2
−
1
3
−
1
4
((
n
+ 1)
−
1) =
n
(
n
−
1)
12
Kruskal
CMSC351: Practice Midterm 1
Fall 2023
Problem 2. Assume you have an array of numbers, where each value occurs
at most
twice.
We
consider sums of contiguous numbers in the array. But we only consider such sums whose two
endpoints have the same value. The sum includes the two equal values themselves. So if the
two equal numbers are at index
i
and index
j
(
i < j
) in array
A
, then we sum all the values
A
[
i
]
, A
[
i
+ 1]
, . . . , A
[
j
].
(a) Give an algorithm that finds the maximum such sum. Make your algorithm as efficient as
possible. Describe the algorithm briefly in English
and
in psuedo code.
(b) Analyze the running time of your algorithm.
Problem 3. Let
A
[1
, .., n
] be an array of
n
numbers (some positive and some negative).
(a) Give an algorithm to find which two numbers have sum closest to zero.
Make your
algorithm as efficient as possible. Write it in pseudo-code.
(b) Analyze its running time.
Problem 4. Assume the you have a heap of size
n
= 2
m
−
1 (stored in an array).
(The largest
element is at the root.)
You may describe the following algorithms in high level language, but
they
must
be clear. Give your answers as a function of
n
. You may assume
n
is large. You
may use extra memory.
(a) Give an algorithm, minimizing the number of comparisons, to find the smallest element
in the heap. Exactly how many comparisons does it take.
(b) Give an algorithm, minimizing the number of comparisons, to find the second smallest
element in the heap. Exactly how many comparisons does it take.
(c) Give an algorithm, minimizing the number of comparisons, to find the third smallest
element in the heap. Exactly how many comparisons does it take.
Problem 5. Consider the following algorithm for finding the two smallest elements in a list: Sort
the first two elements. Call them
special
. Then iterate through the remainder of the elements
one at a time. First compare each new element to the larger of the two special elements, and
if necessary compare it to the smaller. The two new special elements will be the smallest two
of those three elements.
(a) Write the pseudocode for this algorithm.
(b) What is the exact best case number of comparisons? Justify and simplify.
Solution:
n
−
1
(c) What is the exact worst case number of comparisons? Justify and simplify.
Solution:
2
n
−
3
Page 2 of 4
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Related Questions
1. You have an array of 4 ints which is sorted from lowest to highest. You also have a function which runs a bubble sort to sort items from lowest to highest. If you run this function on your array, the function will do at least one swap.
A) True
B) False
arrow_forward
Median Function – In statistics, the median of a set of values is the value that lies in the middle when the values are arranged in sorted order. If the set has an even number of values, the median is the average of the two middle values.
Your program should start with two arrays of integers containing the following values:
Even numbered array: 17 32 45 68 99 101 67 89 22 27
Odd numbered array: 17 32 45 68 99 101 67 89 22
Using a sort function of your choice, first sort the arrays. NOTE: you may use the Standard Template Library sort function or your own sort function.
Then, write a function that determines the median of a sorted array. The function should take an array of numbers and an integer indicating the size of the array and return the median of the values in the array. The same function should be called twice – once for the even array and once for the odd array.
Your program should also have a printArray function that can be used to print the sorted array. (It…
arrow_forward
1. You have an array of 4 ints which is sorted from highest to lowest. You also have a function which runs a bubble sort to sort items from lowest to highest. If you run this function on your array, the function will do multiple swaps.
A) True
B) False
arrow_forward
True or False
For each statement below, indicate whether you think it is True or False
If you have an array with no “holes”, the append function performs at O(1)
Inserting an element at the front and shifting all elements performs significantly worse than appending an element at the end of the list
For the insert function, if the array is empty, there are no comparison operations that need to be performed and you can immediately add the new element
Binary search can be used on an unsorted array to significantly improve its performance from O(n) to O(1)
arrow_forward
True or False
For each statement below, indicate whether you think it is True or False
If you have an array with no “holes”, the append function performs at O(1)
Inserting an element at the front and shifting all elements performs significantly worse than appending an element at the end of the list
For the insert function, if the array is empty, there are no comparison operations that need to be performed and you can immediately add the new element
Binary search can be used on an unsorted array to significantly improve its performance from O(n) to O(1)
Because the update algorithm depends on using linear search, its performance is O(1) in the worst case scenario
True
If you search for and delete an element in an unsorted array and then shift the rest of the elements to fill the hole, the worst case performance is O(n)
If you search for and delete an element in an unsorted array and then move the last element to fill the hole, the worst case performance is O(n)
arrow_forward
1. Sorting• Begin by filling an array with random numbers:import numpy as npnp.random.seed(1012)DATASIZE = 1000MAX_VALUE = 10000000data = np.random.randint(0, MAX_VALUE, size=DATASIZE)• Write a function that is passed a numpy array. The function should walkthrough the array element-by-element, comparing the current element tothe next element. Swap if the next is smaller than the current – sortingthese two elements.• Write a second function that calls the above function n times, where n isthe number of elements (size) of the array. Pass the same numpy arrayeach time.
2. Bubble Sort• The sort from part 1 can be improved. If the data passed to be sorted isalready sorted, it still performs all of the work, as if the array was notsorted.Make two improvements:• Change the first function (the one that does the comparisons), so that it returns aboolean that states whether the array is sorted. Make use of that boolean to stopcalling the first function if the array is sorted.• Consider…
arrow_forward
1. Sorting• Begin by filling an array with random numbers:import numpy as npnp.random.seed(1012)DATASIZE = 1000MAX_VALUE = 10000000data = np.random.randint(0, MAX_VALUE, size=DATASIZE)• Write a function that is passed a numpy array. The function should walkthrough the array element-by-element, comparing the current element tothe next element. Swap if the next is smaller than the current – sortingthese two elements.• Write a second function that calls the above function n times, where n isthe number of elements (size) of the array. Pass the same numpy arrayeach time.
arrow_forward
CST-201
Project 0: Array Warm-Up
The purpose of this assignment is to practice manipulating arrays. This assignment assesses your ability to:
▪Implement sequential and binary search algorithms for array structures.
▪Implement iterative sorting algorithms for array data.
For this assignment, write a program that reads a text file and stores each word in an array. Write one of the iterative sorting algorithms to sort your data. Once the data is sorted, write a binary sort algorithm that, when given a string, returns either the index of the string or a -1 to indicate the string was not found in the array. Your program should allow the user to continually enter strings. An entry of 0 indicates the user is finished searching for strings.
Start your program by reading strings from a file and populating a string array. Declare the array with a capacity for 10,000 strings. An input file is included with this assignment: ‘text.txt’.
Next, write a method that implements either bubble sort,…
arrow_forward
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_forward
(Bubble Sort) Implement the bubble sort—another simple, yet inefficient, sorting technique. It’s called bubble sort or sinking sort because smaller values gradually “bubble” their way to the top of the array (i.e., toward the first element) like air bubbles rising in water, while the larger values sink to the bottom (end) of the array. The technique uses nested loops to make several passes through the array. Each pass compares successive overlapping pairs of elements (i.e., elements 0 and 1, 1 and 2, 2 and 3, etc.). If a pair is in increasing order (or the values are equal), the bubble sort leaves the values as they are. If a pair is in decreasing order, the bubble sort swaps their values in the array.
The first pass compares the first two elements of the array and swaps them if necessary. It then compares the second and third elements. The end of this pass compares the last two elements in the array and swaps them if necessary. After one pass, the largest element will be in the last…
arrow_forward
Kim Gigabit purchase items of various quantities; valid quantities are greater than 0 and less than 100Read the quantity for each 10 items from the keyboard and store each into an integer array; if Kim enters a quantity of 0, negative, or greater than 100, it should be rejected, and she should be queried for a valid entry
1. After the valid entries are complete, display the unsorted array content, pass the unsorted array to another method for sorting, and display of the sorted array; you can use the code below for sorting
2. Modify the code below using the while loop
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package sortascending;
public class Sortascending {
public static void sortAsc( int[] arrayToSort )
{
// Find the integer that should go in each cell j of
// the arrayToSort, from cell 0 to the end
for…
arrow_forward
1. Implement Bubble sort, Insertion sort, Selection sort, Quick sort, Merge sort and Radix sort algorithms (use static method). 2. Assume there are 21 students in your class. Take random scores (in the range of 0 to 100) of 21 students using an Integer array named stdScore. Hint to generate a random score: Random rand = new Random(); Integer score = rand.nextInt(100); 3. To perform the descending order sorting, pass the stdScore array (random score) while invoking each of the sorting algorithm you have implemented in step 1. Count number of comparisons required for performing descending order sorting.
4. Repeat step 3 by passing the already sorted stdScore array. Count number of comparisons required for descending order sorting. 5. Fill up the following table using the results you got from Step 3 and 4
arrow_forward
İN C PROGRAMMİNG
Write a program that fills an integer array of size 1000 with random positive integers between 1 and 10. Assume that each element represents a different city and the integers stored in the array represent the number of golds in those cities. The program traverses over the array and collects the golds at each city, starting from a random position. When the program visits a certain city, all of the golds are collected, and the visited element of the array becomes 0 (no gold is left at that city.) The journey continues with the rule given below. If the position at the nth step is denoted by pn, and the number of golds at the city pn is denoted by gn,
??+1 ={|(?? +??) ???1000|, ?????2=0. |(?? − ??) ??? 1000|, ????? 2 = 1
The program continues visiting cities until the last three visited city has no gold. The program, at each visit, should print out the following information:
• The current city index (pn).
• The previous city index (pn-1).
• The number of golds at the…
arrow_forward
9.2.1: Middle item.
Given a sorted list of integers, output the middle integer. Assume the number of integers is always odd.
Ex: If the input is 2 3 4 8 11 -1 (a negative indicates end), the output is:
4
The maximum number of inputs for any test case should not exceed 9 positive values. If exceeded, output "Too many inputs".
Hint: Use an array of size 9. First read the data into an array. Then, based on the number of items, find the middle item.
Need code writing coral language
arrow_forward
1. Write a program that compares all four advanced sorting algorithms discussed in this chapter. To perform the tests, create a randomly generatedarray of 1,000 elements. What is the ranking of the algorithms? What happens when you increase the array size to 10,000 elements and then 100,000elements?
arrow_forward
C++
1- Creating an array of 8 random integers /// 2- Copying the elements from the first array to another array that fulfills the following condition: The sum of the element to twice its position is less than the square of the difference between the element that follows it and the element that precedes it except for the first and last element They are copied automatically //// 3- Finds the largest even number in the first array and in what position it is found //// 4- Finds the two smallest odd numbers in the first array and in what position it is
arrow_forward
Kim Gigabit purchase items of various quantities; valid quantities are greater than 0 and less than 100Read the quantity for each 10 items from the keyboard and store each into an integer array; if Kim enters a quantity of 0, negative, or greater than 100, it should be rejected, and she should be queried for a valid entry
After the valid entries are complete, display the unsorted array content, pass the unsorted array to another method for sorting, and display of the sorted array
arrow_forward
Select true or false for the statements below. Explain your answers if you like to receive partial credit
Select true or false for the statements below. Explain your answers if you like to receive partial credit
Which of the following is true about searching elements in an unordered array?
With the data is unsorted, search is O(n) because if the element you are looking for is not there, you have to check every element in the array
If you start at the end of the array and traverse to index 0, search improves to O(log n) because you only have to look at half of the array
If you get lucky with checking the first element and find it immediately, then the worst case performance of search improves to O(n^2)
Which of the following is true about searching elements in an ordered array?
You cannot use binary search on an ordered array so the performance is O(n)
If there are no holes in the array and the elements are all next to each other, then the performance for search improves to…
arrow_forward
Question 4: (30 marks) A Math teacher is teaching Math course to a set of classes (each class may have different number of students) and want to check the behavior of his students in a homework report. The teacher gave the classes the same exam and marked their answer and wants to know the class whose students got the highest average. Help the teacher in the required analysis of student’s marks by implementing a Java program ClassAverageMArks2DimmArray using 2-dimensional array to store the students marks and then compute the average of each class student’s marks. The program has the following specification: • A Method titled averageClassMarks for computing the average (as double) of a class students marks (given to the method as a single-dimensional array) • Another Method titled averageAllClassesMarks for computing the average (as single array of double) of all the classes class student’s marks (given to the method as a 2dimensional array). This method has to repeatedly call the…
arrow_forward
True or False
For each statement below, indicate whether you think it is True or False. If you like, you can provide a description of your answer.
5) Inserting elements into a sorted array is O(n) because you have to find the location to add the new element and then shift the remaining elements
6) If the sorted array gets too large, the performance of binary search becomes O(n)
7) For the delete algorithm, after you find the element to delete, you can make the algorithm run faster by replacing it with the last element in the array
8) If you used binary search to find the element to delete, the performance is still O(n) because you may have to shift all elements
arrow_forward
Kim Gigabit purchase items of various quantities; valid quantities are greater than 0 and less than 100Read the quantity for each 10 items from the keyboard and store each into an integer array (use loop); if Kim enters a quantity of 0, negative, or greater than 100, it should be rejected, and she should be queried for a valid entry. After the valid entries are complete, display the unsorted array content, pass the unsorted array to another method for sorting (use for loop), and display of the sorted array. Use java
arrow_forward
f an array is sorted in this order, the values are stored from highest to lowest.a. asymptoticb. logarithmicc. ascendingd. descending
arrow_forward
c++
3. In order to create an efficient spell checker, you want to know the frequency of occurences of vowels and consonants. Write a program which will prompt the user to enter a string from the keyboard. The program should then count and report the number of characters in the string. The program should also count and report the number of times each letter of the alphabet occurs in the string, and print the percentage of the total represented. Using the principles discussed in finding the maximum element of an array, find the letter of the alphabet which occurs most frequently in the sentence. Find also the letter which occurs second-most frequently.
use the following text :
The album also featured alternate versions of Beatles favoritessuch as "Love Me Do," "Please Please Me," "A Hard Day's Night,""YouCan't Do That," as well as never before heard tracks such asMcCartney's "In Spite of All The Danger," Ray Charles' "HallelujahI Love Her So" and Leiber and Stoller's "Searchin',"…
arrow_forward
Question1: define two lists of numbers (arrays) and ask the user to give the size of each, and then ask the user to fill the list(according to a size that he gave), then compare two arrays and determine whether they are equal?
Note: two arrays are equal if all elements are equal.
(Array not vector) C++
arrow_forward
True or False
For each statement below, indicate whether you think it is True or False.
If you use binary search on a sorted array, the performance at worst is O(log n)
For the insert algorithm, if you use binary search to find the location to insert the new element, it will improve the overall performance of the algorithm to O(log n)
For the update algorithm in a sorted array, all you have to do is use linear or binary search to find the element you want to change, and if you find it, you only need to change it to the new value
Binary search can be used on an unsorted array
Inserting elements into a sorted array is O(n) because you have to find the location to add the new element and then shift the remaining elements
If the sorted array gets too large, the performance of binary search becomes O(n)
For the delete algorithm, after you find the element to delete, you can make the algorithm run faster by replacing it with the last element in the array
If you used binary search to…
arrow_forward
solve 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_forward
6. the grade is under 20 which is outlier, remove it from the array list.
7. Print array list using System.out.println()
8. Use indexOf to print index of 80.
9. Use get function.
10. What is the difference between get and index of?
11. Print the values of the array list using Iterator class.
12.. Delete all the values of the array list using clear function.
13. Print all the values of the array after you execute clear using System.out.println(). what is the result of using clear function?
14. What is the shortcoming of using array List?
arrow_forward
SEE MORE QUESTIONS
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
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
Related Questions
- 1. You have an array of 4 ints which is sorted from lowest to highest. You also have a function which runs a bubble sort to sort items from lowest to highest. If you run this function on your array, the function will do at least one swap. A) True B) Falsearrow_forwardMedian Function – In statistics, the median of a set of values is the value that lies in the middle when the values are arranged in sorted order. If the set has an even number of values, the median is the average of the two middle values. Your program should start with two arrays of integers containing the following values: Even numbered array: 17 32 45 68 99 101 67 89 22 27 Odd numbered array: 17 32 45 68 99 101 67 89 22 Using a sort function of your choice, first sort the arrays. NOTE: you may use the Standard Template Library sort function or your own sort function. Then, write a function that determines the median of a sorted array. The function should take an array of numbers and an integer indicating the size of the array and return the median of the values in the array. The same function should be called twice – once for the even array and once for the odd array. Your program should also have a printArray function that can be used to print the sorted array. (It…arrow_forward1. You have an array of 4 ints which is sorted from highest to lowest. You also have a function which runs a bubble sort to sort items from lowest to highest. If you run this function on your array, the function will do multiple swaps. A) True B) Falsearrow_forward
- True or False For each statement below, indicate whether you think it is True or False If you have an array with no “holes”, the append function performs at O(1) Inserting an element at the front and shifting all elements performs significantly worse than appending an element at the end of the list For the insert function, if the array is empty, there are no comparison operations that need to be performed and you can immediately add the new element Binary search can be used on an unsorted array to significantly improve its performance from O(n) to O(1)arrow_forwardTrue or False For each statement below, indicate whether you think it is True or False If you have an array with no “holes”, the append function performs at O(1) Inserting an element at the front and shifting all elements performs significantly worse than appending an element at the end of the list For the insert function, if the array is empty, there are no comparison operations that need to be performed and you can immediately add the new element Binary search can be used on an unsorted array to significantly improve its performance from O(n) to O(1) Because the update algorithm depends on using linear search, its performance is O(1) in the worst case scenario True If you search for and delete an element in an unsorted array and then shift the rest of the elements to fill the hole, the worst case performance is O(n) If you search for and delete an element in an unsorted array and then move the last element to fill the hole, the worst case performance is O(n)arrow_forward1. Sorting• Begin by filling an array with random numbers:import numpy as npnp.random.seed(1012)DATASIZE = 1000MAX_VALUE = 10000000data = np.random.randint(0, MAX_VALUE, size=DATASIZE)• Write a function that is passed a numpy array. The function should walkthrough the array element-by-element, comparing the current element tothe next element. Swap if the next is smaller than the current – sortingthese two elements.• Write a second function that calls the above function n times, where n isthe number of elements (size) of the array. Pass the same numpy arrayeach time. 2. Bubble Sort• The sort from part 1 can be improved. If the data passed to be sorted isalready sorted, it still performs all of the work, as if the array was notsorted.Make two improvements:• Change the first function (the one that does the comparisons), so that it returns aboolean that states whether the array is sorted. Make use of that boolean to stopcalling the first function if the array is sorted.• Consider…arrow_forward
- 1. Sorting• Begin by filling an array with random numbers:import numpy as npnp.random.seed(1012)DATASIZE = 1000MAX_VALUE = 10000000data = np.random.randint(0, MAX_VALUE, size=DATASIZE)• Write a function that is passed a numpy array. The function should walkthrough the array element-by-element, comparing the current element tothe next element. Swap if the next is smaller than the current – sortingthese two elements.• Write a second function that calls the above function n times, where n isthe number of elements (size) of the array. Pass the same numpy arrayeach time.arrow_forwardCST-201 Project 0: Array Warm-Up The purpose of this assignment is to practice manipulating arrays. This assignment assesses your ability to: ▪Implement sequential and binary search algorithms for array structures. ▪Implement iterative sorting algorithms for array data. For this assignment, write a program that reads a text file and stores each word in an array. Write one of the iterative sorting algorithms to sort your data. Once the data is sorted, write a binary sort algorithm that, when given a string, returns either the index of the string or a -1 to indicate the string was not found in the array. Your program should allow the user to continually enter strings. An entry of 0 indicates the user is finished searching for strings. Start your program by reading strings from a file and populating a string array. Declare the array with a capacity for 10,000 strings. An input file is included with this assignment: ‘text.txt’. Next, write a method that implements either bubble sort,…arrow_forward3. 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_forward
- (Bubble Sort) Implement the bubble sort—another simple, yet inefficient, sorting technique. It’s called bubble sort or sinking sort because smaller values gradually “bubble” their way to the top of the array (i.e., toward the first element) like air bubbles rising in water, while the larger values sink to the bottom (end) of the array. The technique uses nested loops to make several passes through the array. Each pass compares successive overlapping pairs of elements (i.e., elements 0 and 1, 1 and 2, 2 and 3, etc.). If a pair is in increasing order (or the values are equal), the bubble sort leaves the values as they are. If a pair is in decreasing order, the bubble sort swaps their values in the array. The first pass compares the first two elements of the array and swaps them if necessary. It then compares the second and third elements. The end of this pass compares the last two elements in the array and swaps them if necessary. After one pass, the largest element will be in the last…arrow_forwardKim Gigabit purchase items of various quantities; valid quantities are greater than 0 and less than 100Read the quantity for each 10 items from the keyboard and store each into an integer array; if Kim enters a quantity of 0, negative, or greater than 100, it should be rejected, and she should be queried for a valid entry 1. After the valid entries are complete, display the unsorted array content, pass the unsorted array to another method for sorting, and display of the sorted array; you can use the code below for sorting 2. Modify the code below using the while loop /* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package sortascending; public class Sortascending { public static void sortAsc( int[] arrayToSort ) { // Find the integer that should go in each cell j of // the arrayToSort, from cell 0 to the end for…arrow_forward1. Implement Bubble sort, Insertion sort, Selection sort, Quick sort, Merge sort and Radix sort algorithms (use static method). 2. Assume there are 21 students in your class. Take random scores (in the range of 0 to 100) of 21 students using an Integer array named stdScore. Hint to generate a random score: Random rand = new Random(); Integer score = rand.nextInt(100); 3. To perform the descending order sorting, pass the stdScore array (random score) while invoking each of the sorting algorithm you have implemented in step 1. Count number of comparisons required for performing descending order sorting. 4. Repeat step 3 by passing the already sorted stdScore array. Count number of comparisons required for descending order sorting. 5. Fill up the following table using the results you got from Step 3 and 4arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_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