## What is Sorting?

Sorting is the process of which a group of data is ordered in a specific way. There are many ways to sort data, one of the most common ways to do this (with numbers) is to sort in ascending order. For example `{1, 9, 2, 5}` would sort to `{1, 2, 5, 9}`. Arrays, being a collection of data, are very commonly the subject of sorting in Java.

## Algorithm

There are many algorithms that allow you to sort an array. One of the simplest sorting algorithms is bubble sort, which sorts by repeatedly swapping adjacent elements in the array. For every pair of elements in the array, if the first element is larger than the second, swap them. The product of this swapping is that after `x` iterations, the last `x` elements will be guaranteed to be sorted. If you think about it logically, it is easy to see why this is the case.

Consider the case of the following array: `8 1 3 7`.

Lets run through what bubble sort would do:

1. Swap the first pair elements (8 > 1). Array now looks like `1 8 7 3`
2. Swap the second pair of elements (8 > 7). Array now looks like `1 7 8 3`
3. Swap the third pair of elements (8 > 3). Array now looks like `1 7 3 8`

Now you can see how the number 8 rose to the top, and now the last element is guaranteed to be in the correct place.

If we continue sorting this way for 3 more iterations, it is guaranteed that the entire array will be sorted.

If you would like to see a full visual representation of how this sorting algorithm works, VisuAlgo has a great visualization of the bubble sort algorithm.

### Implementing Bubble Sort

Bubble sort is an algorithm that is both easy to explain and implement. First, lets start by writing our loops:

``````int[] arr = {1, 5, 3, 7, 9, 10, 4, 1};
// loop through each element in the array
// this makes sure that our sorting algorithm sorts the entire array.
for (int i = 0; i < arr.length; i++) {
// now, loop through every pair, excluding the elements that are already guaranteed to be sorted.
// prevent array out of bounds since the last element doesn't have a pair in front of it. (this is why you subtract one)
for (int j = 0; j < arr.length - i - 1; j++) {
// implement the algorithm
}
}
``````

Next we can check which element is larger using a simple if statement:

``````if (arr[j] > arr[j + 1]) {
// swap here
}
``````

Now we have to implement swapping elements. Swapping elements of an array in Java requires that you declare two variables. If you don’t declare two variables, you will no longer have access to the other element since you’ve just changed it.

### ⚠️ How not to Swap.

For example, if you were to swap two adjacent elements like this:

``````// do NOT do this!
arr[i] = arr[j];
arr[j] = arr[i];
``````

The original `arr[i]` would be overwritten by `arr[j]`.

### ✅ How to Swap Correctly

Thus our swapping code must look like:

``````int a = arr[j], b = arr[j + 1];
arr[j] = b;
arr[j + 1] = a;
``````

Our final code would then look like:

``````int[] arr = {1, 5, 3, 7, 9, 10, 4, 1};
// loop through each element in the array
// this makes sure that our sorting algorithm sorts the entire array.
for (int i = 0; i < arr.length; i++) {
// now, loop through every pair, excluding the elements that are already guaranteed to be sorted.
// prevent array out of bounds since the last element doesn't have a element in front of it. (this is why you subtract one)
for (int j = 0; j < arr.length - i - 1; j++) {
// check if the pair is out of order
if (arr[j] > arr[j + 1]) {
// swap elements.
int a = arr[j], b = arr[j + 1];
arr[j] = b;
arr[j + 1] = a;
}
}
}
``````

## Pros and Cons of Bubble Sort

### Pros

• Very easy to implement.
• Useful when you want to sort for only the top X numbers

### Cons

• Takes a significant amount of time on larger datasets.
• Will continue to run even if the entire array is already sorted.

### Verdict

Although bubble sort can be useful when sorting arrays, it can almost always be replaced by a more efficient algorithm like merge sort or tim sort.

Even if you have small datasets, its useful to use a faster sorting algorithm either way. After all, many small operations can lead to a significant slow down at any kind of scale.

I therefore recommend that you do not use bubble sort in your code, rather you should use Java’s built-in sort function instead (see below).

## Time Complexity (for advanced readers)

Time complexity in computer science is represented by Big-O notation. The fundamental idea behind Big-O notation is “how fast does this rise?”

In other words, Big-O doesn’t bother with how many operations you do per loop, rather it counts how your algorithm scales with larger and larger datasets 1.

Most of time, we use one of the following to describe an algorithm:

`O(1)`: Constant time. No matter how large the dataset is, the algorithm runs the same number of operations (think of this like a horizontal line on a graph).

`O(log n)`: Logarithmic time. If the dataset size is `x`, the number of operations is `y`, where `2^y = x`2.

`O(n)`: Linear time. The number of operations directly correlates to the size of the dataset (think of this as an equation in `y = mx + b` form).

`O(n^2)`: Quadratic time. The number of operations correlates with the dataset size multiplied by itself (think of this as an equation in `ax^2 + bx + c` form).

Given the above, can you guess what the time complexity of bubble sort is? (Hover over the space below to see the answer.)

O(n^2). The giveaway is that there is an embedded for loop. For every element of the array, we are going through every other element of the array. Even if we don’t loop through the array completely every time, it is still O(n^2) since Big-O doesn’t care about linear improvements when your algorithm runs in non-linear time

`O(n^2)` is generally considered slow for an algorithm, because it rises so steeply. As a point of comparison, here is the difference between linear and quadratic time:

Dataset Size O(N) time O(N^2) Time
1 1 1
2 2 4
3 3 9
4 4 16
1000 1000 1000000

## Easier Sorting

You don’t need to implement a sorting algorithm every time you want to sort something. Java already has a built-in sorting function: `Arrays.sort()`. `Arrays.sort()` allows you to sort an array, by default for primitive types3 (other than boolean) in ascending order by value. For objects that implement `Compareable`, it calls the `compareTo(Comparable b)` method4.

``````Integer[] arr = {0, 6, 1, 2, 5};
Arrays.sort(arr);
// arr is now 0, 1, 2, 5, 6
``````

## Searching

Searching is a very simple concept: find the index of a specific element in an array. For example, searching for `3` in the array `4, 1, 6, 1, 3, 2` would result in the index `4`.

The most common searching algorithm is simply looping through every element in the array until the wanted element shows up (or the array ends). The implementation of this algorithm looks like this:

``````private int search(int needle, int[] haystack) {
// loop through every element in the array.
for (int i = 0; i < haystack.length; i++) {
// if the element is what we are searching for, return the index.
if (haystack[i] == needle) {
return i;
}
}
// if the element doesn't exist, return -1 to indicate that it could not be found.
return -1;
}
``````

## Next Steps

After learning about array algorithms, you should try solving some of the following problems on the DMOJ Modern Online Judge:

List Minimum

Bubble Sort

Please note that these problems require basic knowledge of reading input, which you can find a brief introduction of here

Please note that you should never prompt (i.e. ask the user to “enter x”) for input on the DMOJ Modern Online Judge.

## Footnotes

1. It is significantly more complex then this, if you would like to learn more about Big-O notation, here is a much more in-depth explanation.

2. Big-O notation doesn’t actually care about which base your logarithm is, however in programming, the base is usually 2.

3. For very large sets of data, it is recommended that you use the class versions (e.g. `Integer`) of primitives since by default for primitives, Java uses a slower QuickSort algorithm rather than the TimSort algorithm used for objects.

4. The `compareTo(comparable b)` method returns a positive integer if the element is greater than b, `0` if they are the same and a positive integer if the element is less than the other integer.