PrevNext
Not Frequent
 0/8

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 NN 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 [1,4)[1, 4).

#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 5
cout << 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 [1,4)[1, 4).

#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 5
for (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 O(NlogN)\mathcal{O}(N\log N) time sort (repeatedly extracting the minimum in O(N2)\mathcal{O}(N^2) time will always suffice).

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsSorting
CFEasy
Show TagsSorting
CFNormal
Show TagsGreedy, Sorting
BronzeNormal
Show TagsSimulation, Sorting
BronzeNormal
Show TagsSorting
BronzeHard
Show TagsSimulation, Sorting
CFHard
Show TagsGreedy, Sorting

Note: There are some more sorting problems in the Intro to Sets module.

Check Your Understanding

What would the array [7,2,6,3,1][7, 2, 6, 3, 1] be after 1 pass of bubble sort?

Question 1 of 4

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!

PrevNext