Sorting Algorithms For Efficient Data Organization

What is Sorting?

Sorting is a fundamental mathematical operation that involves arranging or rearranging a collection of items in a specific order. The primary goal of sorting is to impose a linear order on a list or array of elements based on certain criteria. This ordered arrangement facilitates efficient searching, retrieval, and manipulation of data.

Types of sorting

• Internal sorting: Internal sorting refers to sorting records or elements within the main memory of a computer system. This means the entire dataset, including all the records to be sorted, resides in the RAM or primary storage.
• External sorting: External sorting involves sorting records that exceed the capacity of the main memory. In this scenario, some records are stored in external memory, such as disk drives, while portions of the data are brought into the main memory for sorting.

Sorting Algorithms

• Exchange Sort:
  Exchange sort, also known as swapping sort, involves comparing pairs of elements in a list and swapping them if they are in the wrong order. The process continues until the entire list is sorted. Prominent examples of exchange sort algorithms include Bubble Sort and Quick Sort.
• Selection Sort:
  Selection sorting involves dividing the list into a sorted and an unsorted region. The algorithm iteratively chooses the smallest (or largest) element from the portion of the collection that is yet to be sorted, relocating it to its appropriate position within the already sorted portion. Selection Sort and Heap Sort are examples of selection sort algorithms.
• Insertion Sort:
  Insertion sort builds the sorted list one element at a time by considering each element and inserting it into its correct position relative to the already sorted elements. Insertion Sort and Merge Sort are examples of insertion sort algorithms.

Bubble sort:

In Bubble Sort, the algorithm traverses the list in successive iterations, inspecting neighboring elements and exchanging them if their order is incorrect. This process continues until a pass through the list occurs without any further swaps, indicating the attainment of a sorted arrangement.

Algorithm:Compare the first two elements. If they are in the wrong order, swap them.Move to the next pair of elements and repeat the comparison and swapping.Continue this process for the entire list in multiple passes until no more swaps are required.

Efficiency

This algorithm is good for a small number of elements, usually less than 100. Conversely, it is not an efficient algorithm for large datasets. The Time complexity is O(n^2) .

Code Implementation:

#include <iostream>

// Function to swap two integers
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp; 
}

void bubbleSort(int arr[], int n) {
    bool swapped;

    for (int i = 0; i < n - 1; i++) {
        swapped = false;

        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Use the swap function to swap arr[j] and arr[j+1]
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // If no two elements were swapped in the inner loop, the array is already sorted.
        if (!swapped) {
            break;
        }
    }
}

int main() {
    int arr[] = {59, 22, 81, 13, 24, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original Array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }

    bubbleSort(arr, n);

    std::cout << "\nSorted Array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }

    return 0;
}

Output of code:

Original Array: 59 22 81 13 24 11 90  
Sorted Array: 11 13 22 24 59 81 90

Insertion Sort:

It sorts a list of records by inserting a new element into an existing sorted list. The array is virtually divided into sorted and unsorted lists. An initial list with only one item is considered a sorted list.

Algorithm

• The algorithm iterates through the array, comparing each element to its predecessors.
• If the current element is smaller than its predecessor, it is compared to elements before it and larger elements are shifted to the right to make space for the current key.
• This process continues until the key is in its correct position in the sorted portion of the array.
• The algorithm repeats this process for each element, gradually building the sorted array.

Code implementation:

#include <iostream>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        //Shift elements in the range of arr[0..i-1] that are greater than 
        //the specified key to a position one step ahead of their current  location.    

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {87, 65, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original Array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }

    insertionSort(arr, n);

    std::cout << "\nSorted Array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }

    return 0;
}

Output:

Original Array: 87 65 25 12 22 11 90 
Sorted Array: 11 12 22 25 65 87 90

Efficiency:
No of comparisons:

• Best case: n – 1
• Worst case: n2/2 + O(n)
• Average case: n2/4 + O (n)

No of assignments (movements)

• Best case: 2*(n-1)
• Worst case: n^2/2+O(n)
• Average Case : n^2/4 + O(n)

Hence running time of insertion sort is O(n^2) in the worst and average case and O(n) in the best case, and the space requirement is O(1)

Advantages:

• It is an excellent method whenever a list is nearly in the correct order, and few items are removed from their correct locations.
• Since there is no swapping, it is twice as faster as bubble sort.

Disadvantage:

• It makes a large amount of shifting of sorted elements when inserting later elements.

Selection Sort:

The selection sort algorithm sorts a list by selecting successive elements in order and placing them into their proper sorted positions.

Algorithm

• The entire list is scanned sequentially for the first position in the sorted list. You search the whole list, find the lowest value, and place it in the first position.
• The entire list is scanned sequentially for the second position in the sorted list. You search the whole list, find the lowest value, and place it in the second position.
• The whole process is repeated until the entire list is sorted.

Code Implementation:

#include <iostream>

void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap the minimum element with the current element
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int size = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original array: ";
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    selectionSort(arr, size);

    std::cout << "Sorted array: ";
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Efficiency:
No of comparisons:

• Best, average and worst case: n(n – 1)/2

No of assignments (movements)

• Best, average and worst case: 3(n – 1)
  total: n – 1 swaps
  If we include a test to prevent interchanging an element with itself, the number of interchanges in the best case would be O.

Hence running time of the selection sort is O(n^2), and additional space requirements are O(1).

Advantages:

• It is the best algorithm for data movement.
• An element that is in its correct final position will never be moved.

Disadvantages:

• In the case of several comparisons, it pays no attention to the original ordering of the list. For a list that is nearly correct to begin with, the selection sort is slower than the insertion sort.

Thank you for reading this article. Please consider subscribing if you loved it.