// ---
// jupyter:
//   jupytext:
//     text_representation:
//       extension: .cpp
//       format_name: light
//       format_version: '1.5'
//       jupytext_version: 1.14.4
//   kernelspec:
//     display_name: C++14
//     language: C++14
//     name: xcpp14
// ---

// + [markdown] tags=[]
// # Quicksort algorithm
//
// Quicksort 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.  
// -

#include <cstdlib>
#include <iostream>
#include <vector>
using array_type = std::vector<double>;

// The next cell initializes the array that we will use for testing.

array_type a(10u);
for (size_t i = 0; i < a.size(); ++i)
{
    a[i] = (rand() / (double)RAND_MAX);
}
a

// + [markdown] tags=[]
// ## Partition
//
// Write 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.
// -

size_t partition(array_type& a, size_t low, size_t high)
{
    double pivot = a[high];
    size_t index = low - 1;
    
    for (size_t i = low; i < high; ++i)
    {
        if (a[i] <= pivot)
        {
            ++index;
            std::swap(a[i], a[index]);
        }
    }
    ++index;
    std::swap(a[index], a[high]);
    return index;
}

// You can then test your function by executing the next cell. What do you notice?

size_t index = partition(a, 0u, a.size()-1);
std::cout << index << std::endl;
a

// ## Quicksort
//
// Implement 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.

void quicksort(array_type& a, size_t low, size_t high)
{
    if (low >= high)
        return;
    
    size_t p = partition(a, low, high);
    quicksort(a, low, p-1);
    quicksort(a, p+1, high);
}

// Then test it in the next cell

quicksort(a, 0, a.size() - 1);
a

// Having to pass the lower and upper bounds is required by the implementation, but not very convenient for the user. How can you improve the API?

StarcoderdataJupyterScriptsDedupFiltered