Sorting Algorithm Quiz - Quick Sort

1) Quick sort uses

Exchanging

Partitioning

Selection

Merging

Quick sort uses partitioning to divide the input array into two sub-arrays, one with elements smaller than a chosen pivot and the other with elements larger than the pivot. This process is repeated recursively on each sub-array until the entire array is sorted. Partitioning is a crucial step in the quick sort algorithm as it determines the position of the pivot element and helps in efficiently sorting the array.

Explanation

Quick sort uses partitioning to divide the input array into two sub-arrays, one with elements smaller than a chosen pivot and the other with elements larger than the pivot. This process is repeated recursively on each sub-array until the entire array is sorted. Partitioning is a crucial step in the quick sort algorithm as it determines the position of the pivot element and helps in efficiently sorting the array.

2) "Divide-and-conquer" refers to:

The list being divided into only two sublists, never more or less, which are sorted and merged back together.

The list being divided into smaller sublists, then those sorted sublists are merged back together.

"Divide-and-conquer" is a problem-solving technique that involves breaking down a problem into smaller subproblems, solving them independently, and then combining the solutions to solve the original problem. In the context of the given options, the correct answer states that the list is divided into smaller sublists, which implies that the original problem is being divided into smaller subproblems. These sublists are then sorted independently, representing the solving of the subproblems, and finally merged back together, representing the combination of the solutions to solve the original problem.

Explanation

"Divide-and-conquer" is a problem-solving technique that involves breaking down a problem into smaller subproblems, solving them independently, and then combining the solutions to solve the original problem. In the context of the given options, the correct answer states that the list is divided into smaller sublists, which implies that the original problem is being divided into smaller subproblems. These sublists are then sorted independently, representing the solving of the subproblems, and finally merged back together, representing the combination of the solutions to solve the original problem.

3) In this sequence, 11 4 20 45 32 60 98 70, which element seems to be the pivot?

70

20

98

4

The sequence appears to be alternating between adding and subtracting numbers. Starting with 11, we subtract 7 to get 4, then add 16 to get 20, subtract 25 to get 45, and so on. The pivot element is the one that breaks this pattern. In this case, the pattern is broken between 20 and 45, where we subtract 13 instead of adding or subtracting a multiple of 9. Therefore, the pivot element is 20.

Explanation

The sequence appears to be alternating between adding and subtracting numbers. Starting with 11, we subtract 7 to get 4, then add 16 to get 20, subtract 25 to get 45, and so on. The pivot element is the one that breaks this pattern. In this case, the pattern is broken between 20 and 45, where we subtract 13 instead of adding or subtracting a multiple of 9. Therefore, the pivot element is 20.

4) Using quick sort is a stable way of sorting

True

False

Quick sort is not a stable way of sorting. Stability in sorting means that the relative order of equal elements is preserved in the sorted output. In quick sort, the elements are partitioned based on a pivot, and the order of equal elements may change during the partitioning process. Therefore, quick sort does not guarantee stability in sorting.

Explanation

Quick sort is not a stable way of sorting. Stability in sorting means that the relative order of equal elements is preserved in the sorted output. In quick sort, the elements are partitioned based on a pivot, and the order of equal elements may change during the partitioning process. Therefore, quick sort does not guarantee stability in sorting.

5) What are the correct intermediate steps of the following data set when it is being sorted with the Quick sort?
15,20,10,18

15,10,20,18 -- 15,10,18,20 -- 10,15,18,20

15,20,10,18 -- 15,10,20,18 -- 10,15,20,18

10, 20,15,18 -- 10,15,20,18 -- 10,15,18,20

10, 20,15,18 -- 10,18,15,20 -- 10,15,18,20

The given answer shows the correct intermediate steps of the data set being sorted with the Quick sort algorithm. The first step is to partition the array around a pivot element, which in this case is 10. After partitioning, the array becomes 10, 20, 15, 18. Then, the same process is applied to the two sub-arrays formed by the partition. The next pivot element is 15, and after partitioning, the array becomes 10, 18, 15, 20. Finally, the last pivot element is 18, and after partitioning, the array becomes 10, 15, 18, 20, which is the sorted array.

Explanation

The given answer shows the correct intermediate steps of the data set being sorted with the Quick sort algorithm. The first step is to partition the array around a pivot element, which in this case is 10. After partitioning, the array becomes 10, 20, 15, 18. Then, the same process is applied to the two sub-arrays formed by the partition. The next pivot element is 15, and after partitioning, the array becomes 10, 18, 15, 20. Finally, the last pivot element is 18, and after partitioning, the array becomes 10, 15, 18, 20, which is the sorted array.