Welcome back,
This is our fifth and the final module of Data Structures and Algorithms. In our previous module we discussed Tree ADT, Binary Search Tree(BST) implementation, Finding min and max element in a BST, Finding height of BST, BST traversal Breadth first, Depth first, Level order traversal-Preorder, Inorder and PostOrder traversal, Checking whether a Binary tree is BST, Deleting a node from BST concepts.
In this module, we will discuss the following:
5. Algorithms
5.1 Search algorithm:
5.1.1 Linear search
5.1.2 Binary search
5.2 Sort algorithm:
5.2.1 Selection sort
5.2.2 Bubble sort
5.2.3 Insertion sort
5.2.4 Merge sort
5.2.5 Quick sort
5. Algorithms
Lets see some search and sort algorithms.
5.1 Search algorithm:
In this module, we discuss
5.1.1 Linear Search Algorithm and
5.1.2 Binary Search Algorithm
5.1.1 Linear search
Runnable Code Snippet_5.1 – Linear Search
/* 5.1.1 linear search */
#include<iostream>
using namespace std;
int linearSearch(int key,int *arr,int imin,int imax){
for(int i=imin;i<=imax;i++){
if(arr[i]==key)
return i;
}
return -1;
}
int main(){
int*a=NULL;
int num,key,position;
cout<<"hw mny elements: ";
cin>>num;
a=new int; // if pgm crashes,use=> a=new int [num];
for(int i=0;i<num;i++){
cin>>a[i];
}
cout<<"Enter element to search: ";
cin>>key;
position=linearSearch(key,a,0,num-1);
if(position==-1)cout<<"not found\n";
else cout<<key <<" found at "<<"position : "<<position+1<<endl;
return 0;
}
5.1.2 Binary search
Runnable Code Snippet_5.1.2 – Binary Search
/* 5.1.2 binary search */
/*Note: dis can be used only for a SORTED ARRAY*/
#include<iostream>
using namespace std;
int binarySearch(int key,int *arr,int imin,int imax){
int imid;
while(imin<=imax){
imid=(imin+imax)/2;
if(arr[imid]==key)
return imid;
else if(key>arr[imid]){
imin=imid+1;
}
else{
imax=imid-1;
}
}
return -1;
}
int main()
{
int num,key,loc;
cout<<"hw mny elements: ";
cin>>num;
int *a=new int[num];
for(int i=0;i<num;i++){
cin>>a[i];
}
cout<<"Enter element to search: ";
cin>>key;
loc=binarySearch(key,a,0,num-1);
if(loc==-1)
cout<<"not found\n";
else cout<<key<<" found at position: "<<loc+1<<endl;
return 0;
}
5.2 Sort algorithm:
Lets discuss few Sort algorithms now. Their basic concept is
- SelectionSort- find min and swap recursively
- BubbleSort- compare with adjacent element and swap, if greater(bubbles largest number up)
- InsertionSort- imaginary hole, compare hole-1 element with hole value, insert if less
- MergeSort- find mid, recursive Msort(l,mid) Msort(r,n-mid) and merge(left, right arrays)
- QuickSort- partitionIndex, pivot, Partition-swap Partition Index(say,PI) with End, recursive Qsort(start,PI-1) and Qsort(PI+1,End)
5.2.1 Selection sort
To sort using Selection sort method find min and swap recursively
Runnable Code Snippet_5.2.1-a – Selection Sort
/* 5.2.1-a selection sort */
#include<iostream>
using namespace std;
int smallest(int *arr,int imin,int imax){
int small=imin;
for(int i=imin+1;i<=imax;i++){
if(arr[small]>arr[i]){
small=i;
}
}
return small;
}
void Swap(int *arr,int index1,int index2){
int temp;
temp=arr[index1];
arr[index1]=arr[index2];
arr[index2]=temp;
}
void selectionSort(int *arr,int imin,int imax){
int ismall;
for(int i=imin;i<=imax;i++){
ismall=smallest(arr,i,imax);
if(i!=ismall)
Swap(arr,i,ismall);
}
}
int main()
{
int num;
cout<<"how many elements: ";
cin>>num;
int *arr=new int;
cout<<"Enter the numbers:\n";
for(int i=0;i<num;i++){
cin>>arr[i];
}
selectionSort(arr,0,num-1);
cout<<"Sorted list is: \n";
for(int i=0;i<num;i++){
cout<<arr[i]<<" ";
}
return 0;
}
Alternate method to do Selection Sort with Time complexity: O(n2)
Runnable Code Snippet_5.2.1-b – Selection Sort with Time complexity O(n2)
/* 5.2.1-b – Selection Sort */
/* Alternate method with Time complexity: O(n2) */
#include<iostream>
using namespace std;
void selectionSort(int A[],int n){
for(int i=0;i<n-1;i++){ //we need to do n-2 passes
int iMin=i; //ith position elements from i till n-1 are candidates
for(int j=i+1;j<n;j++){
if(A[j]<A[iMin])
iMin=j; //update the index of minimum element
}
int temp=A[i];
A[i]=A[iMin];
A[iMin]=temp;
}
}
int main()
{
int num;
cout<<"How many elements: ";
cin>>num;
int *A=new int; //if pgm crashes, use=> int *A=new int[num];
cout<<"Enter the numbers: \n";
for(int i=0;i<num;i++){
cin>>A[i];
}
//int A[]={2,7,4,1,5,3};
cout<<"Sorted list: ";
selectionSort(A,num);
for(int i=0;i<num;i++){
cout<<A[i]<<" ";
}
return 0;
}
5.2.2 Bubble sort
To sort using BubbleSort- compare elements with adjacent element and swap, if greater(bubbles largest number up)
Runnable Code Snippet_5.2.2-a – Bubble Sort
/* 5.2.2-a bubble sort */
#include <iostream>
using namespace std;
void bubbleSort(int array[], int length)
{
for(int i = 0; i < length - 1; i ++)
{
for(int j = length - 1; j > i; j--)
{
if(array[j-1] > array[j])
{
// Swap elements if the lower-indexed key's value is greater
// than its higher-indexed neighbor
array[j] = array[j-1] + array[j];
array[j-1] = array[j] - array[j-1];
array[j] = array[j] - array[j-1];
}
}
}
}
int main()
{
int array[] = {11, 23, 34, 24, 3, 45, 112, 44, 73, 89};
int length = sizeof(array) / sizeof(int);
bubbleSort(array, length);
for(int i = 0; i < length; i++)
{
cout<<"The "<<i + 1<<"th element is: "<<array[i]<<endl;
}
}
Runnable Code Snippet_5.2.2-b – Bubble Sort( Alternate method )
/* 5.2.2-b- Alternate method to bubble sort */
#include<iostream>
using namespace std;
void bubbleSort(int A[], int n)
{
for(int i = 0; i < n-1; i ++)
{
for(int j = n-1; j > i; j--) // Attention: reverse loop
{
if(A[j-1] > A[j])
{
// Swap elements if the lower-indexed key's value is greater
// than its higher-indexed neighbor
int temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
}
}
}
}
int main()
{
int num;
cout<<"How many elements: ";
cin>>num;
int *A=new int;
cout<<"Enter the numbers: \n";
for(int i=0;i<num;i++){
cin>>A[i];
}
//int A[]={2,7,4,1,5,3};
cout<<"Sorted list: ";
bubbleSort(A,num);
for(int i=0;i<num;i++){
cout<<A[i]<<" ";
}
return 0;
}
5.2.3 Insertion sort
To sort using InsertionSort method -consider an imaginary hole, compare hole-1 element with hole value, insert if less
Runnable Code Snippet_5.2.3 – Insertion sort
/* 5.2.3 Insertion sort */
#include <iostream>
using namespace std;
void InsertionSort(int A[], int n)
{
int i,j;
for(i = 0; i < n; i++){
int temp = A[i];
for(j = i - 1; j >= 0 && A[j] > temp; j--){
A[j + 1] = A[j];
}
A[j + 1] = temp;
}
}
int main()
{
int num;
cout<<"How many elements: ";
cin>>num;
int *A=new int[num];
cout<<"Enter the numbers: \n";
for(int i=0;i<num;i++){
cin>>A[i];
}
cout<<"Sorted list: ";
InsertionSort(A,num);
for(int i=0;i<num;i++){
cout<<A[i]<<" ";
}
return 0;
}
5.2.4 Merge sort
To sort using MergeSort method – find mid element, recursive Msort(l,mid) Msort(r,n-mid) and merge(left, right arrays)
Runnable Code Snippet_5.2.4-a – Merge sort
/* 5.2.4-a merge sort */
#include <iostream>
#include <stdlib.h>
using namespace std;
void Merge( int *A,int *L,int *R,int lCount,int rCount )
{
int i=0,j=0,k=0;
while(i<lCount && j<rCount)
{
if(L[i] < R[j])
A[k++] = L[i++];
else
A[k++] = R[j++];
}
while(i<lCount)
A[k++] = L[i++];
while(j<rCount)
A[k++] = R[j++];
}
void MergeSort(int *A,int n)
{
int mid,*L,*R;
if(n<2) return;
mid = n/2;
L = (int *)malloc(mid*sizeof(int));
R = (int *)malloc((n-mid)*sizeof(int));
for(int i=0;i<mid;i++)
L[i] = A[i];
for(int i=mid;i<n;i++)
R[i-mid] = A[n-i];
MergeSort(L,mid);
MergeSort(R,n-mid);
Merge(A,L,R,mid,n-mid);
}
int main(int argc, char* argv[])
{
int arr[] = {6,32,56,15,34,7,1,54,87,63,4,3};
int n = sizeof(arr)/sizeof(arr[0]);
MergeSort(arr,n);
for(int i=0;i<n;i++)
cout<< arr[i] << endl;
return 0;
}
Runnable Code Snippet_5.2.4-b – Merge sort( Alternate method)
/* 5.2.4-b - Merge sort( Alternate method) */
#include<iostream>
using namespace std;
void Merge(int a[], int l[], int lc, int r[], int rc)
{
int i=0, j=0, k=0;
while(i<lc&&j<rc)
{
if(l[i]<r[j])
{
a[k]=l[i];
k++;
i++;
}
else
{
a[k]=r[j];
k++;
j++;
}
}
while(i<lc)
{
a[k++]=l[i++];
}
while(j<rc)
{
a[k++]=r[j++];
}
}
void MergeSort(int a[], int n)
{
int mid, l[10], r[10];
if(n<2)
return;
mid=n/2;
for(int i=0; i<mid; i++)
{
l[i]=a[i];
}
for(int i=mid; i<n; i++)
{
r[i-mid]=a[i];
}
MergeSort(l,mid);
MergeSort(r,n-mid);
Merge(a,l,mid,r,n-mid);
}
int main()
{
int num;
cout<<"How many elements: ";
cin>>num;
int *A=new int;
cout<<"Enter the numbers: \n";
for(int i=0;i<num;i++){
cin>>A[i];
}
cout<<"Sorted list: ";
MergeSort(A,num);
for(int i=0;i<num;i++){
cout<<A[i]<<" ";
}
return 0;
}
5.2.5 Quick sort
To sort using QuickSort method -create partitionIndex, find pivot, Partition-swap PI with End, recursive Qsort(start,PI-1) and Qsort(PI+1,End)
Runnable Code Snippet_5.2.5 – Quick Sort
/* 5.2.5 Quick sort */
#include <iostream>
using namespace std;
int Partition(int *A,int Start,int End){
int pivot=A[End];
int partitionIndex=Start; //set partition index as start initially
for(int i=Start;i<End;i++){
if(A[i]<pivot){
swap(A[i],A[partitionIndex]);
partitionIndex++;
}
}
swap(A[partitionIndex],A[End]);
return partitionIndex;
}
void QuickSort(int *A,int Start,int End){
if(Start<End){
int partitionIndex=Partition(A,Start,End);
QuickSort(A,Start,partitionIndex-1);
QuickSort(A,partitionIndex+1,End);
}
}
int main()
{
int num;
cout<<"How many elements: ";
cin>>num;
int *A=new int[num];
cout<<"Enter the numbers: \n";
for(int i=0;i<num;i++){
cin>>A[i];
}
cout<<"Sorted list: ";
QuickSort(A,0,num-1); //ATTENTION : num-1
for(int i=0;i<num;i++){
cout<<A[i]<<" ";
}
return 0;
}
So, we have come to the end of this read- Data Structures and Algorithms.
We discussed Linked List, Stack, Queue and Tree. Under the Linked List module, we discussed insertion of node at the beginning of Linked List, insertion of node at n-th position of Linked List, insertion of node at end of Linked List, deletion of node at n-th position of Linked List, Linked List reversal- iteratively and recursively, printing element of Linked List forward and reverse, Doubly Linked List,and a dedicated page for Circular Linked List. Under the Stack module, we discussed array implementation of Stack, Linked List implementation of Stack, reversing a string or Linked List using stack STL, balanced paranthesis check using Stack, Evaluating prefix & postfix expression using Stack and Infix to postfix using Stack. Under Queue module we discussed array implementation of Queue and Linked List implementation of Queue. Under Tree module we discussed Tree properties, Types of Trees, Binary Search tree(BST) implementation, finding min and max element in a BST, finding height of BST, BST traversal- Breadth first, Depth first, level order traversal, preorder, inorder, postorder traversals, Checking Binary tree for BST and deleting node from BST.
In addition to that we discussed, few Search and Sort Algorithms. Under Search Algorithm we discussed Linear search and Binary search Algorithms. Under Sort algorithm we covered Selection sort, Bubble sort, Insertion sort, Merge sort and Quick sort.
If you feel I missed any topic, please let me know. I will try to cover them as well, hopefully.
Corrections and Improvement Suggestions are highly appreciated. Thanks in advance..
Please follow the blog to stay updated with the upcoming modules.
love,
<R.S>
For Complete Sourcecode visit my Github repo
RS-codes
RS-codes 
One thought on “Data Structures & Algorithms – Search and Sort Algorithm”