Question

JAVA - Quick Sort .txt and Return

-----------------------------------------------------------------------------

The program should input a .txt file like below and must use a Quick sort Algorithm

================

6 10

4 19 10 12 8 6

0 1 2

3

================

The first number "6" represents the index of the element to return after sort

the second number on the top "10" represents the number of elements or size of array.

The following numbers and lines are the elements that need to go into the array and be sorted.

-----------------------------------------------------------------------------

It should then:

1) Sort using the natural variant of quick sort algorithm and return the "6"th element

the "6" comes from the text file and should work with whatever number the text file has as long as its less than or equal to the second number, in this case "10".

Example Output given above .txt file:

Quicksort finds 8.

Answer 1

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class QuickSortAlgo {
  
private static final String FILENAME = "a.txt";
  
public static void main(String[] args)
{
Scanner fileReader;
int nIndex = 0;
int n = 0;
int[] arr = null;
  
try
{
fileReader = new Scanner(new File(FILENAME));
nIndex = fileReader.nextInt();
n = fileReader.nextInt();
if(nIndex > n)
{
System.out.println("We cannot get element at index " + nIndex + ", where number of elements is " + n);
System.exit(0);
}
arr = new int[n];
int count = 0;
  
while(fileReader.hasNext())
{
arr[count++] = fileReader.nextInt();
}
fileReader.close();
}catch(FileNotFoundException fnfe){
System.out.println(FILENAME + " could not be found!");
System.exit(0);
}
  
System.out.print("Original array: [ ");
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println(" ]");
  
// sort the array
implementQuickSort(arr, 0, n - 1);
  
System.out.print("Sorted array: [ ");
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println(" ]");
  
System.out.println("Quicksort finds " + arr[nIndex]);
}
  
private static int determinePartitionIndex(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for(int j = low; j < high; j++)
{
if(arr[j] < pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
  
return (i + 1);
}
  
private static void implementQuickSort(int arr[], int low, int high)
{
if(low < high)
{
int partitionIndex = determinePartitionIndex(arr, low, high);
implementQuickSort(arr, low, partitionIndex - 1);
implementQuickSort(arr, partitionIndex + 1, high);
}
}
}

******************************************************************** SCREENSHOT *******************************************************