Finding the Kth Smallest Element

Using Randomized Quicksort

Presented by
T. SOMEASWARAN
S. SUGUNA
 INTRODUCTION
 Finding the kth smallest element in an unsorted array is a common problem in computer science, crucial
for tasks such as order statistics and data analysis. Efficiently solving this problem can significantly improve
performance in various applications. This presentation explores how to use randomized quicksort to achieve
this efficiently.

 OVERVIEW OF RANDOMIZED QUICKSORT:

 Randomized quicksort is an enhanced version of the quicksort algorithm that improves performance by

reducing the likelihood of worst-case scenarios. It works by randomly selecting a pivot element from
the array, then partitioning the array into elements less than, equal to, and greater than the pivot. The
process is recursively applied to the partitions.
 Randomization ensures that the pivot choice is unbiased, leading to an average-case time complexity of
O(n log n) for sorting. For finding the kth smallest element, the algorithm focuses only on the relevant
Randomized Quicksort
 Key points:

Partitioning :-
Partitioning is the process of rearranging the elements of an array so that all elements less
than the pivot are on the left, all elements greater than the pivot are on the right, and the pivot is in
its correct position.
Recursive Sorting :-
Recursive sorting involves applying the quicksort algorithm to the sub-arrays formed by
partitioning, sorting the left sub-array and right sub-array separately until the base case of single-
element or empty sub-arrays is reached.
Algorithm Overview:
• Randomized Pivot Selection: Randomly select a pivot element from the array to reduce the chances of
worst-case scenarios.

• Partition the Array: Partition the array into three parts: elements less than the pivot, elements equal to
the pivot, and elements greater than the pivot. Track the position of the pivot.

• Determine Pivot Position: Calculate the number of elements in the left partition (elements less than the
pivot) to determine the pivot’s position in the sorted array.

• Compare Pivot Position with K: If the pivot’s position is equal to k, the pivot is the kth smallest
element .If k is less than the pivot’s position, recursively search for the kth smallest element in the left
partition. If k is greater, adjust k by subtracting the number of elements in the left partition and the
pivot, then recursively search in the right partition.

• Repeat Until Found: Continue the process of partitioning and recursive searching until the kth smallest
Example: Finding the 3rd Smallest Element
Initial Array:

Array: [7, 10, 4, 3, 20, 15]

Goal: Find the 3rd smallest element (k=3)

Step 1: Randomized Pivot Selection and Partitioning:

Randomly select a pivot. Let's say pivot is 3.

1. Partition around 3:

1. Elements less than 3: []

2. Pivot: [3]

3. Elements greater than 3: [7, 10, 4, 20, 15]

2. Array after partitioning: [3, 7, 10, 4, 20, 15]

Step 2: Compare Pivot Position with k:
Pivot position (1) is less than k (3), so we need to find the (k-1)=2nd smallest element in the
right partition [7, 10, 4, 20, 15].
Step 3: Recur into the Right Partition:
Now, array: [7, 10, 4, 20, 15], k=2
Randomly select a pivot. Let's say pivot is 15.
Partition around 15:
•Elements less than 15: [7, 10, 4]
•Pivot: [15]
•Elements greater than 15: [20]
Array after partitioning: [7, 10, 4, 15, 20]
Position of pivot 15 in the sorted array is 4.
Step 4: Compare Pivot Position with k:

Pivot position (4) is greater than k (2), so we need to find the 2nd smallest element in the
left partition [7, 10, 4].

Step 5: Recur into the Left Partition:

Now, array: [7, 10, 4], k=2
Randomly select a pivot. Let's say pivot is 7.
Partition around 7:
•Elements less than 7: [4]
•Pivot: [7]
•Elements greater than 7: [10]
Array after partitioning: [4, 7, 10]
Position of pivot 7 in the sorted array is 2.
Step 6: Compare Pivot Position with k:
Pivot position (2) is equal to k (2), so pivot 7 is the 2nd smallest element in this partition.
Since we needed the 3rd smallest overall and we reduced the search by 1 (k-1) initially, 7 is indeed the
3rd smallest element in the original array.
Summary:
3rd Smallest Element in [7, 10, 4, 3, 20, 15]: 7
Advantage:

Efficiency: Quicksort has an average-case time complexity of O(n log n) due to the partitioning
process.

In-Place Sorting: It sorts the array in place, requiring only O(log n) additional space for the recursive
stack.
Dis Advantage

Non-deterministic behavior: Because the choice of the pivot is random, the algorithm's performance can
vary from run to run even on the same input data. This non-deterministic behavior can be a disadvantage in
some applications where predictability or reproducibility is essential.

Potential for suboptimal pivots: While random selection generally reduces the likelihood of encountering
pathological cases, there's still a small chance of choosing a suboptimal pivot. This can lead to slightly
worse performance compared to deterministic pivot selection strategies in some cases.
PRIMALITY TEST
• FERMAT’S PRIMALITY TEST:

Fermat's primality test is a probabilistic test to determine if a number is a probable prime. It is based on Fermat's
Little Theorem. According to Fermat's Little Theorem, if p is a prime number, then for any integer a such that 1 < = a <p :

a^p−1≡1 (mod p)
• Check the result:
If a^n−1mod n≠1 then n is definitely not prime.
If a^n−1mod n=1 then n might be prime.

• Limitations:

False Positives: Some composite numbers (called Carmichael numbers) can pass the test for several values
of a. Therefore, a number passing Fermat's Primality Test is "probably" prime, not guaranteed to be prime.
MILLER RABIN PRIMALITY TEST :

• The Miller-Rabin Primality Test is a probabilistic algorithm used to determine if a number is a prime. It
improves upon Fermat's Primality Test by reducing the probability of false positives, making it a more reliable
method for large numbers. Here’s an in-depth explanation of the test, its algorithm, and a C implementation

• Steps of the Algorithm

1. Find n-1 = 2^k *m

2. Choose ‘a’ such that 1< a < n-1

3. Compute b0=a^m(mod n)………

4. +1 = Composite and -1 = probability prime.
THANK YOU