PrevNext

You're not signed in!

Sign in to save your progress and sync your settings across devices.

Not Frequent
 0/2

Introduction to Sorting

Authors: Darren Yao, Benjamin Qi, Allen Li

Sorting, and maintaining collections of distinct elements with ordered sets.

Sorting refers to arranging items in some particular order.

Warning!

Bronze problems are (almost always) designed that you shouldn't need to sort, though the concept can come in very handy for some problems. This module is optional for Bronze contestants.

Sorting Methods

Focus Problem – read through this problem before continuing!

Resources
CPHbubble sort, merge sort, counting sort
CSAselection 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
CPHcan stop before user-defined structs, which are covered in silver
CPPreference
CFfirst two related to sorting

Java

tutorialspointCovers sorting arrays

Python

Resources
PYreference

(Dynamic) Arrays

C++

In order to sort a dynamic array, use sort(v.begin(), v.end()) (or sort(begin(v),end(v))), whereas static arrays require sort(arr, arr + N) where NN is the number of elements to be sorted. The default sort function sorts the array in ascending order.

Java

In order to sort a static or dynamic array, use Arrays.sort(arr) or Collections.sort(list) respectively. The default sort function sorts the array in ascending order.

Warning!

The Arrays.sort() function uses quicksort on primitive data types such as longs. 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 Θ(N2)\Theta(N^2) 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 of long. This forces the Arrays.sort() function to use mergesort, which is always O(NlogN)O(N \log N).
  • Shuffle the array beforehand.

Python

In order to sort a list, simply use the sorted(list) function.

(Dynamic) Arrays of Pairs & Tuples

C++

By default, C++ pairs are sorted by first element and then second element in case of a tie.

1// Source: CPH
2
3#include <bits/stdc++.h>
4using namespace std;
5
6int main() {
7 vector<pair<int,int>> v;
8 v.push_back({1,5});
9 v.push_back({2,3});
10 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.

1list = [(1, 2), (2, 3), (2, 1), (3, 1)]
2list = sorted(list)
3for x, y in list:
4 print(f'{x}, {y}')
5
6# Output:
7# 1, 2
8# 2, 1
9# 2, 3
10# 3, 1

Problems

StatusSourceProblem NameDifficultyTagsSolution
CFEasyCheck CF

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

Module Progress:

Give Us Feedback on Introduction to Sorting!

PrevNext