- 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
- 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
Insertion Sort is a simple algorithm that works well on small inputs, but its too slow for large-scale sorting. Instead, algorithms like QuickSort are used, which will be covered in these challenges. The first step of quicksort is to partition an array into two parts.
Given an array 'ar' and a number 'p' in the first cell in the array, can you partition the array so that all elements greater than 'p' are to the right of it and all the numbers smaller than 'p' are to its left?
For example, if given the following as input:
4 5 3 9 1
The first number
4 is the pivot, so you should put the smaller numbers to the left, and the larger to the right, and output:
3 1 4 5 9
The array should otherwise remain in the same order.
The Input is similar to the previous challenges. Output the correctly partitioned array.