<commit_before>package com.jwetherell.algorithms.sorts;

import java.util.Random;

/**
 * Quicksort is a sorting algorithm which, on average, makes O(n*log n) comparisons to sort
 * n items. In the worst case, it makes O(n^2) comparisons, though this behavior is
 * rare. Quicksort is often faster in practice than other algorithms. 
 * 
 * Family: Divide and conquer. 
 * Space: In-place. 
 * Stable: False.
 * 
 * Average case = O(n) Worst case = O(n^2) Best case = O(n*log n)
 * 
 * http://en.wikipedia.org/wiki/Quick_sort
 * 
 * @author <NAME> <<EMAIL>>
 */
public class QuickSort<T extends Comparable<T>> {

    private static final Random RANDOM = new Random();

    public static enum PIVOT_TYPE {
        FIRST, MIDDLE, RANDOM
    };

    public static PIVOT_TYPE type = PIVOT_TYPE.RANDOM;

    private QuickSort() { }

    public static <T extends Comparable<T>> T[] sort(PIVOT_TYPE type, T[] unsorted) {
        int pivot = 0;
        if (type == PIVOT_TYPE.MIDDLE) {
            pivot = unsorted.length/2;
        } else if (type == PIVOT_TYPE.RANDOM) {
            pivot = getRandom(unsorted.length);  
        }
        sort(pivot, 0, unsorted.length - 1, unsorted);
        return unsorted;
    }

    private static <T extends Comparable<T>> void sort(int pivotIndex, int start, int finish, T[] unsorted) {
        pivotIndex = start + pivotIndex;<commit_msg>Fixed incorrect comment in QuickSort.java<commit_after>package com.jwetherell.algorithms.sorts;

import java.util.Random;

/**
 * Quicksort is a sorting algorithm which, on average, makes O(n*log n) comparisons to sort
 * n items. In the worst case, it makes O(n^2) comparisons, though this behavior is
 * rare. Quicksort is often faster in practice than other algorithms. 
 * 
 * Family: Divide and conquer. 
 * Space: In-place. 
 * Stable: False.
 * 
 * Average case = O(n*log n), Worst case = O(n^2), Best case = O(n) [three-way partition and equal keys]
 * 
 * http://en.wikipedia.org/wiki/Quick_sort
 * 
 * @author <NAME> <<EMAIL>>
 */
public class QuickSort<T extends Comparable<T>> {

    private static final Random RANDOM = new Random();

    public static enum PIVOT_TYPE {
        FIRST, MIDDLE, RANDOM
    };

    public static PIVOT_TYPE type = PIVOT_TYPE.RANDOM;

    private QuickSort() { }

    public static <T extends Comparable<T>> T[] sort(PIVOT_TYPE type, T[] unsorted) {
        int pivot = 0;
        if (type == PIVOT_TYPE.MIDDLE) {
            pivot = unsorted.length/2;
        } else if (type == PIVOT_TYPE.RANDOM) {
            pivot = getRandom(unsorted.length);  
        }
        sort(pivot, 0, unsorted.length - 1, unsorted);
        return unsorted;
    }

    private static <T extends Comparable<T>> void sort(int pivotIndex, int start, int finish, T[] unsorted) {
        pivotIndex = start + pivotIndex;
{'fraction_non_alphanumeric': 0.11296625222024867, 'fraction_numerical': 0.004262877442273535, 'mean_word_length': 2.889502762430939, 'pattern_counts': {'":': 0, '<': 21, '<?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}}
{'dir': 'git-commits-cleaned', 'id': '1685986', 'n_tokens_mistral': 961, 'n_tokens_neox': 899, 'n_words': 284}