Find K'th smallest and largest element in an unsorted array

How to use iterative, heapsort and quicksort techniques to find K'th smallest and largest numbers in unsorted array


Category: Data Structure And Algorithms Tags: C#

Find Kth smallest and largest element in an unsorted array - Code Files

Problem statement

    In a given unsorted array having length N and a number K where 0<=K<=N, it is asked to find Kth smallest or largest number in array.

Suppose array arr={5, 10, 12, 1, 4, 7, 15, 13} and asked to find 4th smallest and largest element and output is 7 and 10 respectively.

Solutions

Solution 1: Simple iterative solution - Complexity O(n2)

    public static int KthSmallestIterativeSolution(int[] arr, int k)
    {
        int min = int.MaxValue;
        for (int i = 0; i < k; i++)
        {
            int minIndex = i;
            min = int.MaxValue;
            for (int j = i; j < arr.Length; j++)
            {
                if (arr[j] < min)
                {
                    min = arr[j];
                    minIndex = j;
                }
            }
            // Don't replace if min is already at its correct position
            if (minIndex != i)
            {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
        return min;
    }

    We can simply find smallest elements and put them at lower indexes starting zero. So first smallest element will be placed at 0th index then we look for 2nd smallest element in remaining array (from 1 to n) and place it at 1st index and this goes on until we find Kth smallest element. Let’s run above program.

    static void Main(string[] args)
    {
        int[] arr = new int[] { 5, 10, 12, 1, 4, 7, 15, 13 };
        int k = 4;

        int kthSmallestIterativeSolution = KthSmallestIterativeSolution(arr, k);

        Console.WriteLine($"{k}th smallest element is {kthSmallestIterativeSolution} using {nameof(KthSmallestIterativeSolution)}");
    }

Output

4th smallest element is 7 using KthSmallestIterativeSolution

Similar way we can look for largest elements and place them at initial indexes in order to find Kth largest element.

Solution 2: Using Heap data structure - Complexity O(nlogn)

    If you want to learn about heap data structure and heap sort go through this article. Once MinHeap is created out of array it always places smallest element of array at 0th index. If we want to find Kth smallest then we can place smallest element at end indexes and call MinHeapify on remaining items that will again place smallest element at 0th position. We do the same until we reach desired Kth element.

Below I have created a class for heap data structure with all required methods.

namespace DataStructuresAndAlgorithms
{
    public class Heap
    {
        int[] _arr;
        int _size;

        public Heap(int[] arr)
        {
            _arr = arr;
            _size = arr.Length;
        }
        public void BuildMinHeap()
        {
            for (int i = (_size - 1) / 2; i >= 0; i--)
            {
                MinHeapify(i, _size - 1);
            }
        }

        public void BuildMaxHeap()
        {
            for (int i = (_size - 1) / 2; i >= 0; i--)
            {
                MaxHeapify(i, _size - 1);
            }
        }

        public void MinHeapify(int i, int maxIndex)
        {
            int leftChild = ChildLeft(i);
            int rightChild = ChildRight(i);

            int min = i;

            if (leftChild <= maxIndex && _arr[min] > _arr[leftChild])
            {
                min = leftChild;
            }
            if (rightChild <= maxIndex && _arr[min] > _arr[rightChild])
            {
                min = rightChild;
            }

            if (min <= maxIndex && min != i)
            {
                Swap(i, min);
                MinHeapify(min, maxIndex);
            }
        }

        public void MaxHeapify(int i, int maxIndex)
        {
            int leftChild = ChildLeft(i);
            int rightChild = ChildRight(i);

            int max = i;

            if (leftChild <= maxIndex && _arr[max] < _arr[leftChild])
            {
                max = leftChild;
            }
            if (rightChild <= maxIndex && _arr[max] < _arr[rightChild])
            {
                max = rightChild;
            }

            if (max <= maxIndex && max != i)
            {
                Swap(i, max);
                MaxHeapify(max, maxIndex);
            }
        }

        public void Swap(int x, int y)
        {
            int temp = _arr[x];
            _arr[x] = _arr[y];
            _arr[y] = temp;
        }

        public int Size()
        {
            return _size;
        }

        public int ElementAt(int i)
        {
            return _arr[i];
        }

        private int ChildLeft(int index)
        {
            return (index * 2) + 1;
        }
        private int ChildRight(int index)
        {
            return (index * 2) + 2;
        }
        private int Parent(int index)
        {
            return index / 2;
        }
    }
}

Now we have both Max and Min Heapify methods, for Kth smallest we will use MinHeap and for Kth largest we will use MaxHeap. Let’s create two methods to find Kth smallest and largest elements.

    public static int KthSmallestHeap(int[] arr, int k)
    {
        Heap heap = new Heap(arr);
        heap.BuildMinHeap();
        int maxIndex = heap.Size() - 1;

        for (int i = k; i > 0; i--)
        {
            // Placing smallest element from 0th index to end indexes
            heap.Swap(0, maxIndex);
            // Reducing maxIndex so heapify runs till unsorted elements only leaving swapped elements
            maxIndex--;
            // MinHeapify places smallest element at 0th index
            heap.MinHeapify(0, maxIndex);
        }

        return heap.ElementAt(heap.Size() - k);
    }

    public static int KthLargestHeap(int[] arr, int k)
    {
        Heap heap = new Heap(arr);
        heap.BuildMaxHeap();
        int maxIndex = heap.Size() - 1;

        for (int i = k; i > 0; i--)
        {
            heap.Swap(0, maxIndex);
            maxIndex--;
            heap.MaxHeapify(0, maxIndex);
        }

        return heap.ElementAt(heap.Size() - k);
    }

Run the methods to find Kth smallest and largest elements.

    static void Main(string[] args)
    {
        int[] arr = new int[] { 5, 10, 12, 1, 4, 7, 15, 13 };
        int k = 4;

        int kthSmallestHeap = KthSmallestHeap(arr, k);
        int kthLargestHeap = KthLargestHeap(arr, k);

        Console.WriteLine($"{k}th smallest element is {kthSmallestHeap} using {nameof(KthSmallestHeap)}");
Console.WriteLine($"{k}th largest element is {kthLargestHeap} using {nameof(KthLargestHeap)}");
}

Output

4th smallest element is 7 using KthSmallestHeap

4th largest element is 10 using KthLargestHeap

Solution 3: Quick Sort Method - Complexity O(nlogn)

    I would recommend you to through quick sort before getting into this solution. Quick sort basically work by choosing a number as pivot and then finding its final position in array by comparing it with other numbers. Once final position is found, array splits from that position and same is done on splitted arrays until final position is found for each element.

We will use quick sort idea and just perform pivot on desired split of array, Suppose in array arr={5, 10, 12, 1, 4, 7, 15, 13} we want to find 4th smallest element. We have first pivot as 13 and its final position is at index 6 so after placing it at 6th index array is now arr={5, 10, 12, 1, 4, 7, 13, 15}. So now we want to look for 4th smallest element which should be placed at index 3 if array is sorted. Now we have to perform same in array split [0,5] and we can abandon other split [7,7]. We do same until we have all elements sorted in split containing index 3 or as soon as we find some pivot placed at index 3.

namespace DataStructuresAndAlgorithms
{
    public class QuickSortSolution
    {
        int[] _arr;

        public QuickSortSolution(int[] arr)
        {
            _arr = arr;
        }

        /// <summary>
        /// Returns Kth smallers element
        /// </summary>
        /// <param name="k">K</param>
        /// <param name="p">starting index</param>
        /// <param name="r">Ending index</param>
        /// <returns></returns>
        public int KthSmallestElementQuick(int k, int p, int r)
        {
            if (p < r)
            {
                // Index from where array will be splitted
                int q = Partition(p, r);
                //If pivot is placed at index k-1 then it is the solution
                if (q == (k - 1))
                {
                    return _arr[k-1];
                }
                // Else continue searching in left or right split based on desired number k
                else if (q > (k - 1))
                {
                    return KthSmallestElementQuick(k, p, q - 1);
                }
                else
                {
                    return KthSmallestElementQuick(k, q + 1, r);
                }
            }
            return _arr[k - 1];
        }

        private int Partition(int p, int r)
        {
            int pivot = _arr[r];
            int i = p - 1;

            for (int j = p; j < r; j++)
            {
                if (_arr[j] <= pivot)
                {
                    i++;
                    Swap(i, j);
                }
            }
            i++;
            Swap(i, r);
            return i;
        }

        private void Swap(int i, int j)
        {
            int temp = _arr[i];
            _arr[i] = _arr[j];
            _arr[j] = temp;
        }
    }
}

Let’s run the above code.

    static void Main(string[] args)
    {
        int[] arr = new int[] { 5, 10, 12, 1, 4, 7, 15, 13 };
        int k = 4;

        QuickSortSolution quickSortSolution = new QuickSortSolution(arr);
        int kthSmallestElementQuick = quickSortSolution.KthSmallestElementQuick(k, 0, arr.Length - 1);

        Console.WriteLine($"{k}th smallest element is {kthSmallestElementQuick} using {nameof(quickSortSolution.KthSmallestElementQuick)}");
    }

Output

4th smallest element is 7 using KthSmallestElementQuick


Like 0 People
Last modified about 8 days ago
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 144
Questions: 15
Given Best Solutions: 15 *

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x