Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 3: Brute Force and Exhautive Search, Chapter 5: Divide-and-conquer…
Chapter 3: Brute Force and Exhautive Search
3.1 Selection Sort and Bubble Sort
Selection sort
Scanning the entire given list to find its smallest element and exchange it with the first element
Then we scan the list, starting with the second element to find the smallest among the last n − 1 elements and exchange it with the second element
Bubble Sort
Comparing adjacent elements of the list and exchange them if they are out of order
The next pass bubbles up the second largest element, and so on, until after n − 1 passes the list is sorted
Chapter 5: Divide-and-conquer
General plan:
A problem is divided into several subproblems of the same type, ideally of about equal size
The subproblems are solved (typically recursively, though sometimes a different algorithm is employed, especially when subproblems become small enough)
If necessary, the solutions to the subproblems are combined to get a solution to the original problem
5.1 Mergesort
It sorts a given array by dividing it into two halves and sorting each of them recursively and then
merging the two smaller sorted arrays into a single sorted one
Chapter 4: Decrease-and-Conquer
Is based on exploiting the relationship
between a solution to a giveninstance of a problem and a solution to its
smaller instance
4.1: Insertion sort
Based on a recursive idea
it is more efficient
to implement this algorithm bottom up