To implement a program that sorts the given array elements using Quick Sort algorithm.
Quick Sort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of Quick Sort that pick pivot in different ways. Always pick the first element as a pivot. Always pick the last element as a pivot (implemented below). Pick a random element as a pivot. Pick median as the pivot. The key process in Quick Sort is a partition(). The target of partitions is, given an array and an element "x" of an array as the pivot, put "x" at its correct position in a sorted array and put all smaller elements (smaller than x) before "x", and put all greater elements (greater than x) after "x". All this should be done in linear time.
The divide and conquer strategy is a problem-solving approach in computer science and mathematics that involves breaking down a complex problem into smaller subproblems, solving them independently, and then combining the solutions to solve the original problem. The name comes from the three main steps involved:
The divide and conquer strategy is often used to solve problems that are difficult to solve directly, such as sorting algorithms, matrix multiplication, and finding the closest pair of points in a set.
The main advantage of the divide and conquer strategy is that it allows for parallel processing of the subproblems, which can result in faster processing times. Additionally, it can be easier to reason about and debug smaller subproblems rather than the original, larger problem.
Some common algorithms that use the Divide and Conquer strategy include: