### You're not signed in!

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

# Introduction to Sorting

Authors: Darren Yao, Benjamin Qi, Allen Li

### Prerequisites

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 | |||
---|---|---|---|

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

tutorialspointCovers sorting arraysPython

Resources | |||
---|---|---|---|

PY | reference |

### (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 $N$ 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 `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 $\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(N \log N)$. - Shuffle the array beforehand.

### (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: CPH23#include <bits/stdc++.h>4using namespace std;56int 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}')56# Output:7# 1, 28# 2, 19# 2, 310# 3, 1

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

CF | Easy | Check CF |

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