Introduction to Sorting
Authors: Darren Yao, Benjamin Qi, Allen Li, Andrew Wang
Arranging collections in increasing order.
Sorting refers to arranging items in some particular order.
Sorting Methods
Focus Problem – read through this problem before continuing!
Resources | ||||
---|---|---|---|---|
CPH | bubble sort, merge sort, counting sort | |||
CSA | selection sort, insertion sort, bubble sort, merge sort |
Library Sorting
Although you usually do not need to know how sorting is implemented, you should know how to use built-in methods.
C++
Resources | ||||
---|---|---|---|---|
CPH | can stop before user-defined structs, which are covered in silver | |||
CPP | reference | |||
CF | first two related to sorting |
Java
Resources | ||||
---|---|---|---|---|
tutorialspoint | Covers sorting arrays | |||
Oracle | API for sorting static arrays | |||
Oracle | API for sorting dynamic arrays |
Python
Resources | ||||
---|---|---|---|---|
PY | reference |
Static Arrays
C++
To sort static arrays, use sort(arr, arr + N)
where is the number of
elements to be sorted. The range can also be specified by replacing arr
and
arr + N
with the intended range. For example, sort(arr + 1, arr + 4)
sorts
indices .
#include <bits/stdc++.h>using namespace std;int main() {int arr[] = {5, 1, 3, 2, 4}; int N = 5;sort(arr, arr + N);for (int i = 0; i < N; i++)cout << arr[i] << " "; //1 2 3 4 5cout << endl;int arr2[] = {5, 1, 3, 2, 4};sort(arr2 + 1, arr2 + 4);for (int i = 0; i < N; i++)cout << arr2[i] << " "; //5 1 2 3 4}
Java
In order to sort a static array, use Arrays.sort(arr)
.
import java.util.*;class Main{public static void main (String[] args){int arr[] = {5, 1, 3, 2, 4};Arrays.sort(arr);for (int i = 0; i < arr.length; i++)System.out.print(arr[i] + " "); //1 2 3 4 5}}
Warning!
The Arrays.sort()
function uses quicksort on primitive data types such as
long
s. This is fine for USACO, but in other contests such as CodeForces, it
may time out on test cases specifically engineered to trigger worst-case
behavior in quicksort.
See here for an example of a solution that was hacked on CodeForces.
Two ways to avoid this:
- Declare the underlying array as an array of objects, for example
Long
instead oflong
. This forces theArrays.sort()
function to use mergesort, which is always . - Shuffle the array beforehand.
Dynamic Arrays
C++
In order to sort a dynamic array, use sort(v.begin(), v.end())
(or
sort(begin(v),end(v))
). The default sort function sorts the array in ascending
order. Similarly, we can specify the range. For example,
sort(v.begin() + 1, v.begin() + 4)
sorts indices .
#include <bits/stdc++.h>using namespace std;int main() {vector<int> v{5, 1, 3, 2, 4};sort(v.begin(), v.end());for (int i : v)cout << i << " "; //1 2 3 4 5cout << endl;v = {5, 1, 3, 2, 4};sort(v.begin() + 1, v.begin() + 4);for (int i : v)cout << i << " "; //5 1 2 3 4}
Java
In order to sort a dynamic array, use Collections.sort(list)
. The default sort
function sorts the array in ascending order.
import java.util.*;class Main{public static void main (String[] args){ArrayList<Integer> arr = new ArrayList<Integer>();arr.add(5); arr.add(1); arr.add(3); arr.add(2); arr.add(4);Collections.sort(arr);for (int i : arr)System.out.print(i + " "); //1 2 3 4 5}}
(Dynamic) Arrays of Pairs & Tuples
C++
By default, C++ pairs are sorted by first element and then second element in case of a tie.
// Source: CPH#include <bits/stdc++.h>using namespace std;int main() {vector<pair<int,int>> v;v.push_back({1,5});v.push_back({2,3});v.push_back({1,2});
Tuples are sorted similarly.
Java
You'll need to define your own custom comparator. This is covered in Silver.
Python
By default, Python tuples sort by first element, then second element, and so on in case of repeated ties.
list = [(1, 2), (2, 3), (2, 1), (3, 1)]list = sorted(list)for x, y in list:print(f'{x}, {y}')# Output:# 1, 2# 2, 1# 2, 3# 3, 1
Problems
Warning!
Bronze problems are designed that you shouldn't need a time sort (repeatedly extracting the minimum in time will always suffice).
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CSES | Easy | Show TagsSorting | |||
CF | Normal | Show TagsGreedy, Sorting | |||
Bronze | Normal | Show TagsSimulation, Sorting | |||
Bronze | Hard | Show TagsSimulation, Sorting |
Note: There are some more sorting problems in the Intro to Sets module.
Check Your Understanding
What would the array be after 1 pass of bubble sort?