Question #40177

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

Expert's answer

//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;

}

}

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;

}

}

## Comments

## Leave a comment