# Sorting & Searching

Here are some resources to learn about sorting and binary search:

- Chapter 10 of
*Cracking the Coding Interview* - Binary search (KhanAcademy) (Algolist)
- Merge Sort
- Quicksort
- Selection sort
- Insertion sort
- Heap tutorial

# Examples

Try to do each example by yourself first.

### RGB

(From CareerCup)

Given a character array as input containing only `'R'`

, `'G'`

and `'B'`

in random order, write an algorithm that sorts the array such that `'R'`

comes before `'G'`

before `'B'`

.

Do it in linear time. Try to traverse the array only once and use constant additional space.

**Solution 1**

We can solve this problem using counting sort. We count the number of R, G and B in one pass. Then we go through the array again and place that many R, G and B's in order. This solution is good, but requires two passes through the array. We can solve this problem via one pass through the array. *Hint*: How would you solve this problem in one pass if there were only two letters? Try to generalize to three.

**Solution 2**

We partition the array into three parts, the R, G and B part. We have two pointers, `p`

and `q`

, that point to the end of the R part, and the beginning of the B part, respectively. The algorithm works similar to insertion sort where every time we see `'R'`

we append it to the R part and every time we see `'B'`

prepend it to the B part.

We traverse the array:

- If we see
`'R'`

, swap it with the character at`p`

and increment`p`

. - If we see
`'B'`

, swap it with the character at`q`

and decrement`q`

.

Whenever we swap an `'R'`

or `'B'`

character to the correct place, we are potentially swapping a `'G'`

character to replace it in the center. At the end of the traversal, all the characters should be in the right place.

### Sqrt

(From LeetCode)

Implement `int sqrt(int x)`

.

Compute and return the square root of x.

If x is not a perfect square, return `floor(sqrt(x))`

Example :

```
Input : 11
Output : 3
```

DO NOT USE SQRT FUNCTION FROM STANDARD LIBRARY

**Hint**

We can do a for loop from to and find the first number for which and but that would be too slow if is, for example, a billion.

Because we know that is always increasing, we can think of the range as the indices of a sorted array where . We are looking for the index for which but . What does this sound like?

**Solution**

Binary search! Check out this pseudocode:

```
left = 1
right = x
while left <= right
mid = (left + right) / 2
if mid <= x / mid
left = mid + 1
// result is the last number for which result^2 <= x
result = mid
else
right = mid - 1
return result
```

Note that we can use the statement `mid * mid <= x`

but it may overflow integer so we write `mid <= x / mid`

instead which is the same thing.

will contain the correct answer because it is the last for which . If we don't enter that if statement again, it means that . At that point, every midpoint will be greater than and will keep decreasing until it crosses .

The time complexity of this algorithm is where is the input to our program. Our search range starts at but every iteration cuts this range in half. We can only cut this range times before our endpoints meet at some integer. At that point the range cannot become any smaller.

### Merge K Sorted Arrays

(From GeeksForGeeks)

Given sorted arrays of size each, merge them and print the sorted output.

Example:

Input:

```
k = 3, n = 4
arr[][] = { {1, 3, 5, 7},
{2, 4, 6, 8},
{0, 9, 10, 11}} ;
Output: 0 1 2 3 4 5 6 7 8 9 10 11
```

Can you do it in better than time?

**Hint**

How do you merge two sorted arrays in linear time? How can you generalize that to k sorted arrays?

**Solution**

The solution to this problem is explained here.

**Similar Example**