insertion sort
<algorithm> A sorting algorithm that inserts each item in the proper place into an initially empty list by comparing it with each item in the list until it finds the new element's successor or the end of the list. Compare bubble sort. (1997-02-12) | ||||
Search Dictionary:
Insertion sort definition was found in categories: Language, Idioms & Slang(1) Encyclopedia(1)
Insertion sort Definition from Language, Idioms & Slang Dictionaries & Glossaries
| hEnglish - advanced version |
insertion sort
insertion sort
a sorting algorithm that inserts each item in the proper place into an initially empty list by comparing it with each item in the list until it finds the new element's successor or the end of the list.
insertion sort
a sorting algorithm that inserts each item in the proper place into an initially empty list by comparing it with each item in the list until it finds the new element's successor or the end of the list.
Insertion sort Definition from Encyclopedia Dictionaries & Glossaries
| Wikipedia English - The Free Encyclopedia |
Insertion sort
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:
- Simple to implement
- Efficient on (quite) small data sets
- Efficient on data sets which are already substantially sorted: it runs in O(n + d) time, where d is the number of inversions
- More efficient in practice than most other simple O(n2) algorithms such as selection sort or bubble sort: the average time is n2/4 and it is linear in the best case
- Stable (does not change the relative order of elements with equal keys)
- In-place (only requires a constant amount O(1) of extra memory space)
- It is an online algorithm, in that it can sort a list as it receives it.
| See more at Wikipedia.org... |