Revision

Searching Algorithm

import java.security.PublicKey;


class searching {

//linear search

public static void LinearSearch(int arr[], int key){

for(int i=0 ; i<=arr.length; i++){

if(arr[i] == key){

System.out.println("Element found index no. is " + i);

break;

}


}

}

//Binary Searching

public static int Bineaysearch(int arr[], int key){

int start = 0;

int end = arr.length-1;

while(start < end){

int mid = (start+end)/2;

if(arr[mid] == key){

return mid;

}

else if(mid < key){

mid++;

}

else if (mid > key){

mid--;

}

}

return 0;


}


public static void main(String[] args) {

int arr[] = {10,20,30,40,50,60,70,80,90};

int key = 50;

// LinearSearch(arr, key);

System.out.println(Bineaysearch(arr ,key));


}



}


Largest Value 

public class largestvalue {

public static int Largestvalue(int arr[]){

int max_value = Integer.MIN_VALUE;

for (int i =0 ; i< arr.length; i++){

if(max_value < arr[i]){

max_value = arr[i];

}

}

return max_value;

}

public static void main(String[] args) {

int arr[] = {10,20,3,0,45,12,5,8,6,1,22};

System.out.println(Largestvalue(arr));


}

}


Smallest Value

public class smallestvalue {

public static int smallestvalue(int arr[]){

int min_value = Integer.MAX_VALUE;

for (int i =0 ; i< arr.length; i++){

if(min_value > arr[i]){

min_value = arr[i];

}

}

return min_value;

}

public static void main(String[] args) {

int arr[] = {10,20,3,45,12,5,8,6,1,22};

System.out.println(smallestvalue(arr));


}

}


Reverse array

class Reversearray {

public static void reversearr(int arr[]){


for(int i = arr.length-1; i >=0 ; i-- ){

System.out.println(arr[i]);

}

}

public static void main(String[] args) {

int arr[] = {10,20,30,40,50,60,70,80};

reversearr(arr);


}

}


Pair of array

public class pairofarray {

public static void pairingofarray(int arr[]){

for(int i = 0 ; i< arr.length; i++){

for(int j = i+1 ; j< arr.length; j++){

System.out.print("("+arr[i] + "," +arr[j] +")");

}

System.out.println();

}

}

public static void main(String[] args) {

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

pairingofarray(arr);


}

}


Sub Array 

public class subarray {

public static void subarrayparing(int arr[]){



for (int i = 0 ; i< arr.length; i++){

int sum =0 ;

int max = Integer.MIN_VALUE;

int start =i;

for(int j =0; j< arr.length; j++ ){

int end =j;



for(int k =start ; k<=end; k++){

System.out.print(arr[k] + " ");

sum+= arr[k];




}


System.out.println();

}

System.out.println();

if(sum >max){

max = sum;

}

System.out.println("=" + sum + " " + max);


}


}



public static void main(String[] args) {

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

subarrayparing(arr);

}

}


Tapping water problem

public class Tappingwater {

public static int tappinwater(int height[]){

int n = height.length;

//Leftmax

int leftmax[] = new int[n];

leftmax[0] = height[0];

for (int i =1; i<n; i++){

leftmax[i] = Math.max(height[i] , leftmax[i-1]);

}

//RightMaximum

int rightmax[] = new int[n];

rightmax[n-1] = height[n-1];

for (int j = n-2; j>=0; j--){

rightmax[j] = Math.max(height[j] , rightmax[j+1]);

}

int trapwater = 0 ;

for(int i = 0 ; i<n; i++){

int waterlevel = Math.min(leftmax[i],rightmax[i]);

trapwater+= waterlevel-height[i];

}

return trapwater;

}

public static void main(String[] args) {

int height[] ={4,2,0,6,3,2,5};

System.out.println(tappinwater(height));

}

}


Bubble Sorting

import java.util.Scanner;


public class Bubblesorting {

public static void bubblesortin(int arr[]){

for(int i=0; i< arr.length-1; i++ ){

for (int j=0; j< arr.length-1-i; j++){

if(arr[j] > arr[j+1]){

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

}

}

}


public static void printarry(int arr[]){

for(int i= 0 ; i< arr.length; i++){

System.out.print(arr[i]+" ");

}

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.println("Enter the Number of Element you want to inseret");

int n = sc.nextInt();

int arr[] = new int[n];

for(int i = 0; i<n; i++){

System.out.println("Enter the Element no" + i );

arr[i] = sc.nextInt();

}

bubblesortin(arr);

printarry(arr);


}

}


Selection Sorting 

import java.util.Scanner;


public class Selectionsorting {

public static void selectionsorting(int arr[]) {

for (int i = 0; i < arr.length - 1; i++) {

int minpos = i;

for (int j = i + 1; j < arr.length; j++) {

if (arr[minpos] > arr[j]) {

minpos = j;

}

int temp = arr[minpos];

arr[minpos] = arr[i];

arr[i] = temp;

}


}

}



public static void printarry(int arr[]){

for(int i= 0 ; i< arr.length; i++){

System.out.print(arr[i]+" ");

}

}



public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.println("Enter the Number of Element you want to inseret");

int n = sc.nextInt();

int arr[] = new int[n];

for(int i = 0; i<n; i++){

System.out.println("Enter the Element no" + i );

arr[i] = sc.nextInt();

}

selectionsorting(arr);


printarry(arr);


}

}



Counting Sorting 

import java.util.Scanner;


public class Countingsorting {

public static void counting(int arr[]){

int largest = Integer.MIN_VALUE;

for (int i =0 ; i<arr.length; i++){

largest = Math.max(largest,arr[i]);

}

int count[] = new int[largest+1];

for(int i=0; i<arr.length;i++){

count[arr[i]]++;

}

int j=0;


for(int i=0;i< count.length; i++){

while(count[i] > 0){

arr[j] =i;

j++;

count[i]--;


}

}

}

public static void printarry(int arr[]){

for(int i= 0 ; i< arr.length; i++){

System.out.print(arr[i]+" ");

}

}

public static void main(String[] args) {

int arr[] = {1,1,3,3,2,1,2};

counting(arr);

printarry(arr);


}

}


Spiral Code 

import java.util.Scanner;


public class Countingsorting {

public static void counting(int arr[]){

int largest = Integer.MIN_VALUE;

for (int i =0 ; i<arr.length; i++){

largest = Math.max(largest,arr[i]);

}

int count[] = new int[largest+1];

for(int i=0; i<arr.length;i++){

count[arr[i]]++;

}

int j=0;


for(int i=0;i< count.length; i++){

while(count[i] > 0){

arr[j] =i;

j++;

count[i]--;


}

}

}

public static void printarry(int arr[]){

for(int i= 0 ; i< arr.length; i++){

System.out.print(arr[i]+" ");

}

}

public static void main(String[] args) {

int arr[] = {1,1,3,3,2,1,2};

counting(arr);

printarry(arr);


}

}


queue in array

#include<stdio.h>  

#include<stdlib.h>  

#define maxsize 5



void insert();  

void delete();  

void display();  



int front = -1, rear = -1;  

int queue[maxsize];  

void main ()  

{  

    int choice;  

    while(choice != 4)  

    {    

       

        printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");  

        printf("\nEnter your choice ?");  

        scanf("%d",&choice);  

        switch(choice)  

        {  

            case 1:  

            insert();  

            break;  

            case 2:  

            delete();  

            break;  

            case 3:  

            display();  

            break;  

            case 4:  

            exit(0);  

            break;  

            default:  

            printf("\nEnter valid choice??\n");  

        }  

    }  

}  

void insert()  

{  

    int item;  

    printf("\nEnter the element\n");  

    scanf("\n%d",&item);      

    if(rear == maxsize-1)  

    {  

        printf("\nOVERFLOW\n");  

        return;  

    }  

   

    else  

    {  

        rear = rear+1;  

    }  

    queue[rear] = item;  

    printf("\nValue inserted ");  

     

}  

void delete()  

{  

    int item;  

    if (front == -1 || front > rear)  

    {  

        printf("\nUNDERFLOW\n");  

        return;  

             

    }  

    else  

    {  

        item = queue[front];  

        if(front == rear)  

        {  

            front = -1;  

            rear = -1 ;  

        }  

        else  

        {  

            front = front + 1;  

        }  

        printf("\nvalue deleted ");  

    }  

     

     

}  

     

void display()  

{  

    int i;  

    if(rear == -1)  

    {  

        printf("\nEmpty queue\n");  

    }  

    else  

    {   printf("\nprinting values .....\n");  

        for(i=front;i<=rear;i++)  

        {  

            printf("\n%d\n",queue[i]);  

        }    

    }  

}



Linked list

#include <stdio.h>

#include <stdlib.h>

struct node

{

    int data;

    struct node *next;

};


int main()

{

    struct node *head, *newnode, *temp;

    head = NULL;

    newnode = (struct node *)malloc(sizeof(struct node));

    int choice = 1, count = 0;

    while (choice)

    {


        printf("Enter the value in the node ");

        scanf("%d", &newnode->data);

        newnode->next = 0;

        if (head == NULL)

        {

            head = temp = newnode;

        }

        else

        {

            temp->next = newnode;

            temp = newnode;

        }

        printf("Do you want continue (0 or 1)");

        scanf("%d", &choice);

       

    }


    return 0;

}





inseration 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;

    }

}


Quick Sort

// C program for Merge Sort 

#include <stdio.h> 

#include <stdlib.h> 


// Merges two subarrays of arr[]. 

// First subarray is arr[l..m] 

// Second subarray is arr[m+1..r] 

void merge(int arr[], int l, int m, int r) 

int i, j, k; 

int n1 = m - l + 1; 

int n2 = r - m; 


// Create temp arrays 

int L[n1], R[n2]; 


// Copy data to temp arrays 

// L[] and R[] 

for (i = 0; i < n1; i++) 

L[i] = arr[l + i]; 

for (j = 0; j < n2; j++) 

R[j] = arr[m + 1 + j]; 


// Merge the temp arrays back 

// into arr[l..r] 

// Initial index of first subarray 

i = 0; 


// Initial index of second subarray 

j = 0; 


// Initial index of merged subarray 

k = l; 

while (i < n1 && j < n2) { 

if (L[i] <= R[j]) { 

arr[k] = L[i]; 

i++; 

else { 

arr[k] = R[j]; 

j++; 

k++; 


// Copy the remaining elements 

// of L[], if there are any 

while (i < n1) { 

arr[k] = L[i]; 

i++; 

k++; 


// Copy the remaining elements of 

// R[], if there are any 

while (j < n2) { 

arr[k] = R[j]; 

j++; 

k++; 


// l is for left index and r is 

// right index of the sub-array 

// of arr to be sorted 

void mergeSort(int arr[], int l, int r) 

if (l < r) { 

// Same as (l+r)/2, but avoids 

// overflow for large l and h 

int m = l + (r - l) / 2; 


// Sort first and second halves 

mergeSort(arr, l, m); 

mergeSort(arr, m + 1, r); 


merge(arr, l, m, r); 


// UTILITY FUNCTIONS 

// Function to print an array 

void printArray(int A[], int size) 

int i; 

for (i = 0; i < size; i++) 

printf("%d ", A[i]); 

printf("\n"); 


// Driver code 

int main() 

int arr[] = { 12, 11, 13, 5, 6, 7 }; 

int arr_size = sizeof(arr) / sizeof(arr[0]); 


printf("Given array is \n"); 

printArray(arr, arr_size); 


mergeSort(arr, 0, arr_size - 1); 


printf("\nSorted array is \n"); 

printArray(arr, arr_size); 

return 0; 

}


traversal Linked list

/**

 * C program to create and traverse a Linked List

 */


#include <stdio.h>

#include <stdlib.h>


/* Structure of a node */

struct node {

    int data;          // Data 

    struct node *next; // Address 

}*head;



/* 

 * Functions to create and display list

 */

void createList(int n);

void traverseList();



int main()

{

    int n;


    printf("Enter the total number of nodes: ");

    scanf("%d", &n);


    createList(n);


    printf("\nData in the list \n");

    traverseList();


    return 0;

}


/*

 * Create a list of n nodes

 */

void createList(int n)

{

    struct node *newNode, *temp;

    int data, i;


    head = (struct node *)malloc(sizeof(struct node));


    // Terminate if memory not allocated

    if(head == NULL)

    {

        printf("Unable to allocate memory.");

        exit(0);

    }



    // Input data of node from the user

    printf("Enter the data of node 1: ");

    scanf("%d", &data);


    head->data = data; // Link data field with data

    head->next = NULL; // Link address field to NULL



    // Create n - 1 nodes and add to list

    temp = head;

    for(i=2; i<=n; i++)

    {

        newNode = (struct node *)malloc(sizeof(struct node));


        /* If memory is not allocated for newNode */

        if(newNode == NULL)

        {

            printf("Unable to allocate memory.");

            break;

        }


        printf("Enter the data of node %d: ", i);

        scanf("%d", &data);


        newNode->data = data; // Link data field of newNode

        newNode->next = NULL; // Make sure new node points to NULL 


        temp->next = newNode; // Link previous node with newNode

        temp = temp->next;    // Make current node as previous node

    }

}



/*

 * Display entire list

 */

void traverseList()

{

    struct node *temp;


    // Return if list is empty 

    if(head == NULL)

    {

        printf("List is empty.");

        return;

    }

    

    temp = head;

    while(temp != NULL)

    {

        printf("Data = %d\n", temp->data); // Print data of current node

        temp = temp->next;                 // Move to next node

    }

}