<commit_before>from __future__ import print_function
from __future__ import division


def _select_pivot_value(a_list, first, last):
    """Select pivot value by median of three."""
    first_value = a_list[first]
    last_value = a_list[last]
    middle = (first + last) // 2
    middle_value = a_list[middle]
    if ((first_value < middle_value < last_value) or 
        (last_value < middle_value < first_value)):
        return middle
    elif ((middle_value < first_value < last_value) or
          (last_value < first_value < middle_value)):
        return first
    else:
        return last


def _partition(a_list, first, last):
    """Get split point for patition."""
    # pivot_pos = _select_pivot_value(a_list, first, last)
    # pivot_value = a_list[pivot_pos]
    pivot_value = a_list[first]
    
    left_mark = first + 1
    right_mark = last

    done_bool = False
    while not done_bool:
        while (left_mark <= right_mark and 
               a_list[left_mark] <= pivot_value):
            left_mark += 1

        while (a_list[right_mark] >= pivot_value and 
               right_mark >= left_mark):
            right_mark -= 1

        if right_mark < left_mark:
            done_bool = True
        else:
            temp = a_list[left_mark]
            a_list[left_mark] = a_list[right_mark]
            a_list[right_mark] = temp
            print(a_list)

    # temp = a_list[pivot_pos]
    # a_list[pivot_pos] = a_list[right_mark]
    temp = a_list[first]
    a_list[first] = a_list[right_mark]
    a_list[right_mark] = temp
    print(a_list)

    return right_mark


def _recur_quick_sort(a_list, first, last):
    if first < last:
        split_point = _partition(a_list, first, last)
        _recur_quick_sort(a_list, first, split_point - 1)
        _recur_quick_sort(a_list, split_point + 1, last)


def quick_sort(a_list):
    """Quick sort algortihm."""
    _recur_quick_sort(a_list, 0, len(a_list) - 1)


def main():
    a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('a_list: \n{}'.format(a_list))
    print('By quick sort: ')
    quick_sort(a_list)


if __name__ == '__main__':
    main()<commit_msg>Add quick_sort_recur by list comprehension technique<commit_after>from __future__ import print_function
from __future__ import division


def _select_pivot_value(a_list, first, last):
    """Select pivot value by median of three."""
    first_value = a_list[first]
    last_value = a_list[last]
    middle = (first + last) // 2
    middle_value = a_list[middle]
    if ((first_value < middle_value < last_value) or 
        (last_value < middle_value < first_value)):
        return middle
    elif ((middle_value < first_value < last_value) or
          (last_value < first_value < middle_value)):
        return first
    else:
        return last


def _partition(a_list, first, last):
    """Get split point for patition."""
    # pivot_pos = _select_pivot_value(a_list, first, last)
    # pivot_value = a_list[pivot_pos]
    pivot_value = a_list[first]
    
    left_mark = first + 1
    right_mark = last

    done_bool = False
    while not done_bool:
        while (left_mark <= right_mark and 
               a_list[left_mark] <= pivot_value):
            left_mark += 1

        while (a_list[right_mark] >= pivot_value and 
               right_mark >= left_mark):
            right_mark -= 1

        if right_mark < left_mark:
            done_bool = True
        else:
            temp = a_list[left_mark]
            a_list[left_mark] = a_list[right_mark]
            a_list[right_mark] = temp
            print(a_list)

    # temp = a_list[pivot_pos]
    # a_list[pivot_pos] = a_list[right_mark]
    temp = a_list[first]
    a_list[first] = a_list[right_mark]
    a_list[right_mark] = temp
    print(a_list)

    return right_mark


def _recur_quick_sort(a_list, first, last):
    if first < last:
        split_point = _partition(a_list, first, last)
        _recur_quick_sort(a_list, first, split_point - 1)
        _recur_quick_sort(a_list, split_point + 1, last)


def quick_sort(a_list):
    """Quick sort algortihm."""
    _recur_quick_sort(a_list, 0, len(a_list) - 1)


def quick_sort_recur(a_list):
    if len(a_list) <= 1:
        return a_list
    pivot_value = a_list[len(a_list) // 2]
    left_list = [x for x in a_list if x < pivot_value]
    middle_list = [x for x in a_list if x == pivot_value]
    right_list = [x for x in a_list if x > pivot_value]
    return quick_sort_recur(left_list) + middle_list + quick_sort_recur(right_list)


def main():
    a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('a_list: \n{}'.format(a_list))
    print('By quick sort: ')
    quick_sort(a_list)

    a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('a_list: \n{}'.format(a_list))
    print('By quick sort: ')
    quick_sort_recur(a_list)


if __name__ == '__main__':
    main()
{'fraction_non_alphanumeric': 0.10473251028806585, 'fraction_numerical': 0.014814814814814815, 'mean_word_length': 2.707856598016781, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4072213', 'n_tokens_mistral': 1802, 'n_tokens_neox': 1688, 'n_words': 403}