Question

In: Computer Science

Sorting (quick) Sort the array using quick sort. Write the array content after each pass (i.e.,...

Sorting (quick)

Sort the array using quick sort. Write the array content after each pass (i.e., from pass 1 to pass 7). Each pass is defined as the completion of one partition. We always pick the first array element as the pivot for each partition.

Solutions

Expert Solution

Quick sort is a type of sorting algorithm. It works on the principle of divide and conquer.

  

Here is how quicksort uses divide-and-conquer. As with merge sort, think of sorting a subarray array[p..r], where initially the subarray is array[0..n-1].

  1. Divide by choosing any element in the subarray array[p..r]. Call this element the pivot.

    Rearrange the elements in array[p..r] so that all elements in array[p..r] that are less than or equal to the pivot are to its left and all elements that are greater than the pivot are to its right. We call this procedure partitioning. At this point, it doesn't matter what order the elements to the left of the pivot are in relation to each other, and the same holds for the elements to the right of the pivot. We just care that each element is somewhere on the correct side of the pivot.

    As a matter of practice, we'll always choose the rightmost element in the subarray, array[r], as the pivot. So, for example, if the subarray consists of [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], then we choose 6 as the pivot. After partitioning, the subarray might look like [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Let q be the index of where the pivot ends up.

  2. Conquer by recursively sorting the subarrays array[p..q-1] (all elements to the left of the pivot, which must be less than or equal to the pivot) and array[q+1..r] (all elements to the right of the pivot, which must be greater than the pivot).

  3. Combine by doing nothing. Once the conquer step recursively sorts, we are done. Why? All elements to the left of the pivot, in array[p..q-1], are less than or equal to the pivot and are sorted, and all elements to the right of the pivot, in array[q+1..r], are greater than the pivot and are sorted. The elements in array[p..r] can't help but be sorted!

    Think about our example. After recursively sorting the subarrays to the left and right of the pivot, the subarray to the left of the pivot is [2, 3, 5], and the subarray to the right of the pivot is [7, 9, 10, 11, 12, 14]. So the subarray has [2, 3, 5], followed by 6, followed by [7, 9, 10, 11, 12, 14]. The subarray is sorted.

The base cases are subarrays of fewer than two elements, just as in merge sort. In merge sort, you never see a subarray with no elements, but you can in quicksort, if the other elements in the subarray are all less than the pivot or all greater than the pivot.

Let's go back to the conquer step and walk through the recursive sorting of the subarrays. After the first partition, we have subarrays of [5, 2, 3] and [12, 7, 14, 9, 10, 11], with 6 as the pivot.

To sort the subarray [5, 2, 3], we choose 3 as the pivot. After partitioning, we have [2, 3, 5]. The subarray [2], to the left of the pivot, is a base case when we recurse, as is the subarray [5], to the right of the pivot.

To sort the subarray [12, 7, 14, 9, 10, 11], we choose 11 as the pivot. After partitioning, we have [7, 9, 10] to the left of the pivot and [14, 12] to the right. Then the subarrays are sorted, resulting in [7, 9, 10], followed by 11, followed by [12, 14].

Here is how the entire quicksort algorithm unfolds. Array locations in blue have been pivots in previous recursive calls, and so the values in these locations will not be examined or moved again.


Related Solutions

Sorting (merge) Sort the array (as in Part 2) using merge sort. Write the array content...
Sorting (merge) Sort the array (as in Part 2) using merge sort. Write the array content after each pass (i.e., from pass 1 to pass 9). Each pass is defined as the completion of one merge operation. Suppose an array contains the following integers: -1, 20, 10, -5, 0, -7, 100, -7, 30, -10. Sort the array using the following algorithms: selection sort, bubble sort, and insertion sort. For each algorithm, write the array content after each pass (i.e., from...
use quick sort to sort the following array. show each pass and what the pivot is...
use quick sort to sort the following array. show each pass and what the pivot is during the pass. please explain why you are swapping positions. do not use a compiler. 30 5 40 11 20 9 15 2 60 25 80 3 73 35 4 75 20 6
Compute the first 4 pivots using quick sort algorithm on an array A=<10,15,17,18,6,120,30,250,95>. Write the content...
Compute the first 4 pivots using quick sort algorithm on an array A=<10,15,17,18,6,120,30,250,95>. Write the content of the array A after each pivot is chosen.
Write a program in Java to sort the given array using merge sort, quick sort, insertion...
Write a program in Java to sort the given array using merge sort, quick sort, insertion sort, selection sort and bubble sort based on the input from the user which sorting technique they wanted to use. Get the array size, array elements from the user, and also display the sorted array along with the name of the sorting technique used.
Write a function to sort data (in increasing order) in an array using a. pass by...
Write a function to sort data (in increasing order) in an array using a. pass by value b. and pass by reference.
Write a MIPS program that uses an implementation of quick sort to sort an array of...
Write a MIPS program that uses an implementation of quick sort to sort an array of numbers (Translate the following code into (Mars Assembly language). Quicksort Implementation - C int partition(int arr [] , int left , int right) { int i=left, j=right; int tmp; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr [ i ] < pivot) i ++; while (arr [ j ] > pivot) j −−; if (i <= j)...
* Sort Student array descending based on GPA using MERGE sort. Sorting will be done in...
* Sort Student array descending based on GPA using MERGE sort. Sorting will be done in place. * * @param students array to be sorted, can be empty, but cannot be null */ public static void sortGPA(Student[] students) { // TODO: implement this } Student class: public class Student extends Person { private double GPA; public Student(String lastName, String firstName, double gpa) { super(lastName, firstName); this.GPA = gpa; } public double getGPA() { return GPA; } @Override public boolean equals(Object...
Implementation of Quick sort and heap sorting algorithms in C++ FULL PROGRAMM BOTH THE QUICK SORT...
Implementation of Quick sort and heap sorting algorithms in C++ FULL PROGRAMM BOTH THE QUICK SORT AND HEAP SORT IN THE SAME PROGRAMM
Implementation of Quick sort and heap sorting algorithms in C++ FULL PROGRAMM BOTH THE QUICK SORT...
Implementation of Quick sort and heap sorting algorithms in C++ FULL PROGRAMM BOTH THE QUICK SORT AND HEAP SORT IN THE SAME PROGRAM PS: YOU ARE ANSEWRING THE SAME PROGRAMS I WANT DIFFERENT ONE PLEASE , THANK YOU . BECAUSE THE ONE WERE POSTING DOESNT WORKING !!
Import a data set (txt file) then do the sorting algorithm using quick sort, shell sort,...
Import a data set (txt file) then do the sorting algorithm using quick sort, shell sort, and selection sort. It must show how long it took and how many movements occurred. Please write codes in C++ Here's data set (should be stored in txt file) 7426 4524 4737 9436 3997 2757 6288 5414 9590 5968 6638 3199 9514 1541 9866 2144 6731 911 2171 6135 6437 912 9417 2662 6606 6349 707 2890 5386 9718 3492 5068 9674 8578 8323...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT