Insertion Sort: Difference between revisions
Add the algorithm. |
mNo edit summary |
||
| (5 intermediate revisions by the same user not shown) | |||
| 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: | ||
* '''Subarray:''' $[1, j-1]$ is sorted. | |||
* '''Key:''' $[j]$ is the key we concern with. | |||
* '''Subarray:''' $[j+1, A.length]$ is concerned. | |||
As the insertion sort operates, it is guaranteed that $[1, j-1]$ is sorted. | |||
== Informal Analysis == | |||
=== Loop Invariant<ref>Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Cambridge, MA: The MIT Press. ISBN 978-0-262-03384-8.</ref> === | |||
==== Initialization ==== | |||
It is true prior to the first iteration of loop. As we start with $j$ as $2$, we assumed it as trivial that $A[1]$ is sorted. | |||
==== Maintenance ==== | |||
During maintenance, each key points to the right side if the condition at Line $4$ is met, and by Line $7$ an empty space is left to be inserted. After Line $7$ is executed, subarray $[1 \cdot \cdot j]$ is sorted, and afterwards we increment $j$ for next iteration. | |||
==== Termination ==== | |||
It is known that loop terminates when $j > A.length$. At this occurrence $j=A.length+1$ and subarray $A[1 \cdot\cdot j-1]$ is proven to be sorted during maintenance. Plugging $j$, $A[1 \cdot\cdot A.length + \cancel{1} - \cancel{1}]$. | |||
== References == | |||
<references /> | |||
Latest revision as of 14:58, 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.
- 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:
- Subarray: $[1, j-1]$ is sorted.
- Key: $[j]$ is the key we concern with.
- Subarray: $[j+1, A.length]$ is concerned.
As the insertion sort operates, it is guaranteed that $[1, j-1]$ is sorted.
Informal Analysis
Loop Invariant[1]
Initialization
It is true prior to the first iteration of loop. As we start with $j$ as $2$, we assumed it as trivial that $A[1]$ is sorted.
Maintenance
During maintenance, each key points to the right side if the condition at Line $4$ is met, and by Line $7$ an empty space is left to be inserted. After Line $7$ is executed, subarray $[1 \cdot \cdot j]$ is sorted, and afterwards we increment $j$ for next iteration.
Termination
It is known that loop terminates when $j > A.length$. At this occurrence $j=A.length+1$ and subarray $A[1 \cdot\cdot j-1]$ is proven to be sorted during maintenance. Plugging $j$, $A[1 \cdot\cdot A.length + \cancel{1} - \cancel{1}]$.
References
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Cambridge, MA: The MIT Press. ISBN 978-0-262-03384-8.