Sorting Algorithms: Bubble Sort, Merge Sort, and Quick Sort with example

Sorting Algorithms: Bubble Sort, Merge Sort, and Quick Sort

In computer science, sorting is the process of arranging an unsorted collection of data into a particular order. Sorting is a fundamental problem in computer science, and there are many different algorithms for performing this task. Some of the most commonly used sorting algorithms are bubble sort, merge sort, and quick sort.

1.Bubble Sort

Bubble sort is a simple and intuitive sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm continues to iterate through the list until no more swaps are necessary.

Here is the pseudocode for bubble sort:

css
function bubbleSort(arr)
    n = length(arr)
    for i = 0 to n-1
        for j = 0 to n-i-1
            if arr[j] > arr[j+1]
                swap(arr[j], arr[j+1])

The time complexity of bubble sort is O(n^2), which makes it very slow for large datasets. However, it is easy to understand and implement, and it is useful for small datasets.

2. Merge Sort

Merge sort is a divide-and-conquer algorithm that works by dividing the unsorted list into n sublists, each containing one element. It then repeatedly merges the sublists to produce new sorted sublists until there is only one sublist remaining.

Here is the pseudocode for merge sort:

scss
function mergeSort(arr)
    if length(arr) <= 1
        return arr
    
    middle = length(arr) / 2
    left = arr[0:middle]
    right = arr[middle:]
    
    left = mergeSort(left)
    right = mergeSort(right)
    
    return merge(left, right)

function merge(left, right)
    result = []
    
    while length(left) > 0 and length(right) > 0
        if left[0] <= right[0]
            result.append(left[0])
            left = left[1:]
        else
            result.append(right[0])
            right = right[1:]
    
    if length(left) > 0
        result += left
    if length(right) > 0
        result += right
    
    return result

The time complexity of merge sort is O(n log n), which makes it much faster than bubble sort for large datasets. Merge sort is a stable sort, which means that it maintains the relative order of equal elements in the sorted list.

3. Quick Sort

Quick sort is another divide-and-conquer algorithm that works by selecting a "pivot" element from the list and partitioning the other elements into two sublists, according to whether they are less than or greater than the pivot. The algorithm then recursively sorts the sublists.

Here is the pseudocode for quick sort:

css
function quickSort(arr, left, right)
    if left < right
        pivot = partition(arr, left, right)
        quickSort(arr, left, pivot-1)
        quickSort(arr, pivot+1, right)

function partition(arr, left, right)
    pivot = arr[right]
    i = left - 1
    for j = left to right-1
        if arr[j] <= pivot
            i += 1
            swap(arr[i], arr[j])
    swap(arr[i+1], arr[right])
    return i+1

The time complexity of quick sort is O(n log n) on average, but it can be as bad as O(n^2) in the worst case. However, quick sort is often faster than merge sort in practice because of its efficient use of cache memory.

Conclusion

Sorting is a fundamental problem in computer science, and there are many different algorithms for performing this task. Bubble sort, merge sort, and quick sort are just a few examples of the many sorting algorithms that exist. Each algorithm has its own strengths and weaknesses, and the choice of algorithm depends on the specific requirements of the application.

In general, bubble sort is a good choice for small datasets, while merge sort and quick sort are better for large datasets. Merge sort is a stable sort, which means it maintains the relative order of equal elements in the sorted list, while quick sort is not. Quick sort is often faster than merge sort in practice because of its efficient use of cache memory, but it can be as bad as O(n^2) in the worst case.

There are many other sorting algorithms that are used in practice, including insertion sort, selection sort, and heap sort. The choice of sorting algorithm depends on the specific requirements of the application, such as the size of the dataset, the degree of presorting, and the required stability of the sort.

In conclusion, sorting is a fundamental problem in computer science, and there are many different algorithms that can be used to solve it. By understanding the strengths and weaknesses of different algorithms, programmers can choose the right algorithm for the task at hand and optimize the performance of their applications.

Read too: 101 algorithms frequently used in programming and computer science