Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sorting Algorithms - efficiency depends on the number of comparisons and…
Sorting Algorithms
- efficiency depends on the number of comparisons and the number of swaps
Bubble Sort (Simple)
compare adjacent elements
exchange adjacent elements if they are out of order
Big O complexity:
O(N^2)
Selection Sort (Simple)
finds the smallest number in the list and places it first, then finds the smallest number remaining and and places it in second etc.
it
makes n-1 passes
through a sequence of n elements
Big O compexity:
O(N)
Quick Sort (Advanced)
selects an element in the array, called
the pivot
array is divided so that all elements to the
left are less than the pivot
, and all the elements to the
right are greater than the pivot
fastest when the median value of the array is chosen as the pivot - Big O complexity:
O(N*logN)
Phase 1:
Partition Phase
, Phase 2:
Sort Phase
recursively apply the quick sort to the first part and then to the second
slowest when the array is already or close to being sorted - Big O complexity:
O(N^2)
Advantages
one of the fastest algorithms on average -
Time Complexity
doesn't require additional memory, the sorting takes place in the array
Space Complexity
never used in applications which require guarantee of response time - Life-critical eg. medical monitoring
Insertion Sort (Simple)
about
twice as fast as Bubble Sort
- for data that is
already partially sorted
not too complex for the efficiency offered
faster than Selection Sort in normal situations
sorts a list by repeatedly inserting an unsorted element into a sorted sublist until the whole list is sorted
similar to Bubble Sort
for
data in inverse sorted order - has to execute every comparison
Big O complexity:
O(N^2)
for random data, much better for partially sorted
O(N)
Merge Sort (Advanced)
Big O complexity:
O(N*logN)
a sorting A based on the
Divide & Conquer
paradigm
Conquer
- the sub-problems by solving them recursively
Divide
- the problem into sub-problems that are similar to the original but smaller in size
sorts a collection (array) of n elements into
non-decreasing order
Space Complexity
- requires additional memory of size
n