Sorting

Basic Algorithms

≈ 2 min read

Why sort data at all

Sorting puts elements into a chosen order: for example, from smaller to larger, by string length, or by some object field. Once that happens, the data becomes more predictable: neighboring values are related by order, equal elements are grouped, and many later algorithms become simpler.

But there are many ways to “sort.” Some algorithms are simple and useful for learning, others work well on large arrays, and some are advantageous only when the input has special properties. So the important goal is not to memorize one method, but to understand several different sorting ideas.

What this section covers

Sorting Basics. We will examine what an ordering means, how a comparison rule is defined, and which algorithm properties matter besides the final result.
Bubble Sort. We will see the simple idea of swapping neighboring elements and gradually pushing larger values to the right.
Selection Sort. We will repeatedly find the smallest element in the remaining part and place it into its correct position.
Insertion Sort. We will maintain an already sorted prefix and insert the next element into it.
Merge Sort. We will split the problem into parts, sort them, and carefully combine the results.
Quick Sort. We will introduce partitioning around a pivot and recursively process the resulting parts.
Counting Sort. We will use element values as counter indexes instead of comparing elements with each other.
Stable Sorting. We will see why the relative order of equal elements can sometimes matter.

Java already has sorting, but the algorithms still matter

int[] values = {7, 2, 5, 1};
Arrays.sort(values);

System.out.println(Arrays.toString(values)); // [1, 2, 5, 7]

Application code usually relies on library methods. In this section, we will implement the main algorithms ourselves so that you can see their mechanics, estimate their cost, and choose an appropriate idea for a particular problem.

Back Next