Question 1 Note: Assume that all the following sorting algorithms sort in increasing order. 1.Consider the following elements 6,1,8,3,2,0. The order of the elements after 3 element swaps of the Insertion-sort algorithm is: O 1, 3, 6, 2, 8, 0 O 1, 6, 3, 8, 2, 0 O None O 1, 3, 2, 6, 8, 0 O 1, 3, 6, 8, 2, 0 QUESTION 2 2.Consider the following elements 6,1,8,3,2,0 . The order of the elements after 4 element swaps of the Selection-sort algorithm is (swapping an element with itself is also counted): O 0, 1, 2, 3, 8, 6 O 0, 1, 8, 3, 2, 6 O 0, 1, 2, 3, 6, 8 O 0, 1, 6, 3, 8, 2 O None QUESTION 3 3. Consider the following elements 6,1,8,3,2,0. The order of the elements after 6 element swaps of the Bubble-sort algorithm is: O 1, 6, 3, 2, 0, 8 O None O 1, 3, 2, 0, 6, 8 O 1, 3, 2, 6, 0, 8 O 1, 3, 6, 2, 0, 8

Question 1 Note: Assume that all the following sorting algorithms sort in increasing order. 1.Consider the following elements 6,1,8,3,2,0. The order of the elements after 3 element swaps of the Insertion-sort algorithm is: O 1, 3, 6, 2, 8, 0 O 1, 6, 3, 8, 2, 0 O None O 1, 3, 2, 6, 8, 0 O 1, 3, 6, 8, 2, 0 QUESTION 2 2.Consider the following elements 6,1,8,3,2,0 . The order of the elements after 4 element swaps of the Selection-sort algorithm is (swapping an element with itself is also counted): O 0, 1, 2, 3, 8, 6 O 0, 1, 8, 3, 2, 6 O 0, 1, 2, 3, 6, 8 O 0, 1, 6, 3, 8, 2 O None QUESTION 3 3. Consider the following elements 6,1,8,3,2,0. The order of the elements after 6 element swaps of the Bubble-sort algorithm is: O 1, 6, 3, 2, 0, 8 O None O 1, 3, 2, 0, 6, 8 O 1, 3, 2, 6, 0, 8 O 1, 3, 6, 2, 0, 8

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

Similar questions

Algorithms Assignment Quicksort is a divide and conquer algorithm that re-order the elements over the same input array (to be distinguished from the quicksort version that implements out-place re-ordering). There are two basic operations in the algorithm, swapping items in place and partitioning a section of the array. In light of this, write a report about the quicksort algorithm, which includes the following: • Discuss sorting as a problem and the algorithms used for sorting (briefly discuss merge-sort, insertion sort, etc.). • Discuss and explain the quicksort algorithm (Step, Pseudo-code). • Implement the algorithm using Java/Python and add comments to the code. Show the output of the algorithm (screenshots). • Analyze the best, worst and average case. Provide and analyze example inputs for the best, worst and average cases (use the implementation). Some good references: https://www.geeksforgeeks.org/quick-sort/ https://en.wikipedia.org/wiki/Quicksort
Q4- For each of the following situations, name the best sorting algorithm we studied. (For one or two questions, there may be more than one answer deserving full credit, but you only need to give one answer for each.) (a) The array is mostly sorted already (a few elements are in the wrong place). (b) You need an O(n log n) sort even in the worst case and you cannot use any extra space except for a few local variables.(c) The data to be sorted is too big to fit in memory, so most of it is on disk. (d) You have many data sets to sort separately, and each one has only around 10 elements. (e) You have a large data set, but all the data has only one of about 10 values for sorting purposes (e.g., the data is records of elementary-school students and the sort is by age in years).(f) Instead of sorting the entire data set, you only need the k smallest elements where k is an input to the algorithm but is likely to be much smaller than the size of the entire data set.
Binary Search algorithm uses the divide-and-conquer technique to find elements in O(logn) steps. Given the following sorted array that has 9 elements, what is the scope of the search (First index and last index of the array segment) in each iteration of the binary search algorithm while looking for the element "51"? Note: Numbers that show up in the first row are the array indexes 0. 1 3 4 6. 7 8. 9 12 19 21 30 32 37 44 51 1st Iteration -> First = 0, Last = 8 2nd Iteration -> First = 5, Last = 8 3rd Iteration -> First = 5, Last = 6 %3D O 1st Iteration -> First = 0, Last = 8 2nd Iteration -> First = 5, Last = 8 Brd Iteration -> First = 7, Last = 8 4th Iteration -> First = 8, Last = 8 O 1st Iteration -> First = 0, Last = 8 2nd Iteration -> First = 0, Last = 3 3rd Iteration -> First = 2, Last = 3 4th Iteration -> First = 3, Last = 3 O1st Iteration -> First = 0, Last = 8 2nd Iteration -> First = 0, Last 3 Brd Iteration -> First = 2, Last = 3
Assume the following list is being sorted using the Quick Sort algorithm. Describe the next step in the quick sort algorithm in terms of its effect on the pivot, left, and right indices and the content of the list. Note: For credit, do not just give a general description of the quick sort algorithm. Describe in this specific situation, what's compared to what, whether any data is moved, and how the indices are changed. pivot [0] [1] [2] [3] [4] [5] [6] [6] [7] [9] [8] [10] 34 25 39 94 17 78 41 45 91 56 77 86 left right
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…
Consider the algorithm for insertion sort shown below. The input to this algorithm is an array A. You must assume that indexing begins at 1.
True or False For each statement below, indicate whether you think it is True or False. 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
Binary Search algorithm uses the divide-and-conquer technique to find elements in O(logn) steps. Given the following sorted array that has 9 elements, what is the scope of the search (First index and last index of the array segment) in each iteration of the binary search algorithm while looking for the element "51"? Note: Numbers that show up in the first row are the array indexes 2 3 4 6 7 12 19 21 30 32 37 44 51 • 1st Iteration -> First = 0, Last = 8 2nd Iteration -> First = 5, Last = 8 3rd Iteration -> First = 5, Last = 6 1st Iteration -> First = 0, Last = 8 2nd Iteration -> First = 0, Last = 3 3rd Iteration -> First = 2, Last = 3 1st Iteration -> First = 0, Last = 8 2nd Iteration -> First = 5, Last = 8 3rd Iteration -> First = 7, Last = 8 4th Iteration -> First = 8, Last = 8 1st Iteration -> First = 0, Last = 8 2nd Iteration -> First = 0, Last = 3 3rd Iteration -> First = 2, Last = 3 4th Iteration -> First = 3, Last = 3
FRS-SEARCHING-7 Assume a sorted character array of size n = 26. It contains all the capital letters, i.e, 'A' to 'Z', in increasing order as array elements. Let the search key be equal to 'a' (lower case letter). What is the last letter that will be compared with the search key using binary search algorithm? You may choose not to enclose your answer within a pair of single quotes. Note: you may refer to https://www.asciitable.com/ for the ASCII values of the characters.
Q:During each iteration of Quick Sort algorithm, the first element of array is selected as a pivot. The algorithm for Quick Sort is given below. Modify it in such a way that last element of array should be selected as a pivot at each iteration. Also explain the advantages.
Big-O Solving (PYTHON) Question: Does the choice of the pivot affect the running time of quick sort? Why or why not? It would help if you could provide examples or illustrations. Given ONLY: Quick Sort is another sorting algorithm that follows a divide-and-conquer approach. The algorithm can be summarized in 3 steps: A pivot element is chosen, usually the first element. All elements smaller than the pivot are placed to the left of the pivot. This creates 2 partitions, elements greater than the pivot and elements less than the pivot. The 2 partitions are sorted using Quick Sort. Sample code in python3: def quick_sort(arr): def quick_sort_r(arr, start, end): if end - start < 2: # single element base case return # choose a pivot pivot = start # you may choose other elements store = pivot+1 # index to store less than elements # for all elements after the pivot for i in range(pivot+1, end): if arr[i] < arr[pivot]:…
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.