<jupyter_start><jupyter_text>Quicksort algorithmQuicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.The steps for in-place quicksort are the following:- If the range has less than two elements, return immediatly.- Otherwise pick a value, called a pivot, that occurs in the range. How you choose depends on the partition routine. In this notebook, we will always choose the last element (Lomuto partition scheme) - Partition the range: reorder its elements, while determining a point of division, so that all elements smaller than the pivot come before the division, while all elements greater than the pivot come after it.- Recursively apply the quicksort algorithm to the sub-range up to the point of division, and to the subrange after it.<jupyter_code>#include <cstdlib>
#include <iostream>
#include <vector>
using array_type = std::vector<double>;<jupyter_output><empty_output><jupyter_text>The next cell initializes the array that we will use for testing.<jupyter_code>array_type a(10u);
for (size_t i = 0; i < a.size(); ++i)
{
    a[i] = (rand() / (double)RAND_MAX);
}
a<jupyter_output><empty_output><jupyter_text>PartitionWrite a function `partition` that partitions an array. It should take the array, the lower bound and the upper bound as arguments, and should return the pivot index. You can then test your function by executing the next cells. What do you notice?<jupyter_code>size_t index = partition(a, 0u, a.size()-1);
std::cout << index << std::endl;
a<jupyter_output><empty_output><jupyter_text>QuicksortImplement the quicksort function, which divides the portion of an array into two partitions and sorts those. The function should take the array, the lower bound and the upper bound as arguments. Then test it in the next cell<jupyter_code>quicksort(a, 0, a.size() - 1);
a<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07176360225140713, 'fraction_numerical': 0.003283302063789869, 'mean_word_length': 5.424698795180723, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '635846', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 600, 'n_tokens_neox': 584, 'n_words': 284, 'path': 'courses/functional_stl/notebooks/quicksort.ipynb', 'repo_name': 'gouarin/MAP586', 'size': '2132'}