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