There are many different methods to retrieve K largest elements from large unsorted arrays.
This is one of the basic algorithms which will be taught in any good algorithms class.
Before we answer the question we need to understand what time complexity of different algorithms means and what makes one algorithm better than the other.
The below article will discuss these concepts in depth and help you understand the Best way to retrieve K largest elements from large unsorted arrays and what circumstances makes it the best.
How to determine the best way to retrieve K largest elements from large unsorted arrays?
Best algorithm in terms of simplicity would be bubble sort and in terms of time complexity or quickness the best algorithm would be quick sort algorithm.
After sorting you can directly select the largest k elements from an array. That is best developer adapted and proven way to retrieve K largest elements from large unsorted arrays .
What is Time Complexity?
Before we even begin talking about algorithms we need to know what time complexity means because this is what will be used to evaluate our algorithms.
Time complexity in simple words tells you how fast a given algorithm works. It is represented by the symbol Big O in the form of a function O(x).
For this article you should know that O(1) means constant time and is the fastest followed by O(log n), and then O(n). The function shows time complexity depending on how mathematical functions evolve; for example log(n) evolves slowes than n which is linear.
Different Algorithms to retrieve K largest elements from large unsorted Arrays:
Our methodology will be to first sort the array first in descending order then just take out the first k elements.
So below we will discuss some quick sorting methods and discuss which is better in which situations and which is the easiest to deploy and understand.
1. Merge Sort Algorithm
Merge Sort algorithm uses the divide and conquer approach. In this approach, the array is constantly divided into two halves and then sortedly merged.
Think of it as a recursive process that splits the array in half until further division is impossible. For example, if the array is empty or has just one element left, it should stop dividing; this is the default condition for terminating the recursion.
If the array has several items, we must divide it into half and recursively apply the merge sort on each of the halves.
Finally, after both halves have been sorted, the merge function should be used. The Merge function is responsible for joining two smaller sorted arrays to create a bigger one.
The time complexity for a merger sort is O(nLogn) is a sort which is important to understand if you want to learn faster sorting mechanisms.
The difficulty of deploying this algorithms is considered medium level and should be easy to understand granted you have learned and understood basic algorithms like the bubble sort. The pseudocode for merge sort is given below:
step 1: start
step 2: declare array and left, right, mid variable
step 3: perform merge function.
mergesort(array,left,right)
mergesort (array, left, right)
if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
step 4: Stop2. Quick sort Algorithm
Quick sort is one of the quickest sorting procedures. It has the ability to sort in O(n) time, which is linear time.
Similar to Merge Sort, QuickSort is also an algorithm which uses the Divide and Conquer technique.
It chooses an element as a pivot and splits an array around that pivot point. Different rapid sort algorithms utilize different ways to choose the appropriate algorithm for the scenario.
Below are some methods to pick the pivot depending upon your situation:
- Pick the first element as a pivot.
- Pick the last element as a pivot (The below example uses this)
- Pick a random element as a pivot.
- Pick median as the pivot.
The main differentiating factor in the process of quickSort is a partition().
The primary goal of partitions is, assume you are given an array and an element x of an array as the pivot, put x at its correct position in a sorted array and put all elements smaller than x before x, and put all elements greater than x after x.
All of this process should be done in linear time.
3. Partition Algorithm
There are many different ways a partition algorithm can be done, the below mentioned pseudo code takes the method which is most commonly used and is easy to understand.
The concept of a partition algorithm is straightforward: we begin with the element on the leftmost and keep track of the index of smaller or equal to the elements as i. As we traverse the array, we swap the current element with arr[i]. Otherwise, we must ignore the current element.
The psedo is mentioned below:
Pseudo Code for recursive QuickSort function:
/* An explanation for the variables: low –> Starting index, high –> Ending index */
quickSort(arr[], low, high) {
if (low < high) {
/* An explanation for the variables: pi is partitioning index, arr[pi] is now at right place */
pi = partition(arr, low, high);
quickSort(arr, low, pi – 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
Pseudo code for partition()
/* This function will take the last element as pivot, and will place the pivot element at its correct position in a sorted array.
Then it will place all elements smaller than pivot to left of pivot and all elements greater than the pivot to right of pivot */
partition (arr[], low, high)
{
// pivot (Element to be placed at right position)
pivot = arr[high];
i = (low – 1) // Index of smaller element and indicates the
// right position of pivot found so far
for (j = low; j <= high- 1; j++){
// If current element is smaller than the pivot
if (arr[j] < pivot){
i++; // increment index of smaller element
swap arr[i] and arr[j]
}
}
swap arr[i + 1] and arr[high])
return (i + 1)
}
4. Bubble sort Algorithm
In terms of simplicity and ease of learning, Bubble Sort is regarded as the superior algorithm. A bubble sort has an O(n2) time complexity and is one of the slowest sorting algorithms, yet it is vital to master and comprehend.
It is the simplest sorting algorithm which works by continuously exchanging the adjacent elements if they are not in sorted order.
This approach is not recommended for huge datasets since its average and worst case time complexity are both quite high.
How Bubble Sort Works?
Consider an array arr[] = {25, 21, 24, 22, 28}
First Pass:
- The bubble sort compares elements side by side, and it starts by comparing the first two elements.
- ( 25 21 24 22 28 ) –> ( 21 25 24 22 28 ), in this case since 25>21 the swap is being done. The algorithm compares the two numbers
- ( 21 25 24 22 8 ) –> ( 21 24 25 22 28 ), since 25 > 24 the Swap is done
- ( 21 24 25 22 28 ) –> ( 21 24 22 25 28 ), since 25 > 22 the Swap is done
- ( 21 24 22 25 28 ) –> ( 21 24 22 25 28 ), Here the swap will not be done as the elements are already in order properly
Second Pass:
- The second iteration will look something like this
- ( 21 24 22 25 28 ) –> ( 21 24 22 25 28 )
- ( 21 24 22 25 28 ) –> ( 21 22 24 25 28 ), since 24 > 22 the Swap is done
- ( 21 22 24 25 28 ) –> ( 21 22 24 25 28 )
- ( 21 22 24 25 28 ) –> ( 21 22 24 25 28 )
Third Pass:
- This is were the biggest weakness of bubble sort lies, even though the array is already sorted the algorithm does not know that so it will go through the iteration again wasting the cpu’s time and power.
- The algorithm does one whole iteration again without any swap to know that it is sorted.
- ( 21 22 24 25 28 ) –> ( 21 22 24 25 28 )
- ( 21 22 24 25 28 ) –> ( 21 22 24 25 28 )
- ( 21 22 24 25 28 ) –> ( 21 22 24 25 28 )
- ( 21 22 24 25 28 ) –> ( 21 22 24 25 28 )
I hope this extensively helps you understand how algorithms works and which algorithm will work best for you depending upon your knowledge, skill level and use case.
Conclusion
To answer “Best way to retrieve K largest elements from large unsorted arrays” simply would be to tell you that the best algorithm in terms of simplicity would be bubble sort and in terms of time complexity or quickness the best algorithm would be quick sort algorithm.
After sorting you can directly select the largest k elements from an array. I hope this extensively helps you understand how algorithms works and which algorithm will work best for you depending upon your knowledge, skill level and use case.