Simple Sorting : Insertion Sort
The insertion sort is better than the bubble sort and the selection sort.
Process
For a better understanding, we will describe the process from the middle.
- Outer loop : Record the current value (e.g. index 6) as temp (The values at the left are partially sorted).
- Inner loop : Start comparison to the left
- For each Inner pass : [If inner - 1 > temp] then [move inner - 1 to inner] else [move temp to inner]
- Outer loop : move to the right (e.g. index 7)
- continue above steps until end of outer loop
Java:
Python:
The insertion sort runs in O(N2) time.
As a bonus, you can see below a version which removes duplicate:
As a bonus, you can see below a version which removes duplicate:
Comments
Post a Comment