Selection sorting Dynamically

Worst-Complexity: n ^ 2

Average-Complexity: n ^ 2

Best-Complexity: n ^ 2

Space-Complexity:  1

#include<iostream>
using namespace std;

/*********************sorting function********************/

void selection_Sort(int arr[], int n)
{
    int i, j, min;

    for (i = 0; i < n-1; i++)
    {
        min = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min])
            min = j;

          swap(arr[min],arr[i]);
    }
} 

 /****************** Printing values*****************************/

void print_Array(int arr[], int size) 

{ 

    int i; 

    for (i=0; i < size; i++) 

        cout<<arr[i];

cout<<endl; 

} 

/**********************Driver function*************************/

int main() 

{ 

int *arr;

int n;

cout<<"How many numbers your want to sort:"<<endl;

    cin>>n;

    arr=new int[n];

    cout<<"Enter the numbers:"<<endl;

for(int i=0;i<n;i++)

{

cin>>arr[i];

}    

selection_Sort(arr, n); 

    cout<<"After sorting array: \n"<<endl; 

    print_Array(arr, n); 

    return 0; 

} 

Read More

Quick sorting program

Worse case performance: O(n^2)
Best case performance: O(nlogn)
Average performance: O(nlogn)


#include <iostream>
void quicksort(int arr[],int low,int high);
int partition(int arr[],int low,int high);
using namespace std;
/***********************************/
int partition(int arr[],int low,int high)
{
    int pivot,i;
    pivot=arr[high];
    i=low-1;

    for(int j=low; j<high; j++)
    {
        if(arr[j]<=pivot)
        {
            i++;
            swap(arr[i],arr[j]);
        }
    }
    swap(arr[i+1],arr[high]);
    return(i+1);
}
/*********************************/
void quicksort(int arr[],int low, int high)
{
    if(low<high)
    {
    int pivot;
    pivot=partition(arr,low,high);

    quicksort(arr,low,pivot-1);
    quicksort(arr,pivot+1,high);
    }
}
/*********************************/
int main()
{
    int arr[5]={5,4,3,2,1};
    int n=5;
    cout << "Before sorting values is: ";
    for(int i=0;i<n;i++)
    {
    cout<<arr[i]<<" ";
    }
    quicksort(arr,0,n-1);
    cout<<"\n After sorting: ";
    for(int i=0;i<n;i++)
    {
    cout<<arr[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Read More

Merge sorting program in C++

#include <iostream>

using namespace std;
/****************************************************************************************************/
void merg(int *arr,int first,int last)
{
    int mid=(first+last)/2;
 int i=first;
 int j=mid+1;
 int k=first;
 int temp[100];

    while(i<=mid && j<=last)
    {
        if(arr[i]<arr[j])
            {
            temp[k++]=arr[i++];
            }
        else
            {
                temp[k++]=arr[j++];
            }
    }
        while(i<=mid)
        {
            temp[k++]=arr[i++];
        }
            while(j<=mid)
            {
                temp[k++]=arr[j++];
            }
    for(int i=first;i<=last;i++)
    {
        arr[i]=temp[i];
    }
}
/*********************************************************************************************************/
void mergesort(int arr[],int first,int last)
{
    if(first>=last)
    {
        return;
    }

    int mid=(first+last)/2;

    mergesort(arr,first,mid);
    mergesort(arr,mid+1,last);

    merg(arr,first,last);
}
/**************************************************************************************************************/

int main()
{
    int arr[100];
    int n;
    cout<<"Enter number of elements in array:"<<endl;
    cin>>n;
    cout<<"Enter numbers to be sort:"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    mergesort(arr,0,n-1);
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    return 0;
}

Read More

Insertion sorting using pointers and function

Write a program for insertion sorting. 

 

#include <iostream>

using namespace std;

void insertionSort(int *p,int size);

void insertionSort(int *p,int size)

{

    int i,j,temp;

    for(i=1;i<size;i++)

    {

        temp=p[i];

        j=i-1;

        while(j>=0 && p[j]>temp)

        {

            p[j+1]=p[j];

        j--;

        }

        p[j+1]=temp;

    }

    for(i=0;i<size;i++)

    {

        cout<<p[i]<<" ";

    }

}

int main()

{

    int n;

    int *p;

    cout<<"Enter number of element you want to store in an a array:"<<endl;

    cin>>n;

    p=new int[n];

    cout<<"Now enter the values"<<endl;

    for(int i=0;i<n;i++)

    {

        cin>>p[i];

    }

    insertionSort(p,n);

}

Insertion sorting using pointers and function

Checkout more java programs on Zamacodes.com

         

Read More