Introduction to Sorting

C++

Java

Python

C++

To sort static arrays, use sort(arr, arr + N) where $N$ 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)$.

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

Java

In order to sort a static array, use Arrays.sort(arr).

import java.util.*;

class Main
{
	public static void main (String[] args)
	{
		int arr[] = {5, 1, 3, 2, 4};
		Arrays.sort(arr);
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i] + " "); //1 2 3 4 5
	}
}

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.

C++

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.end() + 1) sorts indices $[1, 4)$.

#include <bits/stdc++.h>
using namespace std;

int main() {
	vector<int> v{5, 1, 3, 2, 4};
	sort(v.begin(), v.end());
	for (int i : v)
		cout << i << " "; //1 2 3 4 5
	cout << endl;

	v = {5, 1, 3, 2, 4};
	sort(v.begin() + 1, v.begin() + 4);
	for (int i : v)
		cout << i << " "; //5 1 2 3 4
}

Java

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

import java.util.*;

class Main
{
	public static void main (String[] args)
	{
		ArrayList<Integer> arr = new ArrayList<Integer>();
		arr.add(5); arr.add(1); arr.add(3); arr.add(2); arr.add(4);
		Collections.sort(arr);
		for (int i : arr)
			System.out.print(i + " "); //1 2 3 4 5
	}
}

Python

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

• Sorting Basics

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