Thursday, August 10, 2023
Monday, August 7, 2023
C program for insertion sort
#include <math.h>
#include <stdio.h>
/* Function to sort an array
using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1],
that are greater than key,
to one position ahead of
their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// A utility function to print
// an array of size n
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
int main()
{
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}
Merge Sort
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i <= high; i++)
a[i] = b[i];
}
void sort(int low, int high) {
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main() {
int i;
printf("List before sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
sort(0, max);
printf("\nList after sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
}
NON RECURSIVE MERGE SORT
#include <stdio.h>
#define MAX 30
int main()
{
int arr[MAX],temp[MAX],i,j,k,n,size,l1,h1,l2,h2;
printf("Enter the number of elements : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Unsorted list is : ");
for( i = 0 ; i<n ; i++)
printf("%d ", arr[i]);
/*l1 lower bound of first pair and so on*/
for(size=1; size < n; size=size*2 )
{
l1=0;
k=0; /*Index for temp array*/
while( l1+size < n)
{
h1=l1+size-1;
l2=h1+1;
h2=l2+size-1;
/* h2 exceeds the limlt of arr */
if( h2>=n )
h2=n-1;
/*Merge the two pairs with lower limits l1 and l2*/
i=l1;
j=l2;
while(i<=h1 && j<=h2 )
{
if( arr[i] <= arr[j] )
temp[k++]=arr[i++];
else
temp[k++]=arr[j++];
}
while(i<=h1)
temp[k++]=arr[i++];
while(j<=h2)
temp[k++]=arr[j++];
/**Merging completed**/
/*Take the next two pairs for merging */
l1=h2+1;
}/*End of while*/
/*any pair left */
for(i=l1; k<n; i++)
temp[k++]=arr[i];
for(i=0;i<n;i++)
arr[i]=temp[i];
printf("\nSize=%d \nElements are : ",size);
for( i = 0 ; i<n ; i++)
printf("%d ", arr[i]);
}/*End of for loop */
printf("Sorted list is :\n");
for( i = 0 ; i<n ; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}/*End of main()*/
Heap Sort
// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root Since we are using 0 based indexing
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver program
int main()
{
int arr[] = { 60 ,20 ,40 ,70, 30, 10};
int n = sizeof(arr) / sizeof(arr[0]);
//heapify algorithm
// the loop must go reverse you will get after analyzing manually
// (i=n/2 -1) because other nodes/ ele's are leaf nodes
// (i=n/2 -1) for 0 based indexing
// (i=n/2) for 1 based indexing
for(int i=n/2 -1;i>=0;i--){
heapify(arr,n,i);
}
cout << "After heapifying array is \n";
printArray(arr, n);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
return 0;
}
//code by Prajwal Chougale
Randomized Quick sort
#include<iostream>
#include<cstdlib>
using namespace std;
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int Partition(int a[], int l, int h) {
int pivot, index, i;
index = l;
pivot = h;
for(i = l; i < h; i++) {
if(a[i] < a[pivot]) {
swap(&a[i], &a[index]);
index++;
}
}
swap(&a[pivot], &a[index]);
return index;
}
int RandomPivotPartition(int a[], int l, int h) {
int pvt, n, temp;
n = rand();
pvt = l + n%(h-l+1);
swap(&a[h], &a[pvt]);
return Partition(a, l, h);
}
int QuickSort(int a[], int l, int h) {
int pindex;
if(l < h) {
pindex = RandomPivotPartition(a, l, h);
QuickSort(a, l, pindex-1);
QuickSort(a, pindex+1, h);
}
return 0;
}
int main() {
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++) {
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
QuickSort(arr, 0, n-1);
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}
RADIX SORT
#include<stdio.h>
int get_max (int a[], int n){
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
void radix_sort (int a[], int n){
int bucket[10][10], bucket_cnt[10];
int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
lar = get_max (a, n);
while (lar > 0){
NOP++;
lar /= 10;
}
for (pass = 0; pass < NOP; pass++){
for (i = 0; i < 10; i++){
bucket_cnt[i] = 0;
}
for (i = 0; i < n; i++){
r = (a[i] / divisor) % 10;
bucket[r][bucket_cnt[r]] = a[i];
bucket_cnt[r] += 1;
}
i = 0;
for (k = 0; k < 10; k++){
for (j = 0; j < bucket_cnt[k]; j++){
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;
printf ("After pass %d : ", pass + 1);
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
// printf ("");
}
}
int main (){
int i, n, a[10];
printf ("Enter the number of items to be sorted: ");
scanf ("%d", &n);
printf ("Enter items: ");
for (i = 0; i < n; i++){
scanf ("%d", &a[i]);
}
radix_sort (a, n);
printf ("Sorted items : ");
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
// printf ("");
return 0;
}
DYNAMIC LCS
#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
int m = pattern_1.size();
int n = pattern_2.size();
// dp will store solutions as the iteration goes on
int dp[n + 1][m + 1];
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < m + 1; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (pattern_2[i - 1] == pattern_1[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
int main() {
string pattern_1 = "RGBGARGA";
string pattern_2 = "BGRARG";
cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}
DFS IN C++
#include<iostream>
using namespace std;
#include<conio.h>
#include<stdlib.h>
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];
int main()
{
int m;
cout <<"Enter no of vertices:";
cin >> n;
cout <<"Enter no of edges:";
cin >> m;
cout <<"\nEDGES \n";
for(k=1; k<=m; k++)
{
cin >>i>>j;
cost[i][j]=1;
}
cout <<"Enter initial vertex to traverse from:";
cin >>v;
cout <<"DFS ORDER OF VISITED VERTICES:";
cout << v <<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=n; j>=1; j--)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stk[top]=j;
top++;
}
v=stk[--top];
cout<<v << " ";
k++;
visit[v]=0;
visited[v]=1;
}
return 0;
}
BFS IN C
#include <stdio.h>
int n, i, j, visited[10], queue[10], front = -1, rear = -1;
int adj[10][10];
void bfs(int v)
{
for (i = 1; i <= n; i++)
if (adj[v][i] && !visited[i])
queue[++rear] = i;
if (front <= rear)
{
visited[queue[front]] = 1;
bfs(queue[front++]);
}
}
void main()
{
int v;
printf("Enter the number of vertices: ");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
queue[i] = 0;
visited[i] = 0;
}
printf("Enter graph data in matrix form: \n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &adj[i][j]);
printf("Enter the starting vertex: ");
scanf("%d", &v);
bfs(v);
printf("The node which are reachable are: \n");
for (i = 1; i <= n; i++)
if (visited[i])
printf("%d\t", i);
else
printf("BFS is not possible. Not all nodes are reachable");
}
KRUSKAL
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];
int find(int);
int uni(int, int);
void main() {
printf("\n\tImplementation of Kruskal's Algorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix:\n");
for (i = 1; i<= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0)
cost[i][j] = 999;
}
}
printf("The edges of Minimum Cost Spanning Tree are\n");
while (ne < n) {
for (i = 1, min = 999; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (cost[i][j] <min) {
min = cost[i][j];
a = u = i;
b = v = j;
}
}
}
u = find(u);
v = find(v);
if (uni(u, v)) {
printf("%d edge (%d,%d) =%d\n", ne++, a, b, min);
mincost += min;
}
cost[a][b] = cost[b][a] = 999;
}
printf("\n\tMinimum cost = %d\n", mincost);
getch();
}
int find(int i) {
while (parent[i])
i = parent[i];
return i;
}
int uni(int i, int j) {
if (i != j) {
parent[j] = i;
return 1;
}
return 0;
}
prims algorithm
#include<iostream>
using namespace std;
// Number of vertices in the graph
const int V=6;
// Function to find the vertex with minimum key value
int min_Key(int key[], bool visited[])
{
int min = 999, min_index; // 999 represents an Infinite value
for (int v = 0; v < V; v++) {
if (visited[v] == false && key[v] < min) {
// vertex should not be visited
min = key[v];
min_index = v;
}
}
return min_index;
}
// Function to print the final MST stored in parent[]
void print_MST(int parent[], int cost[V][V])
{
int minCost=0;
cout<<"Edge \tWeight\n";
for (int i = 1; i< V; i++) {
cout<<parent[i]<<" - "<<i<<" \t"<<cost[i][parent[i]]<<" \n";
minCost+=cost[i][parent[i]];
}
cout<<"Total cost is"<<minCost;
}
// Function to find the MST using adjacency cost matrix representation
void find_MST(int cost[V][V])
{
int parent[V], key[V];
bool visited[V];
// Initialize all the arrays
for (int i = 0; i< V; i++) {
key[i] = 999; // 99 represents an Infinite value
visited[i] = false;
parent[i]=-1;
}
key[0] = 0; // Include first vertex in MST by setting its key vaue to 0.
parent[0] = -1; // First node is always root of MST
// The MST will have maximum V-1 vertices
for (int x = 0; x < V - 1; x++)
{
// Finding the minimum key vertex from the
//set of vertices not yet included in MST
int u = min_Key(key, visited);
visited[u] = true; // Add the minimum key vertex to the MST
// Update key and parent arrays
for (int v = 0; v < V; v++)
{
// cost[u][v] is non zero only for adjacent vertices of u
// visited[v] is false for vertices not yet included in MST
// key[] gets updated only if cost[u][v] is smaller than key[v]
if (cost[u][v]!=0 && visited[v] == false && cost[u][v] < key[v])
{
parent[v] = u;
key[v] = cost[u][v];
}
}
}
// print the final MST
print_MST(parent, cost);
}
// main function
int main()
{
int cost[V][V];
cout<<"Enter the vertices for a graph with 6 vetices";
for (int i=0;i<V;i++)
{
for(int j=0;j<V;j++)
{
cin>>cost[i][j];
}
}
find_MST(cost);
return 0;
}
Tuesday, July 25, 2023
Twin Prime Number in a range
import java.io.*;
import java.util.*;
public class Main
{static boolean checkPrimeNumber(int number)
{
int i;
int m = 0;
int flag = 0;
m = number/2;
if(number == 0 || number == 1){
return false;
}else{
for(i = 2; i <= m ;i++){
if(number%i == 0){
flag=1;
return false;
}
}
if(flag == 0)
{
return true;
}
}
return false;
}
static boolean checkTwinPrimeNumber(int number1, int number2)
{
if(checkPrimeNumber(number1) && checkPrimeNumber(number2) && Math.abs(number1 - number2) == 2)
return true;
else
return false;
}
public static void main(String[] args)
{
int startRange, endRange;
Scanner sc=new Scanner(System.in);
System.out.println("Enter start value");
startRange = sc.nextInt();
System.out.println("Enter last value");
endRange = sc.nextInt();
System.out.println("The pairs of twin primes between" + startRange + " and " + endRange + "are:");
for (int i = startRange; i < endRange; i++) {
if (checkTwinPrimeNumber(i, (i + 2))){
System.out.printf("(%d, %d)\n", i, i + 2);
}
}
}
}
Neon Number
import java.util.Scanner;
import java.lang.Math;
public class Main
{
public static void main(String args[])
{
int sum = 0, n;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number to check: ");
n = sc.nextInt();
int square = n * n;
while(square != 0)
{
int digit = square % 10;
sum = sum + digit;
square = square / 10;
}
if(n == sum)
System.out.println(n + " is a Neon Number.");
else
System.out.println(n + " is not a Neon Number.");
}
}
DecimalToBinary
import java.util.Scanner;
import java.lang.Math;
public class Main
{
public static int convertDecimalToBinary(int dec) {
int rem,b1=0;
int rev = 1;
while (dec > 0) {
rem = dec % 2;
dec = dec / 2;
b1 = b1 + rem * rev;
rev = rev * 10;
}
return b1;
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
System.out.print("Enter a number : ");
int num = in.nextInt();
int decimal = convertDecimalToBinary(num);
System.out.println("Binary to Decimal");
System.out.println(num + " = " + decimal);
}
}
Automorphic Number
import java.util.Scanner;
import java.lang.Math;
public class Main
{
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
System.out.print("Enter a number to check: ");
int num = in.nextInt();
int count=0;
int square = num*num;
int temp = num;
while(temp>0)
{
count++;
temp=temp/10;
}
int lastDigit = (int) (square%(Math.pow(10, count)));
if(num == lastDigit)
System.out.println(num+ " is an automorphic number.");
else
System.out.println(num+ " is not an automorphic number.");
}
}
Armstrong Number
import java.util.Scanner;
import java.lang.Math;
public class Main
{
static boolean isArmstrong(int n)
{
int temp, digits=0, last=0, sum=0;
temp=n;
while(temp>0)
{
temp = temp/10;
digits++;
}
temp = n;
while(temp>0)
{
last = temp % 10;
sum += (Math.pow(last, digits));
temp = temp/10;
}
if(n==sum)
return true;
else return false;
}
public static void main(String args[])
{
int num;
Scanner sc= new Scanner(System.in);
System.out.print("Enter the limit: ");
num=sc.nextInt();
if(isArmstrong(num))
System.out.print(num+ " is armstrong Number ");
}
}
Fibonacci series
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println( " enter a value");
int n1=0,n2=1,n3,i,count;
count = sc.nextInt();
for(i=1;i<=count;++i)//loop starts from 2 because 0 and 1 are already printed
{
n3=n1+n2;
System.out.print(" "+n1);
n1=n2;
n2=n3;
}
}}
Java happy Number
import java.util.*;
public class Main
{public static int isHappyNumber(int num){
int rem = 0, sum = 0;
while(num > 0){
rem = num%10;
sum = sum + (rem*rem);
num = num/10;
}
return sum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println( " enter a value");
int num = sc.nextInt();
int result = num;
while(result != 1 && result != 4){
result = isHappyNumber(result);
}
if(result == 1)
System.out.println(num + " is a happy number");
else if(result == 4)
System.out.println(num + " is not a happy number");
}
}
Java Magic Number
import java.util.Scanner;
public class Main
{
public static void main(String[] args) {
int n, remainder = 1, number, sum = 0;
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number you want to check: ");
n = sc.nextInt();
number = n;
while (number > 9)
{
while (number > 0)
{
remainder = number % 10;
sum = sum + remainder;
number = number / 10;
}
number = sum;
sum = 0;
}
if (number == 1)
{
System.out.println("The given number is a magic number.");
}
else
{
System.out.println("The given number is not a magic number.");
}
}
}
Subscribe to:
Posts (Atom)