8 FAQ Sorting Algorithms Bubble,Insertion,Selection,Pancake,Quick,Merge,Heap & Tree Sorting

1st program Contains Bubble,Insertion,Selection,Pancake Sorting

#include

/* Function to reverse arr[] from start to end*/
void rvereseArray(int arr[], int start, int end)
{

int temp;
while(start < end)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

/* Utility that prints out an array on a line */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);

printf("\n");
}

int get(int ar[],int i)
{

return ar[i];

}

int length(int ar[])
{
return (sizeof(ar)/sizeof(int));
}


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

for( i = 1; i < n; i++ )
{
int index = i;
for( j = i-1; j >= 0; j-- )
{
if( arr[j] > arr[index] )
{
rvereseArray(arr, j, index);
index = j;
}
}
}

}

void swap(int a[],int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;

}
void select_sort(int a[],int n)
{
/* a[0] to a[n-1] is the array to sort */
int iPos;
int iMin,i;

/* advance the position through the entire array */
/* (could do iPos < n-1 because single element is also min element) */
for (iPos = 0; iPos < n; iPos++)
{
/* find the min element in the unsorted a[iPos .. n-1] */

/* assume the min is the first element */
iMin = iPos;
/* test against all other elements */
for (i = iPos+1; i < n; i++)
{
/* if this element is less, then it is the new minimum */
if (a[i] < a[iMin])
{
/* found new minimum; remember its index */
iMin = i;
}
}

/* iMin is the index of the minimum element. Swap it with the current position */
if ( iMin != iPos )
{
swap(a, iPos, iMin);
}
}


}
void insert_sort(int A[],int n)
{
int i,j,key;

for(j=1;j {
key=A[j];
//> A[ j ] is added in the sorted sequence A[0, .. j-1]
i=j-1;
while(i >= 0 && A [i] > key)
{ A[i+1] =A[i];
i=i-1;
}
A [i+1]=key;
}

}

void bubble_sort(int arr[],int n)//optmized see loop
{
int temp,i,j,k;

for(i=0;i{
for(j=n-1;j>i;j--)
{
if(arr[j-1] >arr[j])
{
temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
for(k=0;k{
printf(" %d \t",arr[k]);
}

printf( " \n " );

}

}



int main()
{
int arb[]={5,2,1,4,3};
int n=5;
int i=0;

bubble_sort(arb,n);

printf("\n\n-- Bubble Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",arb[i]);
}

int ari[]={5,2,1,4,3};

insert_sort(ari,n);

printf("\n\n-- Insertion Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",ari[i]);
}

int ars[]={5,2,1,4,3};

select_sort(ars,n);

printf("\n\n-- Selection Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",ars[i]);
}


int arp[]={5,2,1,4,3};

pancake_sort(arp,n);

printf("\n\n-- Pancake Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",arp[i]);
}


}


Time Complexity O(n^2)
Space Complexity O(1)
Run Here https://ideone.com/clone/5Htf9


2nd program heap Sort 

How heap can be build in O(n)  check this out http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf

#include
#include
using namespace std;

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

class Heap
{
int *arr; // pointer to array of elements in heap
int heap_size;
public:
Heap(int a[], int size);
void buildminHeap();
void minHeapify(int );
void heapSort();
int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;
};

Heap::Heap(int a[], int size) {
heap_size = size;
arr = a;
}



void Heap::minHeapify(int i) {
int l = left(i);
int r = right(i);

printf( "l=%d,r=%d \n ",l,r);

int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
printf(" a[i]=%d \t a[large]=%d", arr[i],arr[largest]);
minHeapify(largest);
}
}

void Heap::buildminHeap() {
int i = (heap_size - 1)/2;
printf( " %d ",i);
while (i >= 0)
{
minHeapify(i);
i--;
}
}
void heapsort(int a[],int n)
{
Heap hp(a, n);
hp.buildminHeap();
int i=0,temp=0;
for (i = n-1; i >= 1; i--)
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
hp.minHeapify(0);
}

}
int main()
{
int k = 4;
int arr[] = {12, 34, 10, 8, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);

heapsort(arr,n);

int i=0;
for(i=0;i printf( " %d ",arr[i]);

getchar();
return 0;
}


Time Complexity O(nlogn)
Space Complexity O(1)
Run here https://ideone.com/tP2z3

3rd program Merge Sort

#include

void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}

void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;

if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);
}
}


void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}



int main()
{

int arr[] = {12, 34, 10, 8, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);
int temp[7];

mergeSort(arr,temp,n);

int i=0;
for(i=0;i printf( " %d ",arr[i]);

getchar();
return 0;
}


Time Complexity O(nlogn)
Space Complexity O(n)
Run here https://ideone.com/ZQImg

4th program Quick Sort

#include "stdio.h"

int split ( int*, int, int ) ;

int main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;

void quicksort ( int *, int, int ) ;

quicksort ( arr, 0, 9 ) ;

printf ( "\nArray after sorting:\n") ;

for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;

}

void quicksort ( int a[ ], int lower, int upper )
{
int i ;
if ( upper > lower )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1 ) ;
quicksort ( a, i + 1, upper ) ;
}
}

int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;

p = lower + 1 ;
q = upper ;
i = a[lower] ;

while ( q >= p )
{
while ( a[p] < i )
p++ ;

while ( a[q] > i )
q-- ;

if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}

t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;

return q ;
}


Time Complexity O(nlogn)
Space Complexity O(logn) if stack space considered else O(1)
Run Here https://ideone.com/clone/YFFWE

5th program BST Sort


#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}

/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

printInorder(root);

getchar();
return 0;
}

Time Complexity O(nlogn)
Space Complexity O(1)
Run here https://ideone.com/tP2z3