Sorting Algorithms: Dive into the World of Efficient Data Organisation
Sorting Algorithms: Dive into the World of Efficient Data Organisation
Sorting algorithms are a fundamental concept in computer science. They organise data in a specific order, making it easier to access and search. There are various sorting algorithms, each with advantages and disadvantages. This blog post will deeply dive into some of the most popular sorting algorithms and provide code examples using JavaScript, Python, and Go.
Bubble Sort
Bubble sort is a simple sorting algorithm first described in 1956 by computer scientist John von Neumann. It is also known as sinking sort or exchange sort. The algorithm works by repeatedly comparing adjacent elements in the list and swapping them if they are in the wrong order. The pass through the list is repeated until no more swaps are needed, indicating that the list is sorted. Bubble sort has a time complexity of O(n^2), which makes it less efficient than other sorting algorithms, such as merge sort and quick sort. Despite its inefficiency, bubble sorting is still a fundamental concept in computer science and can help sort small or partially sorted lists.
Here is an example of bubble sort in JavaScript:
function bubbleSort(arr) {
let len = arr.length
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
let arr = [5, 3, 8, 4, 2]
console.log(bubbleSort(arr))And here is the same algorithm implemented in Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
arr = [5, 3, 8, 4, 2]
print(bubble_sort(arr))
Lastly, let’s take a look at bubble sort in Go:
package main
import "fmt"
func bubbleSort(arr []int) []int {
n := len(arr)
for i := 0; i < n; i++ {
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}
func main() {
arr := []int{5, 3, 8, 4, 2}
fmt.Println(bubbleSort(arr))
}
Merge Sort
Merge sort is a sorting algorithm that was first proposed by John von Neumann in 1945. It is a divide-and-conquer algorithm that works by dividing the list into smaller sub-lists, sorting those sub-lists, and then merging them back together. The algorithm has a time complexity of O(n log n) and is highly efficient, making it a popular choice for sorting large data sets. The algorithm works by recursively dividing the list into two halves until there is only one element left in each half. The two halves are then merged back together in a sorted order. Merge sort was one of the first sorting algorithms to have a time complexity that was faster than O(n^2), which made it a significant breakthrough in the field of computer science.
Here is an example of merge sort in JavaScript:
function mergeSort(arr) {
if (arr.length < 2) return arr
const middle = Math.floor(arr.length / 2)
const left = arr.slice(0, middle)
const right = arr.slice(middle)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
const result = []
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result.concat(left, right)
}
let arr = [5, 3, 8, 4, 2]
console.log(mergeSort(arr))Now let’s take a look at merge sort in Python:
def merge_sort(arr):
if len(arr) < 2:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
return merge(merge_sort(left), merge_sort(right))
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
arr = [5, 3, 8, 4, 2]
print(merge_sort(arr))
Lastly, let’s take a look at merge sort in Go:
package main
import "fmt"
func mergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
middle := len(arr) / 2
left := arr[:middle]
right := arr[middle:]
return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) []int {
result := make([]int, 0)
for len(left) > 0 && len(right) > 0 {
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
}
result = append(result, left...)
result = append(result, right...)
return result
}
func main() {
arr := []int{5, 3, 8, 4, 2}
fmt.Println(mergeSort(arr))
}
Quick Sort
Quick sort is a sorting algorithm that was first proposed by British computer scientist Tony Hoare in 1959. It was later published as a paper in 1961 and is now widely used in computer science. The algorithm works by selecting a “pivot” element from the list and partitioning the other elements into two sub-lists, according to whether they are less than or greater than the pivot. The sub-lists are then recursively sorted. Quick sort is an efficient sorting algorithm with an average time complexity of O(n log n) and can be faster than other sorting algorithms such as merge sort and heap sort in certain circumstances.
Here is an example of quick sort in JavaScript:
function quickSort(arr) {
if (arr.length < 2) return arr
const pivot = arr[0]
const left = []
const right = []
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat(pivot, quickSort(right))
}
let arr = [5, 3, 8, 4, 2]
console.log(quickSort(arr))Now let’s take a look at quick sort in Python:
def quick_sort(arr):
if len(arr) < 2:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
arr = [5, 3, 8, 4, 2]
print(quick_sort(arr))
Lastly, let’s take a look at quick sort in Go:
package main
import "fmt"
func quickSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
pivot := arr[0]
left := make([]int, 0)
right := make([]int, 0)
for i := 1; i < len(arr); i++ {
if arr[i] < pivot {
left = append(left, arr[i])
} else {
right = append(right, arr[i])
}
}
left = quickSort(left)
right = quickSort(right)
return append(append(left, pivot), right...)
}
func main() {
arr := []int{5, 3, 8, 4, 2}
fmt.Println(quickSort(arr))
}
Conclusion
Sorting algorithms are a crucial concept in computer science, used to organize data in a specific order. In this blog post, we delved into three popular sorting algorithms: bubble sort, merge sort, and quick sort. We provided code examples for each algorithm using JavaScript, Python, and Go. By comprehending the various types of sorting algorithms and their implementation, you ca