(java) Hello! I am trying to write a program that among other things sorts an Ar
ID: 3669853 • Letter: #
Question
(java)
Hello!
I am trying to write a program that among other things sorts an ArrayList using quick sort, I have tried many different things but right now I am getting a null pointer exception. Any suggestions would be appreciated.
Thank you, here is the code
import java.util.*;
public class BuiltIn {
private static final int[] ArrayS = null;
public static void main(String[] args) {
Random r = new Random();
ArrayList<Object> Array = new ArrayList<>(10);
System.out.println("Array:");
for (int i = 0; i < 10; i++) {
int ran = r.nextInt(1000);
Array.add(ran);
System.out.println(Array.get(i));
}
int right;
int left;
for (int i = 0; i < 10; i++) {
ArrayS = new int[Array.size()];
ArrayS[i] = (int) Array.get(i);
System.out.println(ArrayS[i]);
}
ArrayS = sort(ArrayS, Array, left, right);
System.out.println("Sorted Array:");
for (int i = 0; i < 10; i++) {
System.out.println(ArrayS[i]);
}
Stack Stack = new Stack<>();
Queue Queue = new LinkedList<>();
System.out.println("Queue:");
for (int i = 0; i < 10; i++) {
Queue.add(Array.get(i));
System.out.println(Queue.remove());
}
System.out.println("Stack:");
for (int i = 0; i < 10; i++) {
Stack.add(Array.get(i));
}
for (int i = 0; i < 10; i++) {
System.out.println(Stack.pop());
}
}
private static int sort(int ArrayS[], ArrayList Array, int left, int right) {
int index = partition(ArrayS, Array, left, right);
if (left < index - 1) {
sort(ArrayS, Array, left, index+1);
}
if (index < right) {
sort(ArrayS, Array, index-1, right);
}
return index;
}
private static int partition(int ArrayS[], ArrayList Array, int left, int right) {
right=ArrayS[0];
left=ArrayS[9];
int i = left;
int j = right;
int pivot = ArrayS[(left + right) / 2];
while (i <= j) {
while (ArrayS[i] < pivot) {
i++;
}
while (ArrayS[j] > pivot) {
j--;
}
if (i <= j) {
int temp = ArrayS[i];
ArrayS[i] = ArrayS[j];
ArrayS[j] = temp;
i++;
j--;
}
}
for (int l = 0;l<10;l++){
System.out.println(ArrayS[l]);
}
return i;
}
}
Explanation / Answer
follow the below code which may helps you.
package daa;
import java.util.ArrayList;
import java.util.Random;
public class QuickSort {
private static ArrayList<Integer> inputArray = new ArrayList<Integer>();
public QuickSort(ArrayList<Integer> inputArray){
QuickSort.inputArray = inputArray;
}
public void startQuickStart(int start,int end){
int q;
if(start<end){
q = partition(start, end);
startQuickStart(start, q);
startQuickStart(q+1, end);
}
}
public ArrayList<Integer> getSortedArray(){
return QuickSort.inputArray;
}
int partition(int start,int end){
System.out.println(" ---------Iteration Starts----------");
System.out.println(" Sorting Window from index number:"+start+" to "+end);
int init = start;
int length = end;
Random r = new Random();
int pivotIndex = nextIntInRange(start,end,r);
int pivot = inputArray.get(pivotIndex);
System.out.println("Pivot Element "+pivot+" at index:"+pivotIndex);
while(true){
while(inputArray.get(length)>pivot && length>start){
length--;
}
while(inputArray.get(init)<pivot && init<end){
init++;
}
if(init<length){
int temp;
temp = inputArray.get(init);
inputArray.set(init,inputArray.get(length));
inputArray.set(length,temp);
length--;
init++;
System.out.println(" After Swapping");
for(int i=start;i<=end;i++){
System.out.print(inputArray.get(i)+" ");
}
}else{
System.out.println(" ---------Iteration Ends---------");
return length;
}
}
}
// Below method is to just find random integer from given range
static int nextIntInRange(int min, int max, Random rng) {
if (min > max) {
throw new IllegalArgumentException("Cannot draw random int from invalid range [" + min + ", " + max + "].");
}
int diff = max - min;
if (diff >= 0 && diff != Integer.MAX_VALUE) {
return (min + rng.nextInt(diff + 1));
}
int i;
do {
i = rng.nextInt();
} while (i < min || i > max);
return i;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.