Sorting and Searching

Problem: Given an array that contains $n$ elements, sort the elements in increasing order. This is the sorting problem.

Bubble Sort

A simple algorithm that works in $O(n^2)$ time. The algorithm consists of $n$ rounds, and on each round, it iterates through the elements of the array. Whenever two consecutive elements are found in wrong order, the algorithm swaps them. This is written in the following codes:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - 1; j++) {
        if (array[j] > array[j + 1]) {
            swap(array[j], array[j + 1]);
        }
    }
} ```

After the first round of the bubble sort, the largest element will be in the correct position, and after $k$ rounds, the $k$ largest elements will be in the correct positions.

### Inversions
Inversion is a useful concept when analyzing sorting algorithms. Given a pair of indices $(a,b)$, we say that there is an inversion if $a < b$ and `array[a] > array[b]`. This indicates how much work is needed to sort the array. 
**Important**: An array is completely sorted when there are no inversions.

## Merge Sort
This type of sorting is based on recursion. It works in $O(n\log n)$ time. Merging `array[a...b]` gives the following steps for the merge sort:
1. If *a = b*, do not do anything, because a subarray that only contains one element is already sorted.  
2. Calculate the position of the middle element: *k = ⌊(a + b)/2⌋*.  
3. Recursively sort the subarray `array[a ... k]`.  
4. Recursively sort the subarray `array[k + 1 ... b]`.  
5. *Merge* the sorted subarrays `array[a ... k]` and `array[k + 1 ... b]` into a sorted subarray `array[a ... b]`.
In the last step, merging the sorted subarrays is possible in linear time. 

## Sorting Lower Bound
Any comparison-based sorting algorithm must make at least  $\Omega(n \log n)$ comparisons in the worst case. This means that any sorting algorithm that compares each element has the worst-case running complexity of  $O(n\log n)$. 

## Counting Sort
The lower bound $\Omega (n \log n)$ does not apply to algorithms that do not compare array elements but use some other information. An example of such an algorithm is counting sort that sorts an array in $O(n)$. 

Counting Sort uses a **bookkeeping array** where the **indices** represent values from the original array. The algorithm works as follows:

- It iterates through the input array and **counts how many times** each element appears.
- These counts are stored in the bookkeeping array.

> ⚠️ **Note:** Counting sort is efficient only when the range of input values is small enough so that array elements can be directly used as indices.

## Sorting in Practice
In practice, it is almost never a good idea to implement a home-made sorting algorithm, because all modern programming languages have good sorting algorithms in their standard libraries.

In C++, we use the function `sort`. 
```cpp
vector<int> v = {4,2,5,3,5,8,3};
sort(v.begin(), v.end());

// If we want reverse, we have
sort(v.rbegin(), v.rend());

An ordinary array can be sorted as follows:

int n = 7; // array size
int a[] = {4,2,5,3,5,8,3};
sort(a,a+n);

If a string is given,

string s = "monkey";
sort(s.begin(), s.end());

Pairs are sorted primarily according to their first elements and secondarily according to their second elements:

vector<pair<int,int>> v;
v.push_back({1,5});
v.push_back({2,3});
v.push_back({1,2});
sort(v.begin(), v.end());
// result: [(1,2),(1,5),(2,3)]

This is similar to tuples.

vector<tuple<int,int,int>> v;
v.push_back({2,1,4});
v.push_back({1,5,3});
v.push_back({2,1,3});
sort(v.begin(), v.end());
// result: [(1,5,3),(2,1,3),(2,1,4)]

Comparing strings first by length and secondly by alphabetical order.

bool comp(string a, string b) {
if (a.size() == b.size()) return a < b;
else return a.size() < b.size();
}

// After this, we can now implement in a way like this:
sort(v.begin(), v.end(), comp);

Solving Problems by Sorting

A goal in algorithm design is to find $O(n)$ or $O(n \log n)$ time algorithms for problems that can be trivially solved in $O(n^2)$.

Suppose that we want to check if all elements in an array are unique. We can solve this problem in $O(n\log n)$ time by first sorting the array. If there are equal elements, they are next to each other in the sorted array.

bool ok = true;
sort(array, array+n);
for (int i = 0; i < n-1; i++) {
	if (array[i] == array[i+1]) ok = false;
}

Several other problems can be solved in a similar way in $O(n \log n) time$, such as counting the number of distinct elements, finding the most frequent element, and finding two elements whose difference is minimum.

Sweep Line Algorithms

Suppose that there is a restaurant and we know the arriving and leaving times of all customers on a certain day. Our task is to find out the maximum number of customers who visited the restaurant at the same time.

Note. Solution To solve the problem, we create two events for each customer: one event for arrival and another event for leaving. Then, we sort the events and go through them according to their times. To find the maximum number of customers, we maintain a counter whose value increases when a customer arrives and decreases when a customer leaves. The largest value of the counter is the answer to the problem.

Scheduling Events

Given $n$ events with their starting and ending times, your goal is to select as many non-overlapping events as possible — this is called the interval scheduling maximization problem.

Note. Solution Sort the events according to their ending times and always select the next possible event that ends as early as possible. At each step, pick the earliest finishing event that doesn't overlap with the previous one. This algorithm always produces an optimal solution.

Picking the earliest-ending event frees up time for scheduling more events later. You maximize the remaining time for future decisions.

Tasks and Deadlines

Consider a problem where we are given n tasks with durations and deadlines and our task is to choose an order to perform the tasks. For each task, we earn $d − x$ points where d is the task’s deadline and x is the moment when we finish the task. What is the largest possible total score we can obtain?

Note. Solution Sort tasks by increasing duration and schedule them in that order.

Binary Search

Binary search is a highly efficient algorithm used to find the position of a target value within a sorted array or list. It works by repeatedly dividing the search interval in half.

The search can be implemented as follows:

int a = 0, b = n-1;
while (a <= b) {
	int k = (a+b)/2;
	if (array[k] == x) {
		// x found at index k
	}
	if (array[k] < x) a = k+1;
	else b = k-1;
}

Finding Optimal Solution

Suppose that we are solving a problem and have a function valid(x) that returns true if x is a valid solution and false otherwise. In addition, we know that valid(x) is false when x < k and true when x ≥ k. In this situation, we can use binary search to efficiently find the value of k.

The idea is to binary search for the largest value of x for which valid(x) is false. Thus, the next value k = x + 1 is the smallest possible value for which valid(k) is true. The search can be implemented as follows:

int x = -1;
for (int b = z; b >= 1; b /= 2) {
	while (!valid(x+b)) x += b;
}
int k = x+1;