Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sorting - Coggle Diagram
Sorting
Internal Sort
Requires that the collection of data fit entirely in the computer’s main memory
Suitable to sort a small size of list
Advantages
Easier to understand and analyze data collection
Searching process will be much faster
External Sort
The collection of data will not fit in the computer’s main memory all at once, but it must reside (locate) in secondary storage
Suitable to sort large size of data
Simple Sort
Quadratic Sorting Algorithm
Selection
choose the largest/smallest item and place the item
in its correct place and repeat the process
does not depend on initial arrangement
Number of Comparisons
Best/Average/Worst Case = O(n^2)
suitable for small n-O(n^2) algorithm
Number of Swaps
Best/average/worse case: O(n)
Insertion
Take each item from the unsorted region and insert it into its correct order in the sorted region
Find next unsorted element and insert it in correct place, relative to the ones already sorted
Appropriate for small arrays due to its simplicity
Number of Comparisons
Best Case = O(n)
Average/Worst Case = O(n^2)
Number of Swaps
Best Case: 0
Average/worst case: O(n^2)
Bubble
Compare adjacent element and exchange if out of order
Number of Comparisons
Best/Average/Worst Case = O(n^2)
suitable for small size of data
Improved Bubble Sort
condition check whether the list is sorted
Number of Comparisons
Best Case = O(n)
Average/Worst Case = O(n^2)
Number of Swaps
Best case: 0
Average/Worst Case: O(n^2)
Number of Swaps
Best Case: 0
Average/Worse: O(n^2)
Advanced Sort
Divide and Conquer Sorting Algorithm
Merge
-Divide an array into halves until only one piece left
-Sort each half
-Merge the sorted halves into one sorted array
Performance is independent of the initial order of
the array items
– Worst case: O(n
log2n)
– Average case: O(n
log2n)
Advantage
Mergesort is an extremely fast algorithm
Disadvantage
Mergesort requires a second array (temporary array) as
large as the original array
Quick
– Choose a pivot (first element in the array)
– Partition the array about the pivot
– Sort the left section again until there is one item left
– Sort the right section again until there is one item left
The efficiency of quick sort
depends on the pivot value.
Average case: O(n * log2n)
Worst case: O(n^2)
Quicksort is usually extremely fast in practice
– Even if the worst case occurs, quicksort’s performance is acceptable for moderately large arrays
recursive sorting algorithm
A process in which data in a list are organized in certain order (ascending/descending)