Our Objective

To implement a program that sorts the given array elements using Quick Sort algorithm. 

The Theory

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.

Divide and Conquer strategy

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:

1. Divide: Break the original problem down into smaller, more manageable subproblems.
2. Conquer: Solve the subproblems independently.
3. Combine: Combine the solutions to the subproblems to solve the original problem.

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:

• Merge Sort: A sorting algorithm that divides the input array into two halves, sorts each half independently, and then merges the sorted halves back together.
• Quick Sort: A sorting algorithm that partitions the input array into two subarrays around a pivot value, recursively sorts the subarrays, and then combines the sorted subarrays.
• Binary Search: A search algorithm that divides the input array in half at each step, reducing the search space until the desired value is found.

Learning Outcomes 

• Implementing the Quick sort algorithm requires an understanding of sorting algorithms, their time and space complexities, and their advantages and disadvantages.
• Implementing the Quick sort algorithm requires familiarity with recursion and recursive problem-solving techniques.
• Implementing the Quick sort algorithm requires programming skills such as using loops, conditionals, recursion, and array operations to perform the necessary computations.
• Analyzing the time complexity of the Quick sort algorithm can help students gain an understanding of algorithmic efficiency and the trade-offs between time and space complexity.
• Implementing the Quick sort algorithm requires problem-solving skills to identify the inputs needed, the steps involved in the algorithm, and the output to be generated.