<commit_before>/*
    g++ quick.cpp -o quick
Reference:
    http://www.sorting-algorithms.com/quick-sort
*/
#include <stdio.h>
#include "util.h"

// quick (with 2 partitions)
// Note: The common implementation uses a left and right index (this doesn't)
// ========================================================================
void sort( const int N, int *data )
{
    if( N <= 1 )
        return;
printf( "N=%d\n", N );

    // leave pivot; use as-is data[0]
    // swap( data[0], rand(1,N));

    // move all data that is less then the pivot to the left side
    // we end up with 2 partitions
    //   [1..k-1] all data is <  pivot data[k]
    //   [k..n  ] all data is >= pivot data[k]
    int k = 0;
printf( "pivot = [%d]:%d\n", k, data[k] );

    for( int i = 1; i < N; i++ )
    {
printf( "i:%d  k: %d\n", i, k );
        if( data[i] < data[0] )
        {
            swap( data, ++k, i ); // inefficient if data[1] > data[pivot] --> swap with itself!<commit_msg>Document original bug missing recursive termination<commit_after>/*
    g++ quick.cpp -o quick
Reference:
    http://www.sorting-algorithms.com/quick-sort
*/
#include <stdio.h>
#include "util.h"

// quick (with 2 partitions)
// Note: The common implementation uses a left and right index (this doesn't)
// ========================================================================
void sort( const int N, int *data )
{
    if( N <= 1 ) // BUGFIX: original algorithm does not include recursion termination
        return;
printf( "N=%d\n", N );

    // leave pivot; use as-is data[0]
    // swap( data[0], rand(1,N));

    // move all data that is less then the pivot to the left side
    // we end up with 2 partitions
    //   [1..k-1] all data is <  pivot data[k]
    //   [k..n  ] all data is >= pivot data[k]
    int k = 0;
printf( "pivot = [%d]:%d\n", k, data[k] );

    for( int i = 1; i < N; i++ )
    {
printf( "i:%d  k: %d\n", i, k );
        if( data[i] < data[0] )
        {
            swap( data, ++k, i ); // inefficient if data[1] > data[pivot] --> swap with itself!
{'fraction_non_alphanumeric': 0.23256947830326669, 'fraction_numerical': 0.011701608971233545, 'mean_word_length': 2.472081218274112, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, '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': '1711120', 'n_tokens_mistral': 734, 'n_tokens_neox': 687, 'n_words': 242}