Hello, I need to implement a sorting algorithm using NetBeans 8.2 and Java langu
ID: 3810387 • Letter: H
Question
Hello, I need to implement a sorting algorithm using NetBeans 8.2 and Java language.
The sorting algorightm is QuickSort. Your Quicksort algorithm must use the median-of-three method to determine the pivot, and must use the Hoare Partition algorithm.
This algorithm will have to sort numbers in ascending order. Has to read the input file that will be a file with 10 randoms numbers. The file name is 10.txt.
For example. 10.txt:
-1,2,3,-2,10,24,-68,-90,98,54
You must also have a function confirmSorted(). This function should take your array of numbers, verify that it is sorted in ascending order, and return a Boolean. If the numbers are confirmed to be sorted, print out “Confirmed sorted” and if they aren’t sorted, print out “Confirmed NOT sorted”. Do this before and after the sort.
Also, all programming languages have ways to get elapsed time in milliseconds. The basic idea is to get the time (in milliseconds) before sorting, after sorting, and then find the difference between them.
This image is just an example of how it should look after running the program.
Sample output Below is an idea of what kind of output your program should have Reading data from 100000.txt Confirmed NOT sorted. Sorting using Quicksort. It took 150 ms. Confirmed SortedExplanation / Answer
HI FRiend, Please find my implementation.
For smaller input size: it always pritn 0 miliseconds.
Please let me know in cae of any issue.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class SortFileIntegers {
public static boolean confirmSorted(int[] arr){
for(int i=0; i<arr.length-1; i++)
if(arr[i] > arr[i+1])
return false;
return true;
}
/* This 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 partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<=high-1; 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 quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(System.in);
System.out.print("Enter input file name: ");
String fileName = sc.next();
// opening input file name
Scanner fileScanner = new Scanner(new File(fileName));
// creating an array of size 10
int size = 10;
int arr[] = new int[size];
int i =0 ;
while(fileScanner.hasNextInt())
arr[i++] = fileScanner.nextInt();
fileScanner.close();
sc.close();
if(confirmSorted(arr)){
System.out.println("Confirmed Sorted");
}else{
System.out.println("Confirmed NOT Sorted");
System.out.println("Sorting using Quicksort");
long start = System.currentTimeMillis();
quickSort(arr, 0, arr.length-1);
System.out.println("It took "+(System.currentTimeMillis()-start)+" ms");
System.out.println("Confirmed Sorted");
}
}
}
/*
######### 10.txt #############
-1 2 3 -2 10 24 -68 -90 98 54
Sample run:
Enter input file name: 10.txt
Confirmed NOT Sorted
Sorting using Quicksort
It took 0 ms
Confirmed Sorted
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.