Go to main page
A journey into the programming realm
The point of no return
Leaping into the unknown
Chapter warning
This chapter will contain some algorithms that are usually learned in school.
It is great if you're able to follow the problem and the solution, but if not, do not discourage yourself!
Algorithms are great for exposing you to different problem-solving techniques. However, you will not use them in your everyday programming, and if you actually do need one, you can always look them up on the internet.
Therefore, it's a good idea to read this chapter, but if you are stuck or simply get bored, feel free to go directly to Chapter 3 and come back later on.
Binary search is an algorithm that works only on a sorted set of values, and drastically reduces searching time. It is implemented by selecting the middle element of the data set, and choosing on each iteration to keep only half of it, based on whether a condition was successful or not. The algorithm stops when the element was found or when the remaining set is empty.
The vector is sorted, so the values are in increasing order. If the value is bigger than what we have, we know the following:
Input Example:
Our value: 242
Current vector: [0,1000]
242 < 1000/2, so we select the left half of the vector
Our value: 242
Current vector: [0,500]
242 < 500/2, so we select the left half of the vector
Our value: 242
Current vector: [0,250]
242 > 250/2, so we select the right half of the vector
We can see that after only 3 steps we are left with 125 values and got rid of 875.
If the vector was not sorted, the values would have been randomly distributed, and we had no way of getting rid of half of data, since we had no information about it.
If the value that we need to search is close to one side (let’s say the value 3 for example) – linear search would have been way faster than binary search.
Binary search drastically improves performance when used on a big (sorted) collection of data.
Quicksort is a sorting algorithm which is based on the divide-and-conquer technique.
The algorithm picks an element (pivot) and partitions an array around the pivot. Therefore, the values smaller than the pivot will go to the left, whereas those bigger wil go to the right.
First, we choose a pivot. It can be the value of the middle element, the value of the last element, or any value in range of sorted values (even if it doesn’t exist in the array). Afterwards, we do the partitioning, which means rearranging the elements based on their value, in relation to the pivot value. The last step is to apply quicksort recursively to the left and right parts.
In the code, left and right are indices that initially point to the first and the last element in the array, respectively.
The algorithm moves left forward, until it finds an element which has a greater value than the pivot. The algorithm moves right backward, until it finds an element which has a smaller value than the pivot. If left is smaller than right, they are swapped, and they continue with the search (left is incremented, right is decremented).
The algorithm stops when left becomes greater than right.
After partitioning is done, all values before left are less or equal to pivot, and all values after right are greater or equal to pivot. When partitioning happens, the algorithm splits the array in two parts. Every element of left array is smaller than pivot, and every element of right array is bigger than pivot.
The following inequality is satisfied: Left <= pivot <= Right.
int partition(vector<int>& arr, int left, int right) {
int pivot = arr[(left + right) / 2];
while (left <= right) {
while (arr[left] < pivot) left++;
while (arr[right] > pivot) right--;
if (left <= right) {
swap(arr[left], arr[right]); // swaps the values
left++;
right--;
}
}
return left;
}
void quickSort(vector<int>& arr, int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
int main() {
vector<int> arr = { 1, 12, 5, 26, 7, 14, 3, 7, 2 };
quickSort(arr, 0, arr.size() - 1);
for (int i = 0; i < arr.size(); ++i)
cout << i << " ";
return 0;
}
The main() function is initially called, at line 23.
We fill a vector with random elements (Line 24) and call quicksort to sort them. The algorithm starts at line 14, where the function is declared.
Let’s have a look on the parameters sent: the vector we want to sort (through reference), 0 as left, and the size of the vector -1 as right value (the last element).
We assign size-1 because we want to use the indexes of the elements, and in C++ the arrays start with 0. So if we have 3 items, the indexes will be {0,1,2} => therefore left is set to 0, and right is set as 2. Right after the function is called, a partition is made (Line 15). That partition returns an index.
So how does this partitioning works ? (Line 1)
Line 2 declares a pivot, which is always the middle of our array. Until left reaches right (Line 3):
Line 6 is tricky, because we already checked that condition. But why do we check it again? Line 4 and 5 are checking the values and incrementing left and decrementing right, so we could be in the situation in which these two would have went over one another.
If that’s not yet the case, it means:
Because we want to have all items on the left smaller than pivot, at all times, and all items on the right bigger than pivot, at all times, we swap these two (Line 7) and go past those elements (Line 8-9).
We go back to line 3 and keep checking for any elements that are not placed properly.
So the partition is selecting the middle point of the array and sort all elements smaller than the value in the middle to the left, and all elements bigger than the value in the middle to the right.
Therefore, the index returned by the partition() function is the index from which we know for sure that all the items to the left of it are smaller than that index, and all items from the right of it are bigger than the index.
So, what are we gonna do with this index?
Line 17-18: If the value of left is smaller than the index-1, we call quicksort again, but this time the right will no longer be the end of the vector, but that index itself (-1).
Line 19-20: If the index is smaller than the value of right, we call quicksort again, but this time the left will longer be 0, but that index itself.
Strange.
But what actually happens is, we get a value which will be our index, and that will split our vector in two parts. Afterwards, we call the function again, each time with a smaller vector. There, we will get yet another index, and we will keep splitting our vector in two parts, until left reaches past index and right reaches past index too.
Merge-sort is a sorting algorithm which is based on the divide-and-conquer technique.
Merge sort is performed through three steps:
Let’s assume we have the following array of numbers:
{25, 4, 16, 32, 14, 17, 49, 7}
First step is to divide it into two parts
{25, 4, 16, 32}, {14, 17, 49, 7}
Now, Let’s split them again.
{25, 4}, {16, 32}, {14, 17}, {49, 7}
And again.
{25}, {4}, {16}, {32}, {14}, {17}, {49}, {7}
Now we merge them again (sorted)
{4, 25}, {16, 32}, {14, 17}, {7, 49}
And again
{4, 16, 25, 32}, {7, 14, 17, 49}
And one more time
{4, 7, 14, 16, 17, 25, 32, 49}
But that’s extra work!
No, it’s not, because merging is done in a smart way.
We have the arrays that we want to sort further, so we keep references to the front of these arrays, and always pick the smallest element out of them two, moving it to the sorted array, and incrementing the indices.
void merge(vector<int>& arr, int left, int median, int right) {
int idx_left_end = median - left + 1;
int idx_right_end = right - median;
vector<int> tmp_left, tmp_right;
for (int i = 0; i < idx_left_end; ++i) tmp_left.push_back(arr[left + i]);
for (int i = 0; i < idx_right_end; ++i) tmp_right.push_back(arr[median + 1 + i]);
int idx_left = 0, idx_right = 0;
int idx_merged = left;
while (idx_left < idx_left_end && idx_right < idx_right_end) {
if (tmp_left[idx_left] <= tmp_right[idx_right]) {
// merge element from left side, is lower than the one from right
arr[idx_merged] = tmp_left[idx_left];
idx_left++;
}
else {
// merge element from right side, is lower than the one from left
arr[idx_merged] = tmp_right[idx_right];
idx_right++;
}
idx_merged++;
}
// copy any remaining items, on each side, if one of them reached the limit
while (idx_left < idx_left_end) {
arr[idx_merged] = tmp_left[idx_left];
idx_left++;
idx_merged++;
}
while (idx_right < idx_right_end) {
arr[idx_merged] = tmp_right[idx_right];
idx_right++;
idx_merged++;
}
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int median = (left + right) / 2;
mergeSort(arr, left, median);
mergeSort(arr, median + 1, right);
merge(arr, left, median, right);
}
}
int main() {
vector<int> arr = { 25, 4, 16, 32, 14, 17, 49, 7 };
mergeSort(arr, 0, arr.size() - 1);
return 0;
}
The main() function is initially called, at line 51.
We fill a vector with random elements (Line 52) and call mergeSort() to sort them. The algorithm starts at line 40, where the function is declared.
Let’s have a look on the parameters sent: the vector we want to sort (through reference), 0 as left, and the size of the vector -1 as right value.
We assign size-1 because we want to use the indexes of the elements, and in C++ the arrays start with 0. So if we have 3 items, the indexes will be {0,1,2} => therefore left is set to 0, and right is set as 2.
Let’s see what the function does.
It receives the vector and the entire length of it, and compares left with right. (Line 41). Since left is 0 and right is the size of it, the condition is fulfilled and we move further. In line 42, we pick the middle of our vector, and then we do mergeSort twice:
Once for all the items from start to the middle of our initial vector (Line 44).
Once for all the items from the middle of our initial vector until the end (Line 45).
This is done recursively, so this logic will be applied continuously, splitting the vector in two until left is bigger or equal than right.
Therefore, if we start with an array of 8, we will call the same function for index 0-4 and 5-7. 0-4 will be split in two (0-1, 2-3), which will be again split in ({0}, {1}), and ({2}, {3}).
When the recursivity no longer applies, we return to the caller, and apply merge(), this time passing both the left, right, and the median as values (Line 47).
Merge implementation starts at line 1.
Line 2 and 3 introduce the end indexes for temporary arrays that will keep left and right values.
Assuming the vector was of size 8, the median will be 4 (mid of the array), and therefore, we will pass the function with the values (left =0 , median=4, right=7).
Idx_left_end (Line 2) will have the value “median-left + 1” = 3. This means we have 3 items on the left side.
Idx_right_end (Line 3) will have the value “right-median” = 7-4 = 3. This means we have 3 items on the right side.
Line 5-7 introduces two temporary arrays which copies the items from the left side on the left array, and from the right side, on the right array. Now it’s more clear why we have those indexes we discussed earlier, and why they both start from 0 – they are indexes for our temporary arrays.
Idx_left and idx_right (Line 9) are the current indexes for our temporary arrays.
Line 12 runs a loop until either left or right side finishes with iterating through their elements.
If the item from the left is smaller than the one from the right (Line 13), we add that one in our initial array (Line 15) and increment the index that points to the temporary left array (Line 16).
Otherwise (if the item from the right is smaller than the one from the left), we add that one instead (Line 20) and also increment the index that points to the temporary right array (Line 21).
Each time we add a value in our initial array, we increment its index so we can keep adding items. (Line 23).
Line 27-31, respectively 33-37, is there to copy any remaining items in our initial array.
That is because, for example, all the items from the left side were smaller than those from the right, so we added only those from the left. Now, we still need to add what is remaining (what’s on right side).
Vertex: Node containing data
Edge: The line that connects two vertices
Cycle: Cycles occur when nodes are connected in a way that they forms a closed structure.
Cycle: Cycles occur when nodes are connected in a way that they forms a closed structure.
Self loop: An edge that connects a vertex to itself (source = destination).
Divide et impera (Divide and conquer): Break the problem into sub-problems and solve them each recursively.
Negative weight edge refer to edges with a negative cost.