Can someone help me with these java sorting methods. I have provide the code of
ID: 3707518 • Letter: C
Question
Can someone help me with these java sorting methods. I have provide the code of what I need filled in. Thanks in advance!!
/**
* Sorts a list of Persons using merge sort
*
* @param list
*/
public static void mergeSort (ArrayList<Person> list)
{
// Provide this code
}
/**
* Merge two sorted lists
*
* @param list1
* @param list2
* @param temp
*/
public static void merge (ArrayList<Person> list1, ArrayList<Person> list2, ArrayList<Person> temp)
{
// Provide this code and add in numCompares
}
/**
* QuickSort start method
*
* @param list
*/
public static void quickSort(ArrayList<Person> list)
{
quickSort(list, 0, list.size() - 1);
}
/**
* QuickSort recursive method
*
* @param list
* @param start
* @param end
*/
private static void quickSort (ArrayList<Person> list, int start, int end)
{
// Provide this code
}
/**
* Partition the array list[start..lend]
*
* @param list
* @param start
* @param end
*/
private static int partition (ArrayList<Person> list, int start, int end)
{
// Provide this code and add in numCompares
}
Explanation / Answer
Below code is to sort integers, align your person class with the sorting logics and simply replace the srting factor with the number, logic remains same.
Code:
public class Main {
/* Pivot and partitioning function: Takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
private static int pivot(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
public static void quickSortRecursive(int arr[], int low, int high) {
if (low < high) {
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = pivot(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSortRecursive(arr, low, pi - 1);
quickSortRecursive(arr, pi + 1, high);
}
}
// merge two sorted portions of given array arr, namely, from start to middle
// and from middle + 1 to end into one sorted portion, namely, from start to end
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
private static void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
public static void mergeSortRecursive(int arr[], int l, int r) {
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSortRecursive(arr, l, m);
mergeSortRecursive(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/*
Main method
*/
public static void main(String a[]) {
int arr3[] = {10, 7, 8, 9, 1, 5};
int n = arr3.length;
System.out.print(" Quick sort results: ");
quickSortRecursive(arr3, 0, n - 1);
for (int i: arr3) {
System.out.print(i);
System.out.print(", ");
}
int arr4[] = {12, 11, 13, 5, 6, 7};
int arr_size = arr4.length;
System.out.print(" Merge sort results: ");
mergeSortRecursive(arr4, 0, arr_size - 1);
for (int i: arr4) {
System.out.print(i);
System.out.print(", ");
}
}
}