Please enable JavaScript.
Coggle requires JavaScript to display documents.
Selection Sort & Bubble Sort (Brute Force) - Coggle Diagram
Selection Sort & Bubble Sort (Brute Force)
Selection Sort
1-Scan the entire list to find its smallest element
2- Exchange it (smallest element) with the first element
Its final position in the sorted list
3- Scan the list, starting with the second element
4- Find the smallest element among the last
n-1
elements
5- exchange it(smallest element) with the second element
Its final position in the sorted list
.
.
.
Generally:
The algorithm passes
i
times through the List
Select the smallest element among the last
n-i
elements
Swap with the
Ai
element (A=Array, i= Array index)
After
n-1
passes, the list is sorted
Algorithm Analysis:
Input Size
Number of elements
n
Basic operation
A[j ] < A[min
] (Key comparison)
Number of execution times:
Depends on the Array Size
Asymptotic efficiency
BigTheta(n2)
Bubble Sort
1- Compare adjacent
elements of the list
2- If they are:
In order
Select the next adjacentsones
Out of order
Exchange them
Generally:
The algorithm "bubbles up" the largest element to the end of the list
The next pass "bubbles up" the
n
largest element
The algorithm run until
n − 1
passes, then the list is sorted
:Algorithm Analysis
Input Size
Number of elements
n
Basic Operation
Key Comparisons
Obteined by a sum
Key Swaps
Depend on the Input
Worst Case:
Same as Key Comparisons
Asymptotic efficiency
BigTheta(n2)