Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sorting Algorithms - Coggle Diagram
Sorting Algorithms
Brute-Force
Selection Sort
-
Given an array, this sorting algorithm searches for the smallest item among the last n-i elements and swaps it with Ai, in other words, the ideia is to find the smallest element and exchange it with the first one.
Disadvantages
-
-
It always do (n²-n)/2 comparison, doesn't matter if the array is ordered or not
Advantages
-
-
It doesn't use one auxiliary array and the consequence of this is that it consumes less memory to realize the sorting
Space Complexity
Worst Case: O(n) total, O(1) auxiliary
Bubble Sort
Time Complexity
-
-
Best Case: O(n)
The best case is only O(n) if we check if there was no swaps on the first pass through the array, and if there isn't, the algorithm should stop running because this means array is ordered
Advantages
It is simple to implement and understand, and also it requires just few lines of code
The data is sorted in place so there is little memory overhead and, once sorted, the data is in memory
Given an array, this sorting algorithm repeatedly compares each pair of adjacent items and swaps them if they are not in order. The process repeats until no more swaps occur
-
Space Complexity
Worst Case: O(n) total, O(1) auxiliary
Divide-and-Conquer
Mergesort
Time Complexity
-
-
Best Case: Big-Theta(n log n) typical, Big-Theta(n) natural variant
It sorts a given array A[0..n-1] by dividing it into two halves A[0..n/2−1] and A[n/2..n−1], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one
-
Advantages
A noteworthy advantage of mergesort over quick-sort and heapsort (two advanced sorting algorithms) is its stability
Disadvantages
-
Extra memory usage. The algorithm creates a copy of the array for each level of recursive call, totalizing the additional memory usage equal to O(n log n)
Decrease-and-Conquer
Insertion Sort
-
Space Complexity
Worst Case: O(n) total, O(1) auxiliary
-
-
-