Arrays: quicksort type problems

QUICK SORT TYPE PROBLEMS

K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)

We recommend to read following post as a prerequisite of this post.

K’th Smallest/Largest Element in Unsorted Array | Set 1

Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array. It is given that ll array elements are distinct.

Examples:

Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 4
Output: 10

We have discussed three different solutions here.

-

	package com.tvidushi.arrays;
	public class KthSmallestElement {
	public int findkthSmallestElement(int[] arrA, int k) {
	k = k - 1; // since array index starts with 0
	return kSmall(arrA, 0, arrA.length - 1, k);
	}
	public int kSmall(int[] arrA, int start, int end, int k) {
	int left = start;
	int right = end;
	int pivot = start;
	while (left <= right) {
	//increment left until it reaches a point where it becomes less than or equal to pivot
	while (left <= right && arrA[left] <= arrA[pivot]){
	System.out.println("left"+left);
	left++;
	}
	//Decrement right until it reaches a point where it becomes greater than or equal to pivot
	while (left <= right && arrA[right] >= arrA[pivot]){
	System.out.println("right"+right);
	right--;
	}
	//if still left is less than right than swap a[left] & a[right]
	if (left < right) {
	System.out.println("---left"+left);
	System.out.println("---right"+right);
	swap(arrA, left, right);
	left++;
	right--;
	}
	}
	//swap the elements
	swap(arrA, pivot, right);
	//if pivot =k
	if (pivot == k)
	return arrA[pivot];// if pivot is kth element , return
	//we sorted array until the kth element ,we shd quit here as we reached the element
	else if (pivot < k)
	// if pivot is less than k, then kth element will be on the right
	return kSmall(arrA, pivot + 1, end, k);
	else
	// if pivot is greater than k, then kth element will be on the right
	return kSmall(arrA, start, pivot - 1, k);
	}
	public void swap(int[] arrA, int a, int b) {
	System.out.println("---arrA[a]"+arrA[a]);
	System.out.println("---arrA[b]"+arrA[b]);
	int x = arrA[a];
	arrA[a] = arrA[b];
	arrA[b] = x;
	}
	public static void main(String args[]) {
	int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 };
	KthSmallestElement k = new KthSmallestElement();
	int a = 4;
	int x = k.findkthSmallestElement(arrA, a);
	System.out.print("The " + a + "th smallest element is : " + x);
	}
	}

view raw KthSmallestElement.java hosted with ❤ by GitHub

-