Programming Solutions: Sorting

Selection Sort - Implementation with C++

/*  Bismillahir Rahmanir Rahim
    Implementation of Selection-Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int ar[1000], i, j, n, temp, loc, mn;
    cin>>n; // Enter the number of element
    for(i=0; i<n; i++) cin>>ar[i]; // all elements
    for(i=0; i<n-1; i++){
        mn=ar[i]; // let, its the minimum
        loc=i;    // location of minimum
        for(j=i+1; j<n; j++){
            if(ar[j]<mn){
                mn=ar[j]; // minimum updated
                loc=j;    // location of minimum
            }
        }
        temp=ar[i];
        ar[i]=ar[loc];
        ar[loc]=temp;
    }
    for(i=0; i<n; i++) cout<<ar[i]<<" ";
    cout<<endl;
    return 0;
}

Bubble Sort - Implementation with C++

/*  Bismillahir Rahmanir Rahim
    Implementation of Bubble-Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[50],n,i,j,temp;
    cin>>n; // Enter the number of element
    for(i=0; i<n; i++) cin>>a[i]; // Enter all elements
    for(i=1; i<n; i++){
        for(j=0; j<(n-i); j++){
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    for(i=0; i<n; i++) cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

Quick Sort - Implementation with C++

/*  Bismillahir Rahmanir Rahim
    Implementation of Quick-Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;
int ar[1000];

int partition (int low, int high){
    int pivot=ar[high];
    int i=(low-1);
    for(int j=low; j<high; j++){
        if(ar[j]<=pivot){
            i++;
            swap(ar[i],ar[j]);
        }
    }
    swap(ar[i+1], ar[high]);
    return (i+1);
}

void quickSort(int low, int high){
    if(low<high){
        int pi=partition(low, high);
        quickSort(low, pi-1);
        quickSort(pi+1, high);
    }
}

int main(){
    int n,i;
    cin>>n;
    for(i=0;i<n;i++) cin>>ar[i];
    quickSort(0, n-1);
    for(i=0; i<n; i++) cout<<ar[i]<<" ";
    cout<<endl;
    return 0;
}

Merge Sort - Implementation with C++

/*  Bismillahir Rahmanir Rahim
    Implementation of Merge Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;
int ar[1000];

int marg_partition(int st, int mid , int ed){
    int arr[1000], left, right, j=0, i;
    left=st;
    right=mid+1;
    while(left<=mid && right<=ed){
        if(ar[left]<ar[right]){
            arr[j++]=ar[left];
            left++;
        }
        else{
            arr[j++]=ar[right];
            right++;
        }
    }
    if(left>mid){
        for(i=right;i<=ed;i++)
            arr[j++]=ar[i];
    }
    else {
        for(i=left;i<=mid;i++)
            arr[j++]=ar[i];
    }
    for(i=0;i<j;i++) ar[i+st]=arr[i];
    return 0;
}

int marg_sort(int st,int ed){
    if(st<ed){
        int mid=(st+ed)/2;
        marg_sort(st,mid);
        marg_sort(mid+1,ed);
        marg_partition(st,mid,ed);
    }
}

int main(){
    int i,j,n,k;
    cin>>n;
    for(i=0;i<n;i++) cin>>ar[i];

    marg_sort(0,n-1);
    for(i=0;i<n;i++) cout<<ar[i]<<" ";
    cout<<endl;
    return 0;
}

Insertion Sort - C++ Implementation

Try to understand the following procedure.

77 33 44 11 88 22 66 55

33 77 . . . . . . . . . . . . . . . . . .
33 44 77 . . . . . . . . . . . . . . .
11 33 44 77 . . . . . . . . . . . .
11 33 44 77 88 . . . . . . . . .
11 22 33 44 77 88 . . . . . .
11 22 33 44 66 77 88 . . .
11 22 33 44 55 66 77 88

The following Code represent the concept.

/*  Bismillahir Rahmanir Rahim
    Implementation of Insertion Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int ar[100000], n, i, j, key;
    cin>>n;  // number of elements
    for(i=0; i<n; i++) cin>>ar[i]; // input elements one by one
    
    for(i=1; i<n; i++){ // starting from 2nd element
        key=ar[i]; 
        j=i-1; 
        while(j>=0 && key<ar[j]){ //comparing key with all previous
            ar[j+1]=ar[j]; 
            j--;
        }
        ar[j+1]=key; 
    }
    
    for(i=0;i<n;i++) cout<<ar[i]<<" ";
    return 0;
}

Monday, April 24, 2017

Selection Sort - Implementation with C++

Bubble Sort - Implementation with C++

Quick Sort - Implementation with C++

Merge Sort - Implementation with C++

Insertion Sort - C++ Implementation