Question

Use a random number function to store a list of 1000 pseudorandom integers values in an array. Apply QuickSort class. Display the output.

Answer 1

//Answer on Question#40177 - Programming - Java

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class QuickSort {

static final int AMOUNT = 1000;
static ArrayList<Integer> numbers;

public QuickSort() {
}

public static void main(String args[]) {
numbers = new ArrayList<Integer>();
Random rand = new Random();
for (int i = 0; i < AMOUNT; i++) {
numbers.add(rand.nextInt(AMOUNT + 1));
}
numbers = quicksort(numbers);
for (int i : numbers) {
System.out.println(i + " ");
}
}

static ArrayList<Integer> quicksort(ArrayList<Integer> input) {
if (input.size() <= 1) {
return input;
}

int middle = (int) Math.ceil((double) input.size() / 2);
int pivot = input.get(middle);

ArrayList<Integer> less = new ArrayList<>();
ArrayList<Integer> greater = new ArrayList<>();

for (int i = 0; i < input.size(); i++) {
if (input.get(i) <= pivot) {
if (i == middle) {
continue;
}
less.add(input.get(i));
} else {
greater.add(input.get(i));
}
}

return concatenate(quicksort(less), pivot, quicksort(greater));
}

static ArrayList<Integer> concatenate(List<Integer> less, int pivot, ArrayList<Integer> greater) {

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < less.size(); i++) {
list.add(less.get(i));
}
list.add(pivot);
for (int i = 0; i < greater.size(); i++) {
list.add(greater.get(i));
}
return list;
}
}