<commit_before>#ifndef QUICKSORT_HPP_
#define QUICKSORT_HPP_

// Quick Sort Algorithm
// Efficient, general-purpose, comparison-based sorting algorithm.
// https://en.wikipedia.org/wiki/Quicksort
// Best case performance: O(n log n) typical, O(n) natural variant
// Worst case performance: O(n^2)
// Worst Case Auxiliary Space Complexity: О(n)

#include <limits>

namespace QS {

template<typename T>
class Solution {
public:
    static void QuickSort(T& container) {
        if (container.size() < 2) {
            return;
        }

        Sort(container, 0, container.size() - 1);
    }
private:
    static void Sort(T& container, const size_t& start, const size_t& end) {
        if(start >= end) {
            return;
        }

        // As pivot element choose middle element
        size_t pivotIndex = start + (end - start)/ 2;
        auto pivotValue = container[pivotIndex];

        size_t left = start, right = end;
        do {
            // Find element on the LEFT part of the container that is
            // GREATER OR EQUAL than pivot element
            while(container[left] < pivotValue) {
                ++left;
            }

            // Find element on the RIGHT part of the container that is
            // LESS OR EQUAL than pivot element
            while(pivotValue < container[right]) {
                --right;
            }

            if (left <= right) {
                // Swap such elements so they will be in right parts of the
                // container
                std::swap(container[left], container[right]);
                if (left < std::numeric_limits<size_t>::max()) {
                    ++left;
                }

                if (std::numeric_limits<size_t>::min() < right) {
                    --right;
                }
            }
        }
        while(left <= right);

        Sort(container, start, right);
        Sort(container, left, end);
    }
};

}

#endif /* QUICKSORT_HPP_ */<commit_msg>Rewrite quicksort<commit_after>#ifndef QUICKSORT_HPP_
#define QUICKSORT_HPP_

// Quick Sort Algorithm
// Efficient general-purpose in-place comparison-based sorting algorithm.
// https://en.wikipedia.org/wiki/Quicksort
// Best case performance: O(n log n) typical, O(n) natural variant
// Worst case performance: O(n^2)
// Space Complexity: О(1)

#include <limits>

namespace QS {

template<typename T>
class Solution {
public:
    static void QuickSort(T& container) {
        if (container.size() < 2) {
            return;
        }

        Sort(container, 0, container.size() - 1);
    }
private:
    static void Sort(T& container, const size_t& start, const size_t& end) {
        if(start >= end) {
            return;
        }

        size_t pivotFinalIndex = Partition(container, start, end);
        if (pivotFinalIndex > 0) {
            Sort(container, start, pivotFinalIndex - 1);
        }

        Sort(container, pivotFinalIndex + 1, end);
    }

    static size_t Partition(T& container,
                            const size_t& start, const size_t& end) {
        // Choose pivot element as middle element of container. Swap it
        // with the first element.
        size_t pivotIndex = start + (end - start)/ 2;
        std::swap(container[pivotIndex], container[start]);

        auto pivotValue = container[start];

        // Let's iterate over container and compare elements with pivot.
        // Our goal - is to rearrange elements in container so they would
        // form two parts: first (left) part will contain only elements that
        // are less than pivot; second (right) part will contain all other
        // elements.
        // We could start iteration with element that stands after pivot.
        // We will use two indexes:
        // 'left' - end of the partition with elements less than pivot
        // 'i' - iterator over container elements
        size_t left = start + 1;
        for(size_t i = start + 1; i <= end; ++i)
        {
            // All elements that are less than pivot put to the left partition
            if (container[i] < pivotValue) {
                std::swap(container[i], container[left]);
                ++left;
            }
        }

        // Put pivot element to its final position - last element of partition
        // that contains only elements that are less than pivot
        std::swap(container[start], container[left - 1]);

        // Return final position of pivot element
        return left - 1;
    }
};

}

#endif /* QUICKSORT_HPP_ */
{'fraction_non_alphanumeric': 0.10230803373280072, 'fraction_numerical': 0.0039946737683089215, 'mean_word_length': 1.907741935483871, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 12, 'https://': 2, '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}}
{'dir': 'git-commits-cleaned', 'id': '3382081', 'n_tokens_mistral': 1303, 'n_tokens_neox': 1209, 'n_words': 419}