Please enable JavaScript.
Coggle requires JavaScript to display documents.
Exhaustive Search, Sorting - Coggle Diagram
Exhaustive Search
Bubble Sort
- Compare adjacent elements of the list
- Swap if they're out of order
-
-
-
However, there are Ө(n²) key swaps
Selection Sort
-
-
- Scan the entire given list to find the smallest element
- Swap it with the first element
- Scan the unordered part of the list for its smallest element
- Swap it with the first element of the remaining list
-
Note: a first application of the brute-force approach often results in an algorithm that can be improved with a modest amount of effort
Sorting
Decrease-and-Conquer
Exploits the relationship between the solution of a problem and the solution for its smaller version:
-
-
-
Insertion Sort
Starting with the first element of the array, each A[i] is inserted (one at a time) in its already sorted spot among the first i elements of the array
-
-
-
-
Divide-and-Conquer
Consists in dividing a problem into several subproblems, solving each one of them and combining those solutions to solve the original problem.
Merge Sort
Recursively divides an array into two halves, sorting each one of them recursively, and then merging them into a single sorted array.
-
-