I. Overview: you will write a program to return the kth smallest element of an a
ID: 3809702 • Letter: I
Question
I. Overview:
you will write a program to return the kth smallest element of an array A[] with n elements. (For example, k=1 is the smallest, k=n is the largest, and k=n/2 is the median.) In this programming assignment, you are to use two different algorithms, as describe below, to implement the solutions.
1.Algorithm1: Sort the array using QuickSort and pick the kth smallest element. This has average time complexity of O(nlogn) and worst-case time of O(n^2).
2.Algorithm2: Use Quick-Select (with LomutoPartition) discussed in our lecture (also available in the textbook). This algorithm has an average time complexity of O(n) and a worst-case time of O(n^2).
II. Requirements:
1.Run experiments for the following values of n: 10,000, 100,000 and 1,000,000. For each value of n, produce an array of randomly generated elements (you may use integers). Then use each of the two methods to find the kth smallest element for k=n/2 and print one line result:
2.Algorithm X: n, k, A[k], Number of Key-Comparisons
Make sure that the same original array of n elements is used for both methods. Explain how the results compare with the expected analytical results.
3.Write all your own code. Do not use "off the shelf" code from any source. In particular, you are not allowed to use any sorting function from C/Java libraries. The only variable types allowed in your program are int and int[]. You are not allowed to use any reference data type in Java, like List, Set, etc. The function signature would look like:
4.select1(int[] a, int n, int k);
Hint: Do not perform the key comparisons in-line. Rather, use a function to perform each key comparison, while incrementing a counter.
5.Your program should be written in either Java or C programming language.
Explanation / Answer
Quick Sort
import java.util.Scanner;
public class QuickSortAlgo
{
int arr[];
int length;
public void sort(int[] inputArr)
{
if (inputArr == null || inputArr.length == 0)
{
return;
}
this.arr = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex)
{
int i = lowerIndex;
int j = higherIndex;
int pivot = arr[lowerIndex+(higherIndex-lowerIndex)/2];
while (i <= j)
{
while (arr[i] < pivot)
{
i++;
}
while (arr[j] > pivot)
{
j--;
}
if (i <= j)
{
swap(i, j);
i++;
j--;
}
}
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void swap(int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String a[])
{
QuickSortAlgo myarr = new QuickSortAlgo();
int[] i = {24,2,45,20,56,75,2,56,99,53,12,66,11,33,44,56,76,33,11,55,44};
myarr.sort(i);
System.out.println("Enter index of smallest no you want to find");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.print("The"+n+"th Smallest element is "+i[n-1]);
}
}
Quick Select Algorithm:
import java.util.Scanner;
public class QuickSelectAlgo
{
private static void swapnumber(Comparable<?>[] array, int a, int b)
{
Comparable<?> t = array[a];
array[a] = array[b];
array[b] = t;
}
private static int part(Comparable[] array, int low, int high, int pivot)
{
Comparable pivot_val = array[pivot];
int larger = low;
swapnumber(array, pivot, high);
for(int i = low; i < high; ++i)
{
if(pivot_val.compareTo(array[i]) == -1)
{
swapnumber(array, i, larger++);
}
}
swapnumber(array, high, larger);
return larger;
}
public static Comparable<?> quiselect(Comparable<?>[] arr, int k)
{
int low = 0;
int high = arr.length - 1;
while(low <= high)
{
int random = (int) ((Math.random() * (high - low)) + low);
int p = part(arr, low, high, random);
if(p == k-1)
{
return arr[p];
}
else if(p > k-1)
{
high = p - 1;
}
else
{
low = p + 1;
}
}
return null;
}
public static void main(String args[])
{
Integer[] arr = {2, 4, 5, 3, 1, 5, 24,2,45,20,56,75,2,56,99,53,12,9, 66,11,33,44,56,76,33,11,55,44,8, 6, 1};
System.out.println("Enter nth largest no you want to find");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.println(quiselect(arr, n));
}
}