Is there a way to compress this code down? if so how? and is it possible to expl
ID: 3775445 • Letter: I
Question
Is there a way to compress this code down? if so how? and is it possible to explain what is going on in this program line by line.
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class Sort {
private static final Random random = new Random();
private static final int RANDOM_INT_RANGE = 100;
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Enter Number of elements in array");
int n = scan.nextInt();
int[] arr = newTestArray(n);
int[] copy = Arrays.copyOf(arr, arr.length);
System.out.println("Unsorted array: " + Arrays.toString(arr));
if(n <= 64)
insertionSort(arr);
else
quickSort(arr);
// check the result
Arrays.sort(copy);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
private static int[] newTestArray(int size) {
final int[] arr = new int[size];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(RANDOM_INT_RANGE);
}
return arr;
}
private static void quickSort(int[] arr) {
if(arr.length > 0)
sortInPlace(arr, 0, arr.length - 1);
}
private static void sortInPlace(int[] arr, int left, int right) {
if(left >= right) return; // sorted
final int range = right - left + 1;
int pivot = random.nextInt(range) + left;
//int pivot = (left + (right - left)) / 2;
int newPivot = partition(arr, left, right, pivot);
sortInPlace(arr, left, newPivot - 1);
sortInPlace(arr, newPivot + 1, right);
}
private static int partition(int[] arr, int left, int right, int pivot)
{
// we're going to move around the values in the array.
// > than this pivot value goes to the right,
// < than this pivot value goes to the left
int pivotVal = arr[pivot];
// temporarily move the pivot value out of the way...
swapArrayVals(arr, pivot, right);
int storeIndex = left;
for(int i = left; i <= (right - 1); i++) {
if(arr[i] < pivotVal) {
swapArrayVals(arr, i, storeIndex);
storeIndex++;
}
}
swapArrayVals(arr, storeIndex, right);
return storeIndex;
}
private static void swapArrayVals(int[] arr, int from, int to) {
int fromVal = arr[from];
int toVal = arr[to];
arr[from] = toVal;
arr[to] = fromVal;
}
private static void insertionSort(int[] arr)
{
int temp;
for (int i = 1; i < arr.length; i++)
{
for(int j = i ; j > 0 ; j--)
{
if(arr[j] < arr[j-1])
{
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
}
Explanation / Answer
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class Sort {
private static final Random random = new Random();
private static final int RANDOM_INT_RANGE = 100;
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Enter Number of elements in array");
int n = scan.nextInt();
int[] arr = newTestArray(n);
int[] copy = Arrays.copyOf(arr, arr.length);
System.out.println("Unsorted array: " + Arrays.toString(arr));
if(n <= 64)
insertionSort(arr);
else
quickSort(arr);
// check the result
Arrays.sort(copy);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
private static int[] newTestArray(int size) {
final int[] arr = new int[size];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(RANDOM_INT_RANGE);
}
return arr;
}
private static void quickSort(int[] arr) {
if(arr.length > 0)
sortInPlace(arr, 0, arr.length - 1);
}
private static void sortInPlace(int[] arr, int left, int right) {
if(left >= right) return; // sorted
final int range = right - left + 1;
int pivot = random.nextInt(range) + left;
//int pivot = (left + (right - left)) / 2;
int newPivot = partition(arr, left, right, pivot);
sortInPlace(arr, left, newPivot - 1);
sortInPlace(arr, newPivot + 1, right);
}
private static int partition(int[] arr, int left, int right, int pivot)
{
// we're going to move around the values in the array.
// > than this pivot value goes to the right,
// < than this pivot value goes to the left
int pivotVal = arr[pivot];
// temporarily move the pivot value out of the way...
swapArrayVals(arr, pivot, right);
int storeIndex = left;
for(int i = left; i <= (right - 1); i++) {
if(arr[i] < pivotVal) {
swapArrayVals(arr, i, storeIndex);
storeIndex++;
}
}
swapArrayVals(arr, storeIndex, right);
return storeIndex;
}
private static void swapArrayVals(int[] arr, int from, int to) {
int fromVal = arr[from];
int toVal = arr[to];
arr[from] = toVal;
arr[to] = fromVal;
}
private static void insertionSort(int[] arr)
{
int temp;
for (int i = 1; i < arr.length; i++)
{
for(int j = i ; j > 0 ; j--)
{
if(arr[j] < arr[j-1])
{
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.