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 – try your best to solve 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.
Resources | ||||
---|---|---|---|---|
CPH | can stop before user-defined structs, which are covered in silver | |||
CPP | reference | |||
CF | first two related to sorting |
Static Arrays
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}
Dynamic Arrays
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());// Outputs 1 2 3 4 5for (int i : v) { cout << i << " "; }cout << endl;
(Dynamic) Arrays of Pairs & Tuples
By default, C++ pairs are sorted by first element and then second element in case of a tie.
#include <bits/stdc++.h>using namespace std;int main() {vector<pair<int, int>> v{{1, 5}, {2, 3}, {1, 2}};sort(v.begin(), v.end());/** Outputs:* 1 2* 1 5* 2 3*/for (pair<int, int> p : v) { cout << p.first << " " << p.second << endl; }}
Tuples are sorted similarly.
Problems
Warning!
Bronze problems are designed so 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 | Easy | Show TagsSorting | |||
CF | Normal | Show TagsGreedy, Sorting | |||
Bronze | Normal | Show TagsSimulation, Sorting | |||
Bronze | Normal | Show TagsSorting | |||
Bronze | Hard | Show TagsSimulation, Sorting | |||
CF | Hard | Show TagsGreedy, 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?
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!