Question

3, Modify the splitting process in quicksort: randomly select 3 Numbers, and then select the middle number of 3 Numbers as the grouping standard. What is the probability that the grouping effect is better than (a, 1-a)? (i.e. grouping is more even than (a, 1-a))

Answer 1

package com.hackerrank.arraysorting;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class QuickSort2_Sorting {

        public QuickSort2_Sorting() {
        }

        public List<Integer> partition(List<Integer> list) {

                int pivot = list.get(0);
                List<Integer> result;
                List<Integer> leftSide = new ArrayList<>();
                List<Integer> rightSide = new ArrayList<>();

                for (int i = 0; i < list.size(); i++) {
                        if (list.get(i) < pivot) {

                                leftSide.add(list.get(i));
                        } else if (list.get(i) > pivot) {
                                rightSide.add(list.get(i));
                        }

                }

                if (leftSide.size() > 1) {
                        result = this.partition(leftSide);
                        leftSide = result;
                }
                if (rightSide.size() > 1) {
                        result = this.partition(rightSide);
                        rightSide = result;
                }
                List<Integer> combined = new ArrayList<>();
                combined.addAll(leftSide);
                combined.add(pivot);
                combined.addAll(rightSide);
                // print out
                for (int j : combined) {
                        System.out.print(j + " ");
                }
                System.out.println();

                return combined;
        }

        public static void main(String[] a) {
                Scanner in = new Scanner(System.in);
                QuickSort2_Sorting qs = new QuickSort2_Sorting();
                List<Integer> list = new ArrayList<>();
                int n = in.nextInt();
                for (int i = 0; i < n; i++) {
                        list.add(in.nextInt());
                }
                List<Integer> sorted = qs.partition(list);
                sorted.size();
                in.close();
        }
}