Data Structures and Algorithms

I provided the code and explanation for three fundamental sorting methods that are essential to understand sorting and how it functions. These types of sorting are commonly asked in coding rounds and interviews, and people often have difficulty understanding them. Therefore, it is crucial to grasp the concept and retain the logic.

Happy Learning!

1. SELECTION SORT:

#include <bits/stdc++.h>
using namespace std;

void selection_sort(int arr[], int n)
{
    for (int i = 0; i <= n - 2; i++)
    {
        int mini = i;

        for (int j = i; j <= n - 1; j++)
        {
            if (arr[j] < arr[mini])
            {
                mini = j;
            }
        }
        swap(arr[mini], arr[i]);
    }
}

int main()
{
    int n;
    cout << "Enter n" << endl;
    cin >> n;

    int arr[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    selection_sort(arr, n);
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    return 0;
}

Explanation of the code:

This code is a program that sorts an array of integers using the selection sort algorithm. The program first includes the "bits/stdc++.h" header file and uses the "std" namespace. The program then defines a function called "selection_sort" that takes in two parameters: an array of integers called "arr" and an integer called "n" which represents the number of elements in the array. The function uses the selection sort algorithm to sort the elements of the array in ascending order. The outer for loop starts at the first element of the array and goes till the second last element of the array. Inside the outer loop, there is an inner loop that starts at the current element of the outer loop and goes till the last element of the array. In the inner loop, the variable "mini" is used to keep track of the position of the smallest element found so far. For each iteration of the inner loop, the current element is compared with the element at the "mini" position. If the current element is smaller, the value of "mini" is updated to the current position.

After the inner loop, the element at the "mini" position is swapped with the element at the current position of the outer loop. The main function then prompts the user to enter the number of elements in the array, and takes input for the elements. It then calls the selection_sort function and prints the sorted array. The program ends by returning 0 to indicate successful execution.

2. BUBBLE SORT:

#include <bits/stdc++.h>
using namespace std;

void bubble_sort(int arr[], int n)
{
    for (int i = n - 1; i >= 0; i--)
    {
        int isSwap = 0;
        for (int j = 0; j <= i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j + 1], arr[j]);
                isSwap = 1;
            }
        }
        if (isSwap == 0)
        {
            break;
        }
        cout << "runs\\n"; //to check whether the swapping was done or not
    }
}

int main()
{
    int n;
    cout << "Enter n" << endl;
    cin >> n;

    int arr[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    bubble_sort(arr, n);
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    return 0;
}

Explanation: This code is a function called "bubble_sort" that takes in two parameters: an array of integers called "arr" and an integer called "n" which represents the number of elements in the array. The function uses the bubble sort algorithm to sort the elements of the array in ascending order. The outer for loop starts from the last element of the array and goes till the first element of the array. The inner for loop starts at the first element of the array, and goes till one element before the current element of the outer loop.

In the inner loop, if the current element is greater than the next element, the two elements are swapped using the "swap" function. A variable called "isSwap" is set to 1 to indicate that a swap has occurred.

After the inner loop, if no swaps have occurred, the function breaks out of the outer loop because the array is already sorted. The function also prints "runs" at the end of each outer loop iteration.

3. INSERTION SORT:

#include <bits/stdc++.h>
using namespace std;

void insertion_sort(int arr[], int n)
{
    for (int i = 0; i <= n - 1; i++)
    {
        int j = i;
        while (j > 0 && arr[j - 1] > arr[j])
        {
            swap(arr[j - 1], arr[j]);
            j--;
            cout << "runs\\n"; 
        }
    }
}

int main()
{
    int n;
    cout << "Enter n" << endl;
    cin >> n;

    int arr[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    insertion_sort(arr, n);
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    return 0;
}

Explanation: This code is a program that sorts an array of integers using the insertion sort algorithm. The program first includes the "bits/stdc++.h" header file and uses the "std" namespace. The program then defines a function called "insertion_sort" that takes in two parameters: an array of integers called "arr" and an integer called "n" which represents the number of elements in the array. The function uses the insertion sort algorithm to sort the elements of the array in ascending order. The outer for loop starts at the first element of the array and goes till the last element of the array. Inside the outer loop, there is a while loop that starts at the current position of the outer loop and goes backward till the beginning of the array.

In the while loop, if the previous element is greater than the current element, the two elements are swapped using the "swap" function. The while loop continues to iterate till the current position becomes 0 or the previous element is less than or equal to the current element.

The main function then prompts the user to enter the number of elements in the array, and takes input for the elements. It then calls the insertion_sort function and prints the sorted array. The function also prints "runs" after each swap. The program ends by returning 0 to indicate successful execution.

NOTE: Perform a dry run of the following codes to gain a better understanding of how these methods operate.