File:Insertion_sort.gif · Wikimedia Commons · See Wikimedia Commons
Insättningssortering
Sign in to savesorting algorithm that, at each iteration, inserts the current input element into the suitable position between the already sorted elements
Key facts
- Class
- Sorting algorithm
- Data structure
- Array
- Worst case performance
- O ( n 2 ) {\displaystyle O(n^{2})} comparisons and swaps
- Best case performance
- O ( n ) {\displaystyle O(n)} comparisons, O ( 1 ) {\displaystyle O(1)} swaps
- Average performance
- O ( n 2 ) {\displaystyle O(n^{2})} comparisons and swaps
- Worst case space complexity
- O ( n ) {\displaystyle O(n)} total, O ( 1 ) {\displaystyle O(1)} auxiliary
- Optimal
- No
via Wikipedia infobox
Article · Svenska
Insättningssortering, eller instickssortering, är en av de enklare sorteringsalgoritmer som finns tillgängliga inom datalogi. I praktiken använder man ofta snabbare sorteringsalgoritmer, men om listan redan är delvis sorterad kan den dock vara effektiv. Komplexiteten för insättningssortering är i allmänhet , där n är antalet element, om listan redan är någorlunda sorterad från början är dock insättningssortering en av de snabbare algoritmerna.
Abstract from DBpedia / Wikipedia · CC BY-SA