We are going to look at the idea of divide and conquer problem solving in the context of search algorithms. We will also introduce the idea of efficiency analysis as a way of comparing algorithms.
Searching for things by checking each place one by one seems an obvious thing to do - it is a simple algorithm. However, it is very slow. Divide and conquer gives much faster algorithms. It is the approach to solving a problem where you split the problem in half in a way which leaves you with a simpler version of the same problem - you are still looking for the same thing, just on a problem half the size. Do that over and over and you get the answer incredibly quickly.
Binary search is one search algorithm that uses such a divide and conquer approach. It assumes your data is sorted. Rather than checking each piece of data in turn, you go to the middle element and use that as a signpost. You check whether the thing you are looking for is bigger or smaller that it and then only search the bottom or top half of the data as appropriate. Because the data is in order you can tell which side it must be. You keep doing that until you only have one piece of data left and check if it is the thing you are after.
In computer science, binary search, also known as half-interval search or logarithmic search, is a search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.
Almost any list that comes out of a computer is sorted into some sort of order, and there are many more sorted lists inside computers that the user doesn’t see. Many clever algorithms have been devised for putting values into order efficiently.
The sorting algorithms you will learn share two basic operations in common. These operations are the comparison operation and the swap operation. We will look at each one in more detail before we examine our sorting algorithms.
Design a quick sort algorithm use the four steps of computational thinking to solve the problem
Implement your desgin using python clearly comment the code you have produced
Come up with your own algorithm for sorting a list of numbers into the correct order
