Strand Sort in C++

In this tutorial, we will learn about one of the commonly used sorting algorithms i.e. Strand sort in C++ with algorithm. Before this I recommend you to read the tutorial on merge sort. This will help you to understand this algorithm easily.
Strand sort is generally used to sort elements in ascending order.

‘Sorting’ in programming refers to the arrangement of a sequence in either ascending or descending order.
‘Array’ is a data structure used in programming to store multiple variables of the same type.
‘Vectors’ are the dynamic arrays with the capability to resize themselves.

Algorithm for Strand Sort

strand_sort( int n, int a[] )

  1. This function takes input array and it’s size as parameters.
  2. Firstly we create an empty vector, which will store the sorted sequences from the input array.
  3.  And we will mark these elements as taken using flag array.
  4. We will also define an empty output vector.
  5. Then step by step we will take a sorted sequence and merge it with the output vector until all the input elements are taken.
  6. Then we will finally report the output vector.

merge(vector<int>&c)

  1. We will use this function to merge the sorted sequences with the output vector.
  2. We take a sorted sequence as the parameter.
  3. We will define a temporary vector which will be the same as the output vector computed in the previous step.
  4. Then we will set two pointers onto the first elements of the two vectors respectively.
  5. Now we will compare the two pointers and insert the smaller one into the output vector until one of the pointers reaches the end of the vector.
  6. Lastly, we will insert the remaining elements of the vector into the output vector.

Strand Sort in C++

Time Complexity of the Algorithm of Strand Sort in C++

The time complexity of this algorithm will be O(n) in the best case and O(n²) in the worst case.

  • The best-case will be when the input array is already in ascending order.
  • The worst-case will be when the input array is in descending order.

C++ Code for the Algorithm

 

#include<bits/stdc++.h>
using namespace std;
vector<int>b; // output vector

//merge vector c into output vector
void merge( vector<int>&c ){
    vector<int>d;
    d=b;
    b.clear();
    int i = 0, j = 0;  
    while (i<c.size() && j <d.size()) 
    { 
        if (c[i]<d[j]){ 
            b.push_back(c[i]);
            i++;
        } 
        else{
            b.push_back(d[j]);
            j++; 
        }
    } 
    while (i<c.size()){
        b.push_back(c[i]);
        i++;
    }
    while (j<d.size()){ 
        b.push_back(d[j]);
        j++; 
    } 
}

//strand sort function
void strand_sort( int n, int a[] ){
    int flag[n]; //used to mark that this element is in the output vector(1) or not(0)
    memset(flag,0,sizeof(flag)); //sets initially none of the element is in output vector
    int k=n; //used to store how many elements are left in input array
    vector<int>c; //temporary vector used to store sorted sequences from input array
    //this while loop step by step inserts all sorted sequences from
    //input array to output vector
    while(k>0){
        int h=0;
        for(int x=0; x<n; x++){
            if(flag[x]==0&&a[x]>=h){
                k--;
                flag[x]=1;
                c.push_back(a[x]);
                h=a[x];
            }
        }
        merge(c); //used to merge the small sorted sequences into output vector
        c.clear();
    }
}

//driver function
int main()
{
    int n;  //size of the input array
    cin>>n;
    int a[n];  //input array
    for(int x=0; x<n; x++){
        cin>>a[x];
    }
    strand_sort(n,a); //Here we calls the strand sort function
    for(int x=0; x<n; x++){
        cout<<b[x]<<" ";    //output of the final sorted array
    }
    cout<<"\n";
    return 0;
}

Input

5
5 2 4 3 1

Output

1 2 3 4 5

Some other sorting Algorithms

Leave a Reply

Your email address will not be published. Required fields are marked *