Implement the sort method which sorts the integer array from index start to the
ID: 3697224 • Letter: I
Question
Implement the sort method which sorts the integer array from index start to the index end and the median method which returns the median value of x, y, and z.
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int size = 50;
int[] x = new int[size];
for(int i=0; i<size; i++) {
x[i] = (int) (Math.random() * size);
}
System.out.println(Arrays.toString(x));
new QuickSort(x).sort(0, size-1);
System.out.println(Arrays.toString(x));
}
static final int MIN_SIZE = 10;
int[] array;
QuickSort(int[] array) { this.array = array; }
// sort the array from start to end (inclusive)
// use selection sort when end - start < MIN_SIZE
void sort(int start, int end) {
// TODO
}
void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// return the median value of x, y, and z
int median(int x, int y, int z) {
// TODO
}
}
class SelectionSort {
int[] array;
int start, end;
SelectionSort(int[] array, int start, int end) { this.array = array; this.start = start; this.end = end; }
int[] sort() {
for(int i=start; i<end; i++) {
int j = minIndex(i);
if (i != j) {
swap(i, j);
}
}
return array;
}
void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// return the index with min value from index "start" in "array"
int minIndex(int start) {
int ret = start;
for(int i=start+1; i<=end; i++) {
if(array[ret] > array[i]) {
ret = i;
}
}
return ret;
}
}
Explanation / Answer
import java.util.Arrays;
class QuickSort {
public static void main(String[] args) {
int size = 50;
int[] x = new int[size];
for(int i=0; i<size; i++) {
x[i] = (int) (Math.random() * size);
}
System.out.println(Arrays.toString(x));
new QuickSort(x).sort(0, size-1);
System.out.println(Arrays.toString(x));
}
static final int MIN_SIZE = 10;
int[] array;
QuickSort(int[] array) { this.array = array; }
// sort the array from start to high (inclusive)
// use selection sort when high - start < MIN_SIZE
void sort(int start, int high) {
int[] numbers;
int i = start, j = high;
// Get the pivot element from the middle of the list
int pivot = numbers[start + (high-start)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (numbers[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (numbers[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// Recursio
if (start < j)
quicksort(start, j)
if (i < high)
quicksort(i, high);
// TODO
}
void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// return the median value of x, y, and z
int median(int x, int y, int z) {
// TODO
}
}
class SelectionSort {
int[] array;
int start, high;
SelectionSort(int[] array, int start, int high) { this.array = array; this.start = start; this.high =
high; }
int[] sort() {
for(int i=start; i<high; i++) {
int j = minIndex(i);
if (i != j) {
swap(i, j);
}
}
return array;
}
void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// return the index with min value from index "start" in "array"
int minIndex(int start) {
int ret = start;
for(int i=start+1; i<=high; i++) {
if(array[ret] > array[i]) {
ret = i;
}
}
return ret;
}
}