Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sorting Algorithms - Coggle Diagram
Sorting Algorithms
Considering the application of the brute-force approach to the problem of sorting given a list of n orderable items, we can use two algorithms:
Selection Sort
On the ith pass through the list, which we number from 0 to n − 2, the algorithm searches for the smallest item among the last n − i elements and swaps it with Ai:
After n − 1 passes, the list is sorted.
Selection sort is a big tetha(n^2) algorithm on all inputs.
The number of key swaps is only (n), or, more precisely, n−1
-
Bubble Sort:
Compare adjacent elements of the list and exchange them if they are out of order. By doing it repeatedly, we end up “bubbling up” the largest element to the last position on the list.
-
The number of key swaps, however, depends on the input. In the worst case of decreasing arrays, it is the same as the number of key comparisons. Big Tetha(n^2).
We can improve it if a pass through the list
makes no exchanges, the list has been sorted and we can stop the algorithm
-
-