Insertion Sort: Difference between revisions
Add the algorithm. |
Introductory page. |
||
| Line 12: | Line 12: | ||
j = j - 1 | j = j - 1 | ||
A[j + 1] = key | A[j + 1] = key | ||
}} | }}'''Insertion sort''' is an algorithm for [[Sorting Problem]], arranging an un-ordered list to an ordered list. We assume the first element of the un-ordered list to be ordered such that: | ||
* '''Sub-array:''' $[1, j-1]$ is sorted. | |||
* '''Key: $'''[j]$ is the key we concern with. | |||
* '''Sub-array:''' $[j+1, A.length]$ is concerned. | |||
As the insertion sort operates, it is guaranteed that $[1, j-1]$ is sorted. | |||
Revision as of 14:18, 4 August 2026
This article is a stub. It might be missing pseudocode, complexity analysis, or a correctness sketch. It might need some other information which is incomplete perhaps.
Insertion sort
Insertion-Sort(A)
- for i = 2 to A.length
- key = A[i]
- j = i - 1
- while j > 0 and A[j] > key
- A[j + 1] = A[j]
- j = j - 1
- A[j + 1] = key
Insertion sort is an algorithm for Sorting Problem, arranging an un-ordered list to an ordered list. We assume the first element of the un-ordered list to be ordered such that:
- Sub-array: $[1, j-1]$ is sorted.
- Key: $[j]$ is the key we concern with.
- Sub-array: $[j+1, A.length]$ is concerned.
As the insertion sort operates, it is guaranteed that $[1, j-1]$ is sorted.