Linear Search Program
Code:
#include<iostream>
using namespace std;
int main()
{
int arr[]={14,16,23,25,32,2,4,8,6,10,12};
int a,x=0,i;
cout<<"Enter a value to search in the array: ";
cin>>a;
int n=sizeof(arr)/sizeof(arr[0]);
for(i=0;i<n;i++)
{
if(a==arr[i])
{
x=1;
break;
}
else
{
x=0;
}
}
if(x==1)
cout<<"Data found at location arr["<<i<<"]\n";
else
cout<<"Data not found at any location\n";
return 0;
}
Output:
Enter a value to search in the array: 2 Data found at location arr[5]
Binary Search Program
Code:
#include<iostream>
using namespace std;
int main()
{
int arr[12]={10,20,30,40,50,60,70,80,90,100,110,120};
int i=0,j,k=11;
int value,check=0;
cout<<"Enter a data to search: ";
cin>>value;
while(i<=k)
{
j=(i+k)/2;
if(arr[j]==value)
{
check=1;
break;
}
else
{
if(arr[j]<value)
{
i=j+1;
}
else
k=j-1;
}
}
if(check==1)
cout<<"Data found at location arr["<<j<<"]\n";
else
cout<<"Data not found\n";
return 0;
}
Output:
Enter a data to search: 70 Data found at location arr[6]
Bubble Sort Program
Code:
#include<bits/stdc++.h>
using namespace std;
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void bubble_sort(int nums[], int size)
{
for (int i = 0; i < size - 1; i++)
{
for (int j = 0; j < size - i - 1; j++)
{
if (nums[j] > nums[j + 1])
{
swap(&nums[j],&nums[j+1]);
}
}
}
}
int main()
{
int arr[] = {9,8,7,6,5,4,3,2,1};
int n = sizeof(arr)/sizeof(arr[0]);
bubble_sort(arr,n);
cout<<"Sorted Array \n";
for(int i = 0; i < n; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
Output:
Sorted Array 1 2 3 4 5 6 7 8 9
Insertion Sort Program
Code:
#include<iostream>
using namespace std;
void InsertionSort(int [] , int);
int main()
{
int arr[]={8,5,10,54,-1,67,9};
int n=sizeof(arr)/sizeof(arr[0]);
InsertionSort(arr, n);
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" " ;
}
return 0;
}
void InsertionSort(int arr[], int n)
{
for(int pos=1; pos<n; pos++)
{
int tobesort=arr[pos];
int j=pos-1;
while(j>=0 && arr[j]>tobesort)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=tobesort;
}
}
Output:
-1 5 8 9 10 54 67
Shell Sort Program
Code:
#include <iostream>
#include<cstring>
using namespace std;
void ShellSort(char *, int);
int main()
{
char string[300];
cout << "Enter a string to be sorted: ";
gets(string);
ShellSort(string, strlen(string));
cout<<"Sorted String: "<< string;
return 0;
}
void ShellSort(char *chars, int c)
{
int i, j, incre, k;
char x, a[5];
a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;
for(k=0; k < 5; k++)
{
incre = a[k];
for(i=incre; i < c; ++i)
{
x = chars[i];
for(j=i-incre; (x < chars[j]) && (j >= 0); j=j-incre)
chars[j+incre] = chars[j];
chars[j+incre] = x;
}
}
}
Output:
Enter a string to be sorted: CODEDEC Sorted String: CCDDEEO
Selection Sort Program
Code:
#include <iostream>
using namespace std;
int main()
{
int a[10]={7,1,8,995,41,0,45,73,6,4};
int n, i, j, temp;
n=sizeof(a)/sizeof(a[0]);
for(i = 0; i < n; i++)
{
for(j = i + 1; j < n; j++)
{
if(a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
cout<<"Sorted List using Selection Sort: ";
for(i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
cout<<"\n";
return 0;
}
Output:
Sorted List using Selection Sort: 0 1 4 6 7 8 41 45 73 995
Merge Sort Program
Code:
#include <iostream>
using namespace std;
void merge_sort(int *, int , int );
void merge(int *,int, int , int );
int main()
{
int myarray[30], num;
cout<<"Enter number of elements to be sorted:";
cin>>num;
cout<<"Enter "<<num<<" elements to be sorted:";
for (int i = 0; i < num; i++)
{
cin>>myarray[i];
}
merge_sort(myarray, 0, num-1);
cout<<"Sorted array\n";
for (int i = 0; i < num; i++)
{
cout<<myarray[i]<<"\t";
}
}
void merge_sort(int *arr, int begin, int end)
{
int middle;
if (begin < end)
{
middle=(begin+end)/2;
merge_sort(arr,begin,middle);
merge_sort(arr,middle+1,end);
merge(arr,begin,end,middle);
}
}
void merge(int *arr, int begin, int end, int middle)
{
int i, j, k, c[50];
i = begin;
k = begin;
j = middle + 1;
while (i <= middle && j <= end)
{
if (arr[i] < arr[j])
{
c[k] = arr[i];
k++;
i++;
}
else
{
c[k] = arr[j];
k++;
j++;
}
}
while (i <= middle)
{
c[k] = arr[i];
k++;
i++;
}
while (j <= end)
{
c[k] = arr[j];
k++;
j++;
}
for (i = begin; i < k; i++)
{
arr[i] = c[i];
}
}
Output:
Enter number of elements to be sorted:8 Enter 8 elements to be sorted:5 9 22 54 1 -8 6 45 Sorted array -8 1 5 6 9 22 45 54
Quick Sort Program
Code:
#include <iostream>
void quick_sort(int [], int, int);
int split(int [], int, int);
int main()
{
int arr[8] = {21, 82, 73, 17, 35, 58, 64, 49};
quick_sort(arr, 0, 7);
for (int i = 0; i < 8; i++)
{
std::cout << arr[i] << " ";
}
std::cout << "\n";
return 0;
}
void quick_sort(int a[], int start, int end)
{
if (start < end)
{
int mid = split(a, start, end);
quick_sort(a, start, mid - 1);
quick_sort(a, mid + 1, end);
}
}
int split(int a[], int start, int end)
{
int x = a[end];
int i = start - 1;
for (int j = start; j < end; j++)
{
if (a[j] <= x)
{
i++;
std::swap(a[i], a[j]);
}
}
std::swap(a[i+1], a[end]);
return i+1;
}
Output:
17 21 35 49 58 64 73 82
Heap Sort Program
Code:
#include <iostream>
#include <vector>
void HeapSort(std::vector<int>& array1);
void Create_Max_Heap(std::vector<int>& array1);
void Max_Heap(std::vector<int>& array1, int i, int size_);
int main()
{
std::vector<int> array1 = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
HeapSort(array1);
for(int i = 0; i < array1.size(); i++)
{
std::cout << array1[i] << " ";
}
std::cout << "\n";
return 0;
}
void HeapSort(std::vector<int>& array1)
{
Create_Max_Heap(array1);
int sz = array1.size();
for(int i = array1.size() - 1; i > 0; i--)
{
std::swap(array1[0], array1[i]);
sz--;
Max_Heap(array1, 0, sz);
}
}
void Create_Max_Heap(std::vector<int>& array1)
{
for(int i = (array1.size() / 2); i >= 0; i--)
Max_Heap(array1, i, array1.size());
}
void Max_Heap(std::vector<int>& array1, int i, int size_)
{
int largest, l = (2*i) + 1, r = l + 1;
if(l < size_ && array1[l] > array1[i])
largest = l;
else
largest = i;
if(r < size_ && array1[r] > array1[largest])
largest = r;
if(largest != i)
{
std::swap(array1[i], array1[largest]);
Max_Heap(array1, largest, size_);
}
}
Output:
1 2 3 4 7 8 9 10 14 16
Counting Sort Program
Code:
#include<iostream>
using namespace std;
int k=0;
void CountingSort(int A[],int B[],int n)
{
int reps[k+1],t;
for(int i=0;i<=k;i++)
{
reps[i] = 0;
}
for(int i=0;i<n;i++)
{
t = A[i];
reps[t]++;
}
for(int i=1;i<=k;i++)
{
reps[i] = reps[i]+reps[i-1];
}
for(int i=0;i<n;i++)
{
t = A[i];
B[reps[t]] = t;
reps[t]=reps[t]-1;
}
}
int main()
{
int n;
cout<<"What size of array do you want? - ";
cin>>n;
int A[n],B[n];
cout<<"Enter your desired array elements: ";
for(int i=0;i<n;i++)
{
cin>>A[i];
if(A[i]>k)
{
k = A[i];
}
}
CountingSort(A,B,n);
cout<<"Sorted array: ";
for(int i=1;i<=n;i++)
{
cout<<B[i]<<" ";
}
cout<<"\n";
return 0;
}
Output:
What size of array do you want? - 4 Enter your desired array elements: 4 65 20 1 Sorted array: 1 4 20 65
Radix Sort Program
Code:
#include <iostream>
#include <queue>
#include <list>
using namespace std;
int array[]={54,55,84,954,22,12,65,44,332,49,87};
char * Radix_POS [] = {
"ones", "tens", "hundreds", "thousands",
"ten thousands", "hundred thousands", "millions"
};
int FetchPosition(int number, int pos)
{
int DIG;
while (pos > 0)
{
DIG = number % 10;
number = number / 10;
pos--;
}
return DIG;
}
void DisplayEntryArray(int elements[], int count)
{
printf("Array elements: ");
for (int index = 0; index < count; index ++)
{
printf("%d, ",elements[index]);
}
printf("\n");
}
void RadixSort(int elements[], int count)
{
queue <int> *q[10];
int i, j, k, max = -2147483648;
for (i = 0; i < count; i++)
{
if (elements[i] > max)
{
max = elements[i];
}
}
i = 0;
while (max)
{
max = max /10;
i++;
}
max = i;
for (i = 0; i < max; i++)
{
printf("Radix position: %s\n",
(i < 7 )? Radix_POS[i]: "");
for (int j=0; j < 10; j++)
{
q[j] = new queue<int>;
}
for ( k=0; k < count; k++)
{
int DIG = FetchPosition(elements[k], i+1);
q[DIG]->push(elements[k]);
}
k = 0;
for ( j=0; j < 10; j++)
{
printf("Queue[%d]: ", j);
while (!q[j]->empty())
{
elements[k] = q[j]->front();
q[j]->pop();
printf("%d, ", elements[k]);
k++;
}
printf("\n");
}
for ( j=0; j < 10; j++)
{
delete q[j];
}
DisplayEntryArray(elements, count);
}
}
int main(int argc, char* argv[])
{
printf("Radix sort:\n");
DisplayEntryArray(array, 11);
RadixSort(array, 11);
printf("Radix sort array:\n");
DisplayEntryArray(array, 11);
return 0;
}
Output:
Radix sort: Array elements: 54, 55, 84, 954, 22, 12, 65, 44, 332, 49, 87, Radix position: ones Queue[0]: Queue[1]: Queue[2]: 22, 12, 332, Queue[3]: Queue[4]: 54, 84, 954, 44, Queue[5]: 55, 65, Queue[6]: Queue[7]: 87, Queue[8]: Queue[9]: 49, Array elements: 22, 12, 332, 54, 84, 954, 44, 55, 65, 87, 49, Radix position: tens Queue[0]: Queue[1]: 12, Queue[2]: 22, Queue[3]: 332, Queue[4]: 44, 49, Queue[5]: 54, 954, 55, Queue[6]: 65, Queue[7]: Queue[8]: 84, 87, Queue[9]: Array elements: 12, 22, 332, 44, 49, 54, 954, 55, 65, 84, 87, Radix position: hundreds Queue[0]: 12, 22, 44, 49, 54, 55, 65, 84, 87, Queue[1]: Queue[2]: Queue[3]: 332, Queue[4]: Queue[5]: Queue[6]: Queue[7]: Queue[8]: Queue[9]: 954, Array elements: 12, 22, 44, 49, 54, 55, 65, 84, 87, 332, 954, Radix sort array: Array elements: 12, 22, 44, 49, 54, 55, 65, 84, 87, 332, 954,
Bucket Sort Program
Code:
#include<iostream>
#include<stdio.h>
#include<conio.h>
void Bucket_Sort(float* ,int );
int main()
{
int n,l;
float *a;
std::cout<<"Array Size: \n";
std::cin>>n;
std::cout<<"Enter array elements: \n";
a=new float[n];
for(int l=0;l<n;l++)
std::cin>>a[l];
std::cout<<"Sorted array: \n";
for(l=0;l<n;l++)
std::cout<<a[l]<<" ";
std::cout<<"\n" ;
Bucket_Sort(a,n);
getch();
}
class node
{
public:
float info;
node *SortUp,*Prev;
node(){SortUp=Prev=0;}
node(int n, node *p1=0, node *p2=0)
{
info=n;
SortUp=p1;
Prev=p2;
}
};
void SortElements(node *head)
{
if (head == 0)
return;
float key;
node *j,*i, *q=0;
for(i=head->SortUp;i!=0;i=i->SortUp)
{
q=0;
key = i->info;
j=i->Prev;
while(j!=0 && key < (j->info) )
{
j->SortUp->info=j->info;
q = j;
j=j->Prev;
}
if(q!=0)
q->info = key;
}
}
void Bucket_Sort(float *a,int n)
{
node* *b = new node* [n];
for(int i=0; i<n;i++)
b[i]=0;
for(int i=0;i<n;i++)
{
int index=n*a[i];
node *temp=new node(sizeof(node));
temp->info=a[i];
if(b[index]==NULL)
{
b[index]=temp;
}
else
{
temp->SortUp=b[index];
b[index]->Prev=temp;
b[index]=temp;
}
}
for(int i=0; i<n;i++)
{
SortElements(b[i]);
}
node *HeadUp=0;
std::cout<<"Sorted array: \n";
for(int i=0; i<n;i++)
{
HeadUp = b[i];
while(HeadUp != 0)
{
std::cout<<HeadUp->info<<" ";
HeadUp = HeadUp->SortUp;
}
}
}
Output:
Array Size: 5 Enter array elements: 45 99 112 4 22 Sorted array: 4 22 45 99 112
Comb Sort Program
Code:
#include<bits/stdc++.h>
using namespace std;
int next(int interval)
{
interval = (interval*10)/13;
if (interval < 1)
return 1;
return interval;
}
void CombSort(int a[], int n)
{
int interval = n;
bool swapped = true;
while (interval != 1 || swapped == true)
{
interval = next(interval);
swapped = false;
for (int i=0; i<n-interval; i++)
{
if (a[i] > a[i+interval])
{
swap(a[i], a[i+interval]);
swapped = true;
}
}
}
}
int main()
{
int a[] = {44,545,7,99,10,51,23,4,2,65};
int n = sizeof(a)/sizeof(a[0]);
CombSort(a, n);
printf("Sorted array: \n");
for (int i=0; i<n; i++)
printf("%d ", a[i]);
return 0;
}
Output:
Sorted array: 2 4 7 10 23 44 51 65 99 545
Bitonic Sort Program
Code:
#include<iostream>
#include<stdio.h>
#include<conio.h>
void BitonicSort(int*, int);
int main()
{
int a[] = {44,545,7,99,10,51,23};
int n = sizeof(a)/sizeof(a[0]);
BitonicSort(a, n);
printf("Sorted array: \n");
for (int i=0; i<n; i++)
printf("%d ", a[i]);
return 0;
}
void BitonicSort(int *data, int N)
{
int i, j, k;
int temp;
for (k = 2;k <= N;k = 2 * k)
{
for (j = k >> 1;j>0; j = j >> 1)
{
for (i = 0;i<N;i++)
{
int ixj = i^j;
if ((ixj)>i)
{
if ((i&k) == 0 && data[i] > data[ixj]) {
temp = data[i];
data[i] = data[ixj];
data[ixj] = temp;
}
if ((i&k) != 0 && data[i] < data[ixj]) {
temp = data[i];
data[i] = data[ixj];
data[ixj] = temp;
}
}
}
}
}
}
Output:
Sorted array: 7 10 23 44 51 99 545
Cocktail Sort Program
Code:
#include <iostream>
using namespace std;
int temp;
void CocktailSort(int* , int);
int main()
{
int arr[] = {45,34,11,3,97,65};
int i;
int n = sizeof(arr) / sizeof(arr[0]);
CocktailSort(arr, n);
cout <<"Sorted array: \n";
for (i = 0; i < n; i++)
cout<<arr[i]<<" ";
cout<<"\n";
return 0;
}
void CocktailSort(int a[], int n)
{
int swap = 1;
int start = 0,i;
int end = n - 1;
while (swap)
{
swap = 0;
for (i = start; i < end; ++i)
{
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
swap = 1;
}
}
if (!swap)
break;
swap = 0;
for (i = end - 1; i >= start; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
swap = 1;
}
}
++start;
}
}
Output:
Sorted array: 3 11 34 45 65 97
Cycle Sort Program
Code:
#include<iostream>
using namespace std;
void Swap(int &, int &);
void PrintData(int *, int);
void CycleSort(int *, int);
int main()
{
int n;
cout << "Size of array: ";
cin >> n;
int array1[n];
cout << "Enter array elements:" << endl;
for(int i = 0; i<n; i++)
{
cin >> array1[i];
}
cout << "Before Sorting: ";
PrintData(array1, n);
CycleSort(array1, n);
cout << "After Sorting: ";
PrintData(array1, n);
}
void Swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
void PrintData(int *array, int size)
{
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void CycleSort(int *array, int n)
{
for(int start = 0; start<n-1; start++)
{
int key = array[start];
int location = start;
for(int i = start+1; i<n; i++)
{
if(array[i] < key)
location++;
}
if(location == start)
continue;
while(key == array[location])
location++;
if(location != start)
Swap(array[location], key);
while(location != start) {
location = start;
for(int i = start+1; i<n; i++)
{
if(array[i] < key)
location++;
}
while(key == array[location])
location++;
if(key != array[location])
Swap(key, array[location]);
}
}
}
Output:
Size of array: 5 Enter array elements: 12 99 4 65 -2 Before Sorting: 12 99 4 65 -2 After Sorting: -2 4 12 65 99
Tim Sort Program
Code:
#include <iostream>
using namespace std;
const int exec = 32;
void InsertionSort(int arr[], int post, int pre)
{
for (int i = post + 1; i <= pre; i++)
{
int temp = arr[i];
int j = i - 1;
while (arr[j] > temp && j >= post)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
void MergeSort(int arr[], int l, int m, int r)
{
int x = m - l + 1, y = r - m;
int post[x], pre[y];
for (int i = 0; i < x; i++)
post[i] = arr[l + i];
for (int i = 0; i < y; i++)
pre[i] = arr[m + 1 + i];
int i = 0;
int j = 0;
int k = l;
while (i < x && j < y)
{
if (post[i] <= pre[j])
{
arr[k] = post[i];
i++;
}
else
{
arr[k] = pre[j];
j++;
}
k++;
}
while (i < x)
{
arr[k] = post[i];
k++;
i++;
}
while (j < y)
{
arr[k] = pre[j];
k++;
j++;
}
}
void TimSort(int arr[], int n)
{
for (int i = 0; i < n; i+=exec)
InsertionSort(arr, i, min((i+31), (n-1)));
for (int size = exec; size < n; size = 2*size)
{
for (int post = 0; post < n; post += 2*size)
{
int mid = post + size - 1;
int pre = min((post + 2*size - 1), (n-1));
MergeSort(arr, post, mid, pre);
}
}
}
void SortedArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {54, 6, 78, 43, -9};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Unsorted Array: \n");
SortedArray(arr, n);
TimSort(arr, n);
printf("Sorted Array: \n");
SortedArray(arr, n);
return 0;
}
Output:
Unsorted Array: 54 6 78 43 -9 Sorted Array: -9 6 43 54 78
