1.
Solve problems by using sequential search, binary search, and quadratic
algorithms (selection, insertion) sorting
AIM:
To write a java program to develop a Java application to solve sequential search, binary search and
quadratic sorting algorithms.
ALGORITHM:
Binary Search:
1.Take four variables => start, end, middle,target.
2.Find the middle element of an array => now your array is divided into two parts left and right.
3.1f target element > middle
element => search in right part.
4.If target element <
middle element =>search in left part.
5.If middle
6.1f
element target element
start > end => element
not found.
> return that element.
Linear Search:
1.Start.
2. Traversethe
array
3.Match the key element
with array element
4. Ifkey element is
found, return the index position of the
5. Ifkey array element
element is not found, return -1
6.End.
Insertion Sort:
1.Start.
2.Repeat steps 2 to 4 till the array end is reached.
3.Compare the element at current index iwith its
predecessor. Ifit is smaller, repeat step 3.
4.Keep shifting elements from the sorted"
section of the array till the correct location of the
found. key is
5.Incrementloop variable.
6.End.
SelectionSort:
1.Start.
2.Run two loops: an inner loop and an outer loop.
3.Repeat steps till the minimum element are found.
4.Mark the element marked by the outer loop variable as a minimum.
5.If the current element in the inner loop is smallerthan the
marked minimum element,change the
value of the minimum element to the current element.
6.Swap the value of the minimum element with the element marked by the outer loop variable.
7.End.
PROGRAM: (i)
publicclass BinarySearchExample
public static void binary Search(int arr(], int first, int last, int key)
int mid = (first + last)/2;
while( first <= last )
if (arr[mid]< key)
first =mid + 1;
else if (arr[mid]=key )
{
System.out.printin("Element is found at index: "+mid);
break;
else
{
last =mid - 1;
}
mid = (first +last)/2;
if (
first > last ){
System.out.printin("Element is not found!");
public static void main(Stringargs[1){
int arr[] ={10,20,30,40,50};
int key =30;
int last=arr.length-1;
binarySearch(arr,0, last, key);
OUTPUT:
Element is found at index: 2
PROGRAM: (ii)
import java.util.Scanner;
public class LinearSearchExample
public static int linearSearch(int[]
arr, int key)
for(int
i-0;i<arr.length;it+)
if(arr[i] key)
return i:
return -1;
public static void
main(String a(])
int[] al=
{10,20,30,50,70,90};
int key = 50;
System.out.println(key+"
is found at index: "+linearSearch(al,
key));
OUTPUT:
50is found at index: 3
PROGRAM: (ii)
public class Insertion SortExample
public static voidinsertion Sort(int arrayl])
int n =array.length;
for (int j=1;j <n; j++) {
int key =array[j);
int i=j-1;
while ( >-l) && (
(i array [i] > key ))
array [i+1]= array [i]:
i--;
array[i+1]=key;
public static void main(String a(]D{
int[] arrl ={7,19,3,2,43,1 1,58,22};
System.out.println ("Before Insertion Sort");
for(int i:arrl)
System.out.print(i+" ");
System.out.printin);
insertionSort(arr 1 );//sorting array using insertion sort
System.out.printin("A fter Insertion Sort");
for(int i:arrl)
System.out.print(it" ");
OUTPUT:
Before Insertion Sort
7 193 2 43 11 58 22
After InsertionSort
23711 19 2243 58
PROGRAM:(iv)
public class SelectionSortExample
public static void selectionSort(int[] arr)
for(int =0; i<
i arr.length - 1; itt)
int index=i;
for (int j=it 1;j < arr.length; j++)
if (arr[i] < arr[index))
index =j://searching for lowest index
int smallerNumber = arr[index];
arr[index] =arr[il;
arr[i] =smallerNumber;
}
public static void main(String a(])
int[] arrl ={9,14,3,2,43,1 1,58,22};
System.out.println("Before Selection Sort");
for(int i:arrl)
{System.out.print(i+" ");
System.out.println0;
selectionSort(arr l );//sorting array using selection sort
System.out.printin("After Selection Sort");
for(int i:arrl){
System.out.print(i+" "):
OUTPUT:
Before SelectionSort
9 14324311 5822
After SelectionSort
239 11 14 224358
Result:
Thus the java application program to solve searching and sorting techniques has been
executed successfully.
2. Develop stack and queue data structuresusing classes and objects.
AIM:
To develop a Java application to implement stack and queue data structures using classes
and objects.
ALGORITHM:
Stack:
1. Start the program.
2. Push inserts an item at the top of the stack (i.e., above its current top element).
3. Pop removes the object at the top of the stack and returns that object from the function.
4. The stack size will be decremented by one.
5. isEmpty tests if the stackis empty or not.
6. isFull tests if the stack is full or not.
7. Peek returns the object atthe top of the stack without removing it from the stack or modifying
the stackin any way.
8. Size returns the total number of elementspresent in the stack.
9. Stop the program.
Queue:
Enqueue Operation
Step 1 -Check if the queue is full.
Step 2- If thequeue is full, produce overflow error and exit.
Step 3 -If the queue not increment rear pointer to point the next empty space.
is full,
Step 4 -Add data element to the queue location, where the rear pointing. is
Step 5 -return success.
Dequeue Operation
Step 1 -Check if the queue is empty.
Step 2- If the queue is empty, produce underflow error and exit.
Step 3 -If the queue is not empty, accessthe data where front is pointing.
Step 4- Increment front pointer topoint to the next available data element.
Step 5 -Return success.
|
PROGRAM: (i)
Java code for stack implementation
import java.io.*;
import java.util.*;
class Test
II Pushing element on the top of the stack
static void stack_ push(Stack<Integer>stack)
for(int i =0; i< 5; it+)
stack.push(i):
I/Popping element from the top of the stack
static void stack_pop(Stack<lnteger>stack)
System.out.println("Pop
Operation:");
for(int i =0; i < 5;it+)
Integery =(Integer) stack.pop0;
System.out.println(y):
I/ Displaying element on the top of the stack
static void stack_peek(Stack<Integer> stack)
Integer element =(nteger) stack.peek();
System.out.printin("Element
on stacktop: "+ element);
I| Searching element in the stack
static void stack search(Stack<Integer> stack, int element)
Integer pos = (Integer) stack.search(element);
if(pos ==-1)
System.out.println("Element
not found");
else
System.out.println("Element
is found at position: "+pos);
public static void main (String[] args)
Stack<Integer>stack= new Stack<Integer>0;
stack push(stack):
stack_ pop(stack);
stack_ pushstack);
stack peek(stack);
stack_ search(stack, 2);
stack search(stack, 6);
OUTPUT:
Pop Operation:
3
2
1
Element on stack top: 4
Element is found at position:3
Element not found
PROGRAM: (ii)
II implementation of queue
I|A class to represent a queue
class Queue
int front, rear, size;
int capacity;
int array[]:
public Queue(int capacity)
{
this.capacity =capacity:
front =this.size =0;
rear =capacity - 1;
array =new int[this.capacity];
I| Queue is full when size becomes
Ilequal to the capacity
boolean isFull(Queuequeue)
return (queue.size queue.capacity);
I/Queue is empty when size is 0
boolean isEmpty(Queue queue)
return (queue.size=0);
I/ Method to add an item to the queue.
I/ Itchanges rear and size
void enqueue(intitem)
if (isFull(this)
return;
this.rear = (this.rear +1% this.capacity;
this.array[this.rear] =item;
this.size=this.size + 1;
System.out.printin(item +"enqueued to queue");
I/Method to remove an item from queue.
I/ Itchanges front and size
int dequeue)
if (isEmpty(this))
return Integer. MIN_ VALUE;
int item = this.array[this. front];
this.front= (this.front + 1)% this.capacity;
this.size =this.size - 1;
return item;
I| Method to get front of queue
int front()
{
if (isEmpty(this)
return Integer.MIN VALUE;
return this.array[this.front];
I|Method to get rear of queue
int rear()
if (isEmpty (this))
return Integer.MIN_VALUE;
return this.array[this.rear];
I|Driver class
public class Test
public static void main(String[]args)
Queue queue =new Queue(1000);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
System.out.println(queue.dequeue (0 +"dequeued from queueln");
System.out.println("Front item is "+ queue.front();
System.out.println("Rear item is "+queue.rear();
OUTPUT:
10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40
Result:
Thus the java application to implement stack and queue data structures using classes and
objects has been done successfully.
