Understanding Sorting Algorithms

Introduction

In computer science, sorting algorithms are fundamental tools that let us arrange elements in either numerical or alphabetical order. They act as the basic instructions for arranging disordered material into logical sequences. We shall go into the world of sorting algorithms in this post and examine their importance, guiding principles, and classifications. We will start by comprehending the fundamentals of sorting and the importance of efficiency when working with enormous datasets. From there, we’ll look at different sorting strategies, from the straightforward Bubble Sort to the effective Quick Sort. You will have a firm understanding of how these algorithms operate and how they can be used to enhance the functionality of computer programmes by the time this article is finished.

Sorting Algorithms

A Sorting Algorithm is used to rearrange a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.

In computer science, a sorting algorithm is like a recipe that helps us organize a list of things in a particular order. The most common orders are either from smallest to largest or from largest to smallest. It’s important to sort things efficiently because it helps other computer programs work faster and do their jobs better.

Imagine you have a bunch of numbers or words all mixed up in a list, and you want to put them in order. A sorting algorithm helps you do that automatically. It takes the messy list and gives you a new list where the elements are arranged from smallest to largest or largest to smallest, depending on what you want.

When a sorting algorithm works, it follows two important rules:

1. The elements in the new list are arranged in a specific order. For example, if you’re sorting numbers, each number is either bigger or equal to the previous number in the list. If you’re sorting words, they are put in alphabetical order.
2. The new list has the same items as the original list, but they are rearranged. None of the items are added or removed.

To sort things quickly, it’s better to have the original list stored in a way that allows us to easily jump to any item, instead of going through them one by one. It’s like having a recipe book with an index, so you can quickly find the page you need, rather than flipping through every page until you find what you’re looking for.

So, a sorting algorithm is a way to organize a list of things, like numbers or words, in a specific order. It helps other programs run faster, and it works best when the original list is stored in a way that allows easy access to any item.

Classification

1. Computational complexity: Sorting algorithms can be classified based on how efficient they are. We measure efficiency by looking at how the algorithm’s performance changes as the size of the list to be sorted increases. We want sorting algorithms that perform well as the list gets larger.
2. Swaps and memory usage: Some sorting algorithms can sort a list by rearranging the elements within the list itself, without needing additional memory. This is called an “in-place” algorithm. Other algorithms might need extra memory to perform the sorting.
3. Recursion: Sorting algorithms can be recursive or non-recursive. Recursive algorithms break down the sorting problem into smaller sub-problems and solve them recursively. Non-recursive algorithms don’t use this approach.
4. Stability: When sorting elements, it’s important to maintain the relative order of items with equal values. For example, if you have two cards with the same rank, a stable sorting algorithm will keep them in the same order they were in before sorting.
5. Comparison sort: Some sorting algorithms compare elements in pairs to determine their order. They use a comparison operator (like “greater than” or “less than”) to make these comparisons.
6. General method: Sorting algorithms can use different techniques to sort elements, such as inserting elements into their correct positions, exchanging elements, selecting elements, or merging different parts of the list.
7. Serial or parallel: Sorting algorithms can be designed to work on a single computer processor (serial) or on multiple processors simultaneously (parallel).
8. Adaptability: Some sorting algorithms can take advantage of the initial order of the elements in the list to improve their performance. They are considered “adaptive” algorithms.
9. Online: An online sorting algorithm can continuously sort a list as new elements are added to it. It can handle a constant stream of incoming data.

Sorting algorithms can be classified based on different factors:

• Some algorithms rearrange the items within the list itself, while others need extra memory to do the sorting.
• Some algorithms use a step-by-step process, where they compare two items at a time and decide their order. This is like comparing two numbers and deciding which one is bigger or smaller.
• There are different ways to approach sorting, like inserting items into their correct positions, swapping items, or selecting items one by one.
• Some algorithms are designed to work on one computer processor, while others can work on multiple processors at the same time.
• Stability is a concept where equal items are sorted while preserving their original order. For example, if you have two cards with the same rank, a stable sorting algorithm will keep them in the same order they were in before sorting.

Sorting algorithms can be complex, but the main idea is to have a way to organize a list of things efficiently. The specific algorithm used depends on factors like the size of the list, the available memory, and the desired outcome.

Bubble sorting

is the most straightforward sorting algorithm that functions by repeatedly switching nearby elements if they are in the wrong order. Large data sets should not be used with this approach due to its high average and worst-case time complexity.

1. Start from the first element (index 0) and compare it with the next element (index 1).
2. If the first element is greater than the second element, swap them.
3. Move to the next pair of elements (index 1 and index 2) and compare them.
4. Continue this process for the entire list, comparing and swapping adjacent elements if necessary.
5. After the first pass through the list, the largest element will “bubble up” to the last position in the list.
6. Repeat the above steps for the remaining unsorted portion of the list (excluding the last position, as it is already in its correct sorted position).
7. Continue this process for multiple passes until the entire list is sorted.

Algorithm

Code

#include <stdio.h>

// Function to perform bubble sort
void bubbleSort(int arr[], int n) {
    // Outer loop to control the number of passes through the array
    for (int i = 0; i < n - 1; i++) {
        // Assume that the array is sorted initially for each pass
        int sortedFlag = 1;

        // Inner loop to compare adjacent elements and swap them if necessary
        for (int j = 0; j < n - 1 - i; j++) {
            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                // Swap the elements if they are in the wrong order
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                // Set the sortedFlag to 0 indicating that a swap occurred
                sortedFlag = 0;
            }
        }

        // If no swap occurred in this pass, the array is already sorted, and we can terminate early
        if (sortedFlag == 1) {
            break;
        }
    }
}

// Function to print the array elements
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Example usage
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Unsorted array: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Output

Selection sort

Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.

The algorithm repeatedly selects the smallest element from the unsorted portion of the list and swaps it with the first element of the unsorted part. This process is repeated for the remaining unsorted portion until the entire list is sorted.

Pseudocode

We can say mainly it’s two steps

1. Find minimum value
2. swapping

Algorithm

1. Start with the first element as the minimum (assuming it is the smallest).
2. Compare this element with the rest of the elements in the array to find the actual minimum element in the unsorted portion of the array.
3. Swap the minimum element found in Step 2 with the first unsorted element (the element at the current starting position).
4. Move the starting position of the unsorted portion to the right (increase the index by 1).
5. Repeat steps 1 to 4 until the entire array is sorted.

• The entire array is iterated over from index 0 to 4 sequentially for the first position in the sorted array. After going through the entire array, it is evident that 11 is the lowest value at the first place, where 64 is now stored. Therefore, swap out 64 for 11. 11 tends to show up in the top spot of the sorted list after one iteration, despite being the least value in the array.

• Repeat the sequential traversal of the rest of the array for the second place, where 25 is present. After traversing the array, we discovered that 12 is the second-lowest value and that it belongs in the second position, therefore we switched these values.

• Next, identify the third least value in the array where 25 is once more present by traversing the remaining elements of the array. Since 22 was found to be the third least value during traversal and should be in the third position in the array, swap 22 with the element currently in the third position.

• In a similar manner, for position four, search the remaining elements of the array to identify the fourth least element. 25 will come in fourth place because it is the fourth-lowest value.

• Finally, the array’s greatest value is automatically positioned in the final position. The array that is produced is the sorted array.

Code

#include <stdio.h>

// Function to perform selection sort
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Assume the current element is the minimum
        int minIndex = i;

        // Find the index of the minimum element in the unsorted part of the array
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                // If a smaller element is found, update minIndex
                minIndex = j;
            }
        }

        // Swap the minimum element with the first unsorted element
        // The first unsorted element is at index 'i'
        // The minimum element is at index 'minIndex'
        // This step places the minimum element in its correct position in the sorted part
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

// Function to print the array elements
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Example usage
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Unsorted array: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Output

Quick Sort

You pick a number randomly and start arranging all numbers less than that number on the left, all the numbers bigger than that number on the right, and do that same until you sort all array

Algorithm

1. Swap function
2. Quick sort
3. Quick sort recursion
4. Partition function

Quick sort recursion function algorithm

• Put the base condition
• Bringing the value of the pivot_index by calling the Partition function
• Calling itself with the left array
• Calling itself with the right part of the array

Partition function algorithm

1. The Partition the function is used to partition the array for QuickSort. It takes an array arr, and two indices low and high, which defines the range of the array that needs to be partitioned.
2. In Step 1, the pivot is chosen. In this example, we select the last element of the array as the pivot, but you can choose the pivot using different techniques, like selecting it randomly.
3. In Step 2, we initialize the variable i to low - 1. i will represent the index of the smaller element in the array.
4. In Step 3, we loop over the array from the index low to high - 1. If an element at the index j is smaller than or equal to the pivot, we increment i and swap the element at the index i with the element at the index j. This step moves smaller elements to the left side of the pivot.
5. After the loop in Step 4, i + 1 will be the correct index for the pivot. We swap the element at the index i + 1 with the pivot element (which is at the index high), placing the pivot in its correct sorted position.
6. In Step 5, we return the index i + 1, which is the index of the pivot in the sorted array. The array is now partitioned with smaller elements to the left of the pivot and larger elements to the right.

Implementation

#include <stdio.h>

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

// Function to perform the partition step
int partition(int arr[], int low, int high) {
    // Choose the pivot element (in this case, we choose the last element as the pivot)
    int pivot = arr[high];
    
    // Initialize the index of the smaller element
    int i = low - 1;

    // Loop over the array to partition it
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i = i + 1;
            // Swap arr[i] and arr[j] since arr[j] belongs to the left partition
            swap(&arr[i], &arr[j]);
        }
    }

    // After the loop, 'i + 1' will be the correct index for the pivot
    // Swap arr[i + 1] and pivot (arr[high]) to place the pivot in its correct position
    swap(&arr[i + 1], &arr[high]);

    // Return the index 'i + 1' which is the index of the pivot in the sorted array
    return i + 1;
}

// Function to perform QuickSort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Perform the partition step to get the correct position of the pivot
        int pivotIndex = partition(arr, low, high);

        // Recursively sort the left and right partitions
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// Function to print the array elements
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Example usage
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Unsorted array: ");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Output

insertion sort

is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

insertion sort Algorithm

To sort an array of size N in ascending order iterate over the array and

1. compare the current element (key) to its predecessor
2. if the key element is smaller than its predecessor
3. compare it to the elements before.
4. Move the greater elements one position up to make space for the swapped element.

How it work

Let’s have an array. First

• The array’s first two members are initially compared using an insertion sort.
• Since 12 is greater than 11, they are not arranged in ascending order, and 12 is not in the proper place. So, change 11 and 12. Therefore, 11 is currently kept in a sorted sub-array.

• Next Pass: Move on to the following two components and compare them now.
• Here, 13 is greater than 12, therefore both items appear to be in ascending order; as a result, there won’t be any switching. Third Pass: 12 is also kept in a sorted sub-array with 11 Fourth Pass:
• Now, 11 and 12 are the only two elements in the sorted sub-array. Moving on to the following two components, which are 13 and 5,

• Change 5 and 13 because they aren’t both in the right spot.

• Elements 12 and 5 are no longer sorted after the swap; thus, swap once more.

• Again, in this case, 11 and 5 are not sorted, so swap once more.

• Here, position 5 is correct Fourth Pass: Currently, the elements in the sorted sub-array are 5, 11, and 12. The following two components are 13 and 6
• They are obviously not sorted, so shift between them both.

• Now that 6 is less than 12, switch once more.

• Here, also swapping makes 11 and 6 unsorted hence, swap again

• Finally, the array is completely sorted.

Implementation

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, j, key;

    // Iterate over the array starting from the second element
    for (i = 1; i < n; i++) {
        // Store the current element to be inserted into the sorted part of the array
        key = arr[i];

        // Find the correct position (index) in the sorted part of the array to insert the key
        j = i - 1;

        // Move elements greater than the key to the right
        // until we find the correct position for the key
        while (j >= 0 && key < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }

        // Insert the key in its correct position
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    // Call the Insertion Sort function
    insertionSort(arr, n);

    printf("\nSorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Output

If you’re eager to delve into the job market, check out the website to review requirements, qualifications, and salary information. Take a glimpse into your potential future.

Remote Rocketship

Feel free to connect 🌹me on:

Twitter

Linkedin

Github

Sincerely, Noran🌹