Insertion sort is a simple sorting algorithm where each iteration removes one element from an input data set and inserts it into its correct position within a partially sorted list until all elements are inserted.
Think of insertion sort like organizing playing cards in your hand. You start with an empty hand (sorted list) and pick up cards (elements) one by one from the table (input data set), inserting each card into its correct position in your hand.
Selection Sort: A sorting algorithm that repeatedly selects the smallest element from the unsorted part and moves it to the sorted part.
Merge Sort: A divide-and-conquer algorithm that divides an array into two halves, sorts them separately, and then merges them back together.
Quick Sort: A divide-and-conquer algorithm that picks an element as a pivot, partitions the array around this pivot, and recursively sorts subarrays before and after the pivot.
What is the time complexity of selection sort and insertion sort in the worst case scenario?
In insertion sort, when is an element inserted into the sorted subarray?
Which sorting algorithm is simpler: selection sort or insertion sort?
How does insertion sort work?
What is one advantage of insertion sort over selection sort?
Study guides for the entire semester
200k practice questions
Glossary of 50k key terms - memorize important vocab
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.