Types of Sorting Algorithm in R Programming
Last Updated :
17 Jun, 2021
There are multiple ways by which data can be sorted in the R language. It’s up to the data Analyst to consider the most suitable method based upon the structure of the data. There are multiple algorithms for performing sorting on the data in the R programming language. Below different types of sorting function have been discussed. A sample of 10 random numbers between 1 to 100 from an array is used. We are going to discuss the following sorting algorithm:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
- Quick Sort
Bubble Sort
In this algorithm, two adjacent elements are compared and swapped if the criteria are met. In bubble sort, in each iteration, the largest element is brought to the end of the array(in case of increasing) by swapping elements, hence the name of the algorithm is bubble sort. To understand the bubble sort algorithm in detail please refer to Bubble Sort.
R
bubble_sort <- function(x)
{
n <- length(x)
for (i in 1 : (n - 1)) {
for (j in 1 : (n - i)) {
if (x[j] > x[j + 1]) {
temp <- x[j]
x[j] <- x[j + 1]
x[j + 1] <- temp
}
}
}
x
}
arr <- sample(1 : 100, 10)
sorted_array <- bubble_sort(arr)
sorted_array
|
Output:
[1] 2 19 26 68 74 76 80 81 82 91
Insertion Sort
In this sorting algorithm, sorted and unsorted elements are compared, and the unsorted element is placed in its correct position after each iteration. In this algorithm, the first element is assumed to be sorted and the second element is stored separately as a key element that needs to be sorted. The key is then compared with the sorted element. If the sorted element is greater than the key element, their places are swapped, and the key element becomes the first element. To understand the Insertion sort algorithm in detail please refer to Insertion Sort.
R
insertion_sort <- function(x)
{
n <- length(x)
for (i in 2 : (n))
{
key = x[i]
j = i - 1
while (j > 0 && x[j] > key)
{
x[j + 1] = x[j]
j = j - 1
}
x[j + 1] = key
}
x
}
arr <- sample(1 : 100, 10)
sorted_arr <- insertion_sort(arr)
sorted_arr
|
Output:
[1] 10 27 30 41 58 77 80 89 90 85
Selection Sort
This sorting algorithm is widely used in the R language. Here, the smallest element from the unsorted list is pushed to the start of the list at every iteration. To understand the Selection sort algorithm in detail please refer to Selection Sort.
R
selection_sort <- function(x)
{
n <- length(x)
for (i in 1 : (n - 1))
{
min_index <- i
for (j in (i + 1) : (n))
{
if (x[j] < x[min_index]) {
min_index = j
}
}
temp <- x[i]
x[i] <- x[min_index]
x[min_index] <- temp
}
x
}
arr <- sample(1 : 100, 10)
sorted_arr <- selection_sort(arr)
sorted_arr
|
Output
[1] 6 16 21 28 31 48 57 73 85 99
Merge Sort
This is a divide and conquers algorithm. We divide the array into two parts from mid, sort those two array,s and merge them. The entire process is done recursively. To understand the Merge sort algorithm in detail please refer to Merge Sort.
R
merge <- function(a, b) {
temp <- numeric(length(a) + length(b))
astart <- 1
bstart <- 1
j <- 1
for(j in 1 : length(temp)) {
if((astart <= length(a) &&
a[astart] < b[bstart]) ||
bstart > length(b)) {
temp[j] <- a[astart]
astart <- astart + 1
}
else {
temp[j] <- b[bstart]
bstart <- bstart + 1
}
}
temp
}
mergeSort <- function(arr) {
if(length(arr) > 1) {
mid <- ceiling(length(arr)/2)
a <- mergeSort(arr[1:mid])
b <- mergeSort(arr[(mid+1):length(arr)])
merge(a, b)
}
else {
arr
}
}
arr <- sample(1:100, 10)
result <- mergeSort(arr)
result
|
Output
[1] 6 8 16 19 21 24 35 38 74 90
Quick Sort
This is a divide and conquers algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. Pivot can be random. To understand the Merge sort algorithm in detail please refer to Quick Sort.
R
quickSort <- function(arr) {
random_index <- sample(seq_along(arr), 1);
pivot <- arr[random_index]
arr <- arr[-random_index]
left <- c()
right <- c()
left<-arr[which(arr <= pivot)]
right<-arr[which(arr > pivot)]
if (length(left) > 1)
{
left <- quickSort(left)
}
if (length(right) > 1)
{
right <- quickSort(right)
}
return(c(left, pivot, right))
}
arr <- sample(1:100, 10)
result <- quickSort(arr)
result
|
Output:
[1] 13 18 21 38 70 74 80 83 95 99
Please Login to comment...