Algorithm Comparison
Compare algorithmic efficiency and operation counts side-by-side.
Live Statistics
Binary Insertion Sort
Binary Insertion Sort improves upon standard Insertion Sort by minimizing the number of comparisons. Instead of linearly scanning backwards to find the insertion point, it uses Binary Search on the already-sorted portion of the array. While this reduces the comparison complexity to , the algorithm still requires write operations to shift elements to make room for the insertion.
Steps
- Assume the first element is a sorted sub-array.
- Select the next element as the key.
- Perform a Binary Search on the sorted sub-array to find the index of the first element greater than the key.
- Shift all elements from that index onwards one position to the right to create a gap.
- Insert the key into the gap.
- Repeat until the entire array is sorted.
Bogo Sort
Bogo Sort, also known as Permutation Sort or Stupid Sort, is a sorting algorithm based on the generate and test paradigm. It is not used for practical sorting but serves as an excellent educational tool to illustrate the concept of a "perverse" or brute-force algorithm. The strategy is simple: if the list is not sorted, shuffle it randomly and check again. This continues until the single correct permutation is found by pure chance.
Steps
- 1. Check Order: Iterate through the list to check if it is sorted. If it is, the algorithm is complete.
- 2. Shuffle: If the list is not sorted, randomly shuffle all of its elements to create a new, random permutation.
- 3. Repeat: Go back to step 1 and repeat the process indefinitely until the sorted permutation is generated.