Linear sort

Introduction:

This is a comparison based sort where we swap the largest element in the array a[0 .. n-1] with a[n-1] and recurrsively do the same for array a[0 .. n-2] (i.e., excluding the largest element and taking array of size n-1) . Do this till we have only one element left a[0].

Problem Statement:

Sort an array of n integers

Algorithm

1. we have an array of n numbers.

2. In this method we bubble large numbers to right side.... ( to get sorted array in ascending order )

3. In first iteration we compare adjacent numbers and swap larger to right.

i.e., for i = 0 to size of n-1 if a[i] > a[i+1] then swap(a[i], a[i+1]) after this iteration we see that the largest number in the array will be at the right end.

4. Now repeat the above iteration again with one less array size ...we will see that second largest will be at the second position from the end ...

5.we repeat the above step untill array size is 0

6. After all iterations the array will be sorted.

Pseudo code :

linear_sort(a[], n):
    if n == 1:
        return
    max = a[n-1]
    for i = 0 to n-1:
        if a[i] > max:
            swap(a[i], a[n-1])
    linear_sort(a, n-1)

Code :

    #include <bits/stdc++.h>
    using namespace std;
    
    
    void linear_sort(int a[], int n)
    {
        // if size 1 return
        if (n == 1)
        {
            return;
        }
        int max = a[n - 1];
        // Assume last element is max
        for (int i = 0; i < n - 1; i++) // from 0 to i-2 (inclusive)
        {
            if (a[i] > max) // compare every element with last i.e max and swap if greater.
            {
                max = a[i];
                swap(a[i], a[n - 1]);
            }
        }
        linear_sort(a, n - 1);//sort the n-1 size array
    }
    
    
    int main()
    {
        int n;
        cout << "Enter n: ";
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        linear_sort(a, n);
        for (int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        printf("\n");
    }

Complexity Analysis :

Time complexity is \(O(n^2)\) since \(O(n)\) is for n recursions and O(n) is for find maximum element each time