- Introduction to Challenges
- Insertion Sort 1
- Insertion Sort Itself
- Correctness and the Loop Invariant
- Running Time
-
Counting Sort 1 - Simple Counting Sort
- Prepare for Full Counting Sort
- The Full Counting Sort
-
QuickSort1 - Simple Quick Sort
- Quick-Sort Advanced
- Quick Sort Running Time
Input Format for standard Sorting Challenges:
- t - the number of test cases
- s - the size of the array
- ar - the list of integers
Running Time
The running time of an algorithm for a specific input is the number of operations executed. We usually want to know how many operations an algorithm will take in proportion to the size of its input, N. We will look at how many shifts Insertion Sort takes.
For each element V in an array of N numbers, InsertionSort shifts everything to the right until it can insert V into the array. If the array is already sorted, it will take 0 shifts to verify that.
The worst case for Insertion Sort is if the array is in reverse order. To insert each number, the algorithm will need to shift over that number to the beginning of the array. Sorting the entire array of N numbers will therefore take 1+2+...+(N-1) operations, or N2 / 2.
Click for More
Challenge
How many shifts does Insertion Sort take?
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.