 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
 QuickSort 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+...+(N1) operations, or N^{2} / 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.