# 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 $\mathcal{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.

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

Note: For "Why Did the Cow Cross the Road III", you need a custom comparator for Java. This is covered in Silver.

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

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

## Give Us Feedback on Introduction to Sorting!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.