Scribd
Upload
28 views21 pages

Java Sorting and Searching Algorithms

This document discusses various sorting algorithms. It begins by defining sorting and describing the different categories of sorting. It then explains concepts like passes and discusses common sorting techniques like selection sort, bubble sort, insertion sort, merge sort, quick sort and heap sort. For each technique, it provides pseudocode to illustrate the algorithm. It also includes examples of Java programs implementing selection sort, bubble sort, insertion sort and quick sort on arrays.

Uploaded by

hemanth
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views21 pages

Java Sorting and Searching Algorithms

This document discusses various sorting algorithms. It begins by defining sorting and describing the different categories of sorting. It then explains concepts like passes and discusses common sorting techniques like selection sort, bubble sort, insertion sort, merge sort, quick sort and heap sort. For each technique, it provides pseudocode to illustrate the algorithm. It also includes examples of Java programs implementing selection sort, bubble sort, insertion sort and quick sort on arrays.

Uploaded by

hemanth
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structures Using JAVA Semester IV

UNIT – V
SORTING AND SEARCHING
SORTING:
“Sorting is the process of arranging the elements in a list or collection
in increasing or decreasing order of some property”. It involves comparisons
of the data items among themselves and exchanging or replacing some of
them to achieve an arrangement of the items in the desired order.

Sorting can be classified into two categories, internal sorting and


external sorting, depending on where the input data resides, either in the
internal memory or in the external memory.

PASSES:
Only two items can be compared at a time. For comparing all the
elements in a given list, we have to traverse the entire list from left to right,
taking two adjacent items at a time and perform an exchange between two
items if necessary. This traversal of the list each time is called a pass.

SORTING TECHNIQUES:
There are different types sorting techniques. They are:

1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Heap Sort

SELECTION SORT:
One of the easiest ways to sort elements is by selection sort.
Beginning with the first element in the list of elements, a search is
performed to locate the element which is smallest.

The selection sort algorithm sorts an array by repeatedly finding the


next smallest element and placing it in its next proper position (within the
desired order) continues until all elements have been sorted in ascending
order.

The algorithm maintains two subarrays in a given array:

1. The subarray which is already sorted.


Data Structures Using JAVA Semester IV

2. Remaining subarray which is unsorted.

In every, iteration of selection sort the minimum element (considering


ascending order) from the unsorted subarray is picked and moved to the
sorted subarray.

Program:

import [Link].*;

public class SelectionSort {

public static void main(String a[ ]) throws IOException {

int i, size;

int array[ ];

DataInputStream in = new DataInputStream([Link]);

[Link]("Enter array size:");

size = [Link]([Link]( ));

array = new int[size];

[Link]("Enter any "+size+" integers:");


Data Structures Using JAVA Semester IV

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

[Link]("Enter "+(i+1)+" number:");

array[i] = [Link]([Link]());

[Link](" Selection Sort\n");

[Link]("Values Before the sort:\n");

for(i = 0; i < [Link]; i++)

[Link]( array[i]+" ");

[Link]( );

selection_srt(array, [Link]);

[Link]("Values after the sort:\n");

for(i = 0; i <[Link]; i++)

[Link](array[i]+" ");

[Link]( );

public static void selection_srt(int array[ ], int n)

for(int x=0; x<n; x++)

int index_of_min = x;

for(int y=x; y<n; y++)

if(array[index_of_min]>array[y])

index_of_min = y;

} }

int temp = array[x];


Data Structures Using JAVA Semester IV

array[x] = array[index_of_min];

array[index_of_min] = temp;

Output:

Enter array size: 5

Enter any 5 integers:

Enter 1 number: 9

Enter 2 number: 5

Enter 3 number: 1

Enter 4 number: 10

Enter 5 number: 2

Selection Sort

Values before the sort: 9 5 1 10 2

Values after the sort: 1 2 5 9 10

BUBBLE SORT:
Bubble sort is also known as exchange sort. Bubble Sort is the
simplest sorting algorithm that works by repeatedly swapping the adjacent
elements if they are in wrong order.

Algorithm:

1. Compare each pair of adjacent elements from the beginning of an


array and, if they are in reversed order, swap them.
2. If at least one swap has been done, repeat step 1.
Data Structures Using JAVA Semester IV

/* Program to implement Bubble sort */

import [Link].*;

public class BubbleSort {

public static void main(String a[ ]) throws IOException {

int i,size;

int array[ ];

DataInputStream in = new DataInputStream([Link]);


[Link]("Enter array size:");

size = [Link]([Link]( ));

array = new int[size];

[Link]("Enter any "+size+" integers:");

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

[Link]("Enter "+(i+1)+" number:");


Data Structures Using JAVA Semester IV

array[i] = [Link]([Link]( ));

[Link](" Bubble Sort\n");

[Link]("Values Before the sort:\n");

for(i = 0; i < [Link]; i++)

[Link]( array[i]+" ");

[Link]( );

bubble_srt(array, [Link]);

[Link]("\nValues after the sort:\n");

for(i = 0; i <[Link]; i++)

[Link](array[i]+" ");

[Link]( );

public static void bubble_srt( int a[ ], int n ) {

int i, j,t=0;

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

for(j = 1; j < (n-i); j++) {

if(a[j-1] > a[j]) {

t = a[j-1]; a[j-1]=a[j]; a[j]=t;


} } } } }

INSERTION SORT:
Insertion sorting algorithm is similar to bubble sort. But insertion sort
is more efficient than bubble sort because in insertion sort the elements
comparisons are less as compare to bubble sort. In insertion sorting
algorithm compare the value until all the prior elements are lesser than
compared value is not found.

This algorithm is more efficient than the bubble sort .Insertion sort is
a good choice for small values and for nearly-sorted values.
Data Structures Using JAVA Semester IV

/* Program to implement Insertion sort */

import [Link].*;

public class InsertionSort {

public static void main(String a[ ]) throws IOException {

int i,size;

int array[ ];

DataInputStream in = new DataInputStream([Link]);

[Link]("Enter array size:");

size = [Link]([Link]());

array = new int[size];

[Link]("Enter any "+size+" integers:");

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

[Link]("Enter "+(i+1)+" number:");

array[i] = [Link]([Link]( ));


Data Structures Using JAVA Semester IV

[Link](" Insertion Sort\n");

[Link]("Values Before the sort:\n");

for(i = 0; i < [Link]; i++)

[Link]( array[i]+" ");

[Link]();

insertion_srt(array, [Link]);

[Link]("\nValues after the sort:\n");

for(i = 0; i <[Link]; i++)

[Link](array[i]+" ");

[Link]( );

public static void insertion_srt(int array[ ], int n) {

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

int j = i;

int B = array[i];

while ((j > 0) && (array[j-1] > B)) {

array[j] = array[j-1];

j--;

array[j] = B;

}}}

QUICK SORT:
Quick sort algorithm is developed by C. A. R. Hoare. Quick sort is a
comparison sort. The working of quick sort algorithm is depending on a
divide-and-conquer strategy. A divide and conquer strategy is dividing an
array into two sub-arrays. Quick sort is one of the fastest and simplest
sorting algorithms.
Data Structures Using JAVA Semester IV

Algorithm:

1. In quick sort algorithm pick an element from array of elements. This


element is called the pivot.
2. Then compare the values from left to right until a greater element is
finding then swap the values.
3. Again start comparison from right with pivot. When lesser element is
finding then swap the values.
4. Follow the same steps until all elements which are less than the pivot
come before the pivot and all elements greater than the pivot come
after it.
5. After this partitioning, the pivot is in its last position. This is called
the partition operation.
6. Recursively sort the sub-array of lesser elements and the sub-array
of greater elements.
Data Structures Using JAVA Semester IV

/* Program implement Quick sort */

import [Link].*;

public class QuickSort {

public static void main(String a[ ]) throws IOException {

int i,size;

int array[ ];

DataInputStream in = new DataInputStream([Link]);

[Link]("Enter array size:");

size = [Link]([Link]( ));

array = new int[size];

[Link]("Enter any "+size+" integers:");

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

[Link]("Enter "+(i+1)+" number:");

array[i] = [Link]([Link]());

[Link](" Quick Sort\n");

[Link]("Values Before the sort:\n");

for(i = 0; i < [Link]; i++)

[Link]( array[i]+" ");

[Link]( );

quick_srt(array, 0, [Link]-1);

[Link]("\nValues after the sort:\n");

for(i = 0; i <[Link]; i++)

[Link](array[i]+" ");

[Link]();

public static void quick_srt(int array[ ], int low, int n) {


Data Structures Using JAVA Semester IV

int lo = low;

int hi = n;

if (lo >= n) {

return;

int mid = array[(lo + hi) / 2];

while (lo < hi) {

while (lo<hi && array[lo] < mid) {

lo++;

while (lo<hi && array[hi] > mid) {

hi--;

if (lo < hi) {

int T = array[lo];

array[lo] = array[hi];

array[hi] = T;

}}

if (hi < lo) {

int T = hi;

hi = lo;

lo = T;

quick_srt(array, low, lo);

quick_srt(array, lo == low ? lo+1 : lo, n);

}
Data Structures Using JAVA Semester IV

HEAP SORT:
A heap is a complete binary tree which is represented using array or
sequential representation.

Every heap data structure has the following properties...

1. Ordering: Nodes must be arranged in a order according to values


based on Max heap or Min heap.
2. Structural: All levels in a heap must full, except last level and
nodes must be filled from left to right strictly.

Heap is classified as:

Max Heap: A Heap is a Max heap if all the nodes having value greater than
every children of the node.

Min Heap: A Heap is a Min heap if all the nodes having value lesser than
every children of the node.

Algorithm for Heap Sort:

1. Heapify the given elements.


2. Take first element into the sorted array.
3. Replace the first position with the last element.
4. Check whether the tree is a heap or not.
If yes then go to step-2
If no then go to step-1.

Using Max Heap:


Data Structures Using JAVA Semester IV

Program:
import [Link];
public class HeapSort {
private static int N;
public static void sort(int arr[ ]) {
heapify(arr);
for (int i = N; i > 0; i--) {
swap(arr,0, i);
N = N-1;
maxheap(arr, 0);
}}
public static void heapify(int arr[ ]) {
N = [Link]-1;
for (int i = N/2; i >= 0; i--)
maxheap(arr, i);
}
public static void maxheap(int arr[ ], int i) {
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i) {
swap(arr, i, max);
maxheap(arr, max);
}}
public static void swap(int arr[ ], int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[ ] args) {
Scanner scan = new Scanner( [Link] );
[Link]("Heap Sort Test\n");
int n, i;
[Link]("Enter number of integer elements");
n = [Link]( );
int arr[ ] = new int[ n ];
[Link]("\nEnter "+ n +" integer elements");
for (i = 0; i < n; i++)
Data Structures Using JAVA Semester IV

arr[i] = [Link]( );
sort(arr);
[Link]("\nElements after sorting ");
for (i = 0; i < n; i++)
[Link](arr[i]+" ");
[Link]( );
} }
MERGE SORT:
Merge Sort is a Divide and Conquer algorithm. It divides input array
in two halves, calls itself for the two halves and then merges the two sorted
halves.

The following figure shows the merge sort process:


Data Structures Using JAVA Semester IV

Program:

import [Link].*;

public class MergeSort {

static int a[ ]=new int[15];

public class static void mergeSort(int low, int high) {

int mid;

if(low < high) {

if(mid+high)/2;

mergeSort(low, mid);

mergeSort(mid+1,high);

mergeSort(low, mid, high);

public static void merge(int low, int mid, int high) {

int b[ ]=new int[10], f=low, i=low, s=mid+1;

while((f<=mid)&&(s<=high)) {

if(a[f]<=a[s])

b[i]=a[f++];

else

b[i]=a[s++];

i++;

while(f<=mid)

b[i++]=a[f++];

while (s<=high)

b[i]=a[s++];

for(i=low;i<=high;i++)
Data Structures Using JAVA Semester IV

a[i]=b[i];

public static void main(String args[ ]) {

int size, I, low, high;

Scanner s=new Scanner([Link]);

[Link](“ENTER SIZE:”);

size=[Link]( );

[Link](“ENTER “+SIZE+”ELEMENTS:”);

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

a[i]=[Link]( );

low=0; high=size-1;

mergeSort(low,high);

[Link](“SORTED ORDER IS:”);

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

[Link](“ “+a[i]);

SEARCHING:
Search is a process of finding a value in a list of values .In other
searching is the process of locating given value position in a list of value.

Searching is classified into:

1. LINEAR SEARCH:
In Linear Search, we start with the first element of the list and
keep searching the whole list until we get the element from the list.
If a list is stored in computer’s memory as unsorted then to search
something in this list we will have to run Linear Search.

Algorithm:
Step 1: Read the search element from the user and compare, the search
element with the first element in the list.
Data Structures Using JAVA Semester IV

Step 2: If both are matching, then display "Given element found!!!" and
terminate the function

Step 3: If both are not matching, then compare search element with the
next element in the list.

Step 4: Repeat steps 3 and 4 until the search element is compared with the
last element in the list.

Step 5: If the last element in the list is also doesn't match, then display
"Element not found!!!" and terminate the function.

PROGRAM:
import [Link].*;

class LinearSearch {

public static void main(String args[ ])throws IOException {

int num[ ];

int key,pos,n,i;

BufferedReader br=new BufferedReader(new


InputStreamReader([Link]));

[Link]("Enter size of array");

n=[Link]([Link]( ));

num=new int[n];

[Link]("Enter "+n+" elements into array");


for(i=0;i<n;i++)
Data Structures Using JAVA Semester IV

num[i]=[Link]([Link]( ));
[Link]("Enter the element to be searched");

key=[Link]([Link]());

pos=linearSearch(num,n,key);

if(pos==-1)

[Link]("search is unsuccessful");

else {

[Link]("search is successful");

[Link](key +" found at position "+(pos+1));


}

static int linearSearch(int arr[], n, key) {


int i;

i=0;

while(i<n) {

if(arr[i]=key)

return i;

if(arr[i]>key)

break;

i++;

return -1;

}}}

OUTPUT:
Enter size of array: 5

Enter 5 elements into array:

10 20 30 40 50

Enter the element to be searched: 40

Search is successful

40 found at position 4
Data Structures Using JAVA Semester IV

2. BINARY SEARCHING:
It is also known as half-interval search. The binary search
algorithm can be used with only sorted list of element.

The process of searching a sorted array by repeatedly dividing the


search interval in half is called “Binary Search”.

Algorithm:

Step 1: Read the search element from the user and find the middle element
in the sorted list.

Step 2: Compare the search element with the middle element in the sorted
list.

Step 4: If both are matching, then display "Given element found!!!"


then terminate the function.

Step 5: If both are not matching, then check whether the search element is
smaller or larger than middle element.

Step 6: If the search element is smaller than middle element, then repeat
steps 2, 3, 4 and 5 for the left sublist of the middle element.

Step 7: If the search element is larger than middle element, then repeat
steps 2, 3, 4 and 5 for the right sublist of the middle element.

Step 8: Repeat the same process until we find the search element in the list
or until sublist contains only one element.

Step 9: If that element also doesn't match with the search element, then
display "Element not found in the list!!!" and terminate the function.
Data Structures Using JAVA Semester IV

Program:

import [Link].*;

class BinarySearch {

public static void main(String args[ ])throws IOException {

int num[ ];

int key, pos, n, i;

BufferedReader br=new BufferedReader(new


InputStreamReader([Link]));

[Link]("Enter size of array");

n=[Link]([Link]( ));

num=new int[n];

[Link]("Enter "+n+" elements into array");

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

num[i]=[Link]([Link]( ));

[Link]("Enter the element to be searched");

key=[Link]([Link]( ));

pos=binarySearch(num, n, key);

if(pos==-1)

[Link]("Search is unsuccessful");

else {

[Link]("search is successful");

[Link](key +" found at position "+(pos+1));

static int binarySearch(int arr[ ], n, key) {

int low, high, mid;

low=0 ;

high=n-1;

while(low<high) {
mid=(low+high)/2;
Data Structures Using JAVA Semester IV

if(arr[mid]==key)

return mid;
else {

if(key>arr[mid])

low=mid+1;

else

high=mid-1;

return -1;

OUTPUT:
Enter size of array: 5

Enter 5 elements into array:

10 20 30 40 50

Enter the element to be searched: 30

Search is successful

30 found at position 3

Common questions

Powered by AI

Merge Sort utilizes the divide-and-conquer strategy by splitting the input array into halves, recursively sorting each half, and then merging the sorted halves back together. This ensures that each subarray is sorted before the merge phase, allowing the algorithm to effectively handle large datasets by breaking the problem into more manageable parts and achieving a time complexity of O(n log n).

Selection Sort and Bubble Sort differ primarily in their approach to sorting. Selection Sort selects the smallest element from the unsorted portion and swaps it with the first unsorted element, focusing on selecting the extreme element each iteration. In contrast, Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order, gradually bubbling up the largest unsorted elements to the end of the list. Hence, Selection Sort involves fewer swaps compared to Bubble Sort .

Merge Sort is considered stable because it preserves the order of equal elements as they appear in the input; that is, if two elements compare equal, they retain their sequence in both the initial array and after sorting. This property is advantageous in scenarios where the input array contains secondary keys or where maintaining an initial order is necessary for a subsequent sorting operation. The guarantee of stability is crucial for multi-dimensional data sorting tasks .

Binary Search is more efficient than Linear Search because it halves the search interval with each iteration, reducing its time complexity to O(log n) compared to the O(n) of Linear Search, which checks each element sequentially. However, the prerequisite for using Binary Search is that the data set must be sorted; without this, Binary Search cannot efficiently determine the position of the search element .

The pivot element in Quick Sort acts as a reference point that partitions the array into two sub-arrays: those elements less than the pivot and those greater. Its strategic selection ensures efficient partitioning, impacting the sorting process by aiming for near-equal partitions, which minimizes the height of the recursive tree and maintains the algorithm's efficiency. The correct choice of pivot can therefore significantly affect the overall performance and speed of Quick Sort .

Quick sort is considered one of the fastest sorting algorithms because it employs a divide-and-conquer strategy. This strategy divides the array into two sub-arrays, sorts them, and then combines them, efficiently handling the elements. The partition operation ensures elements smaller than the pivot are placed before it and those greater are placed after. This sorting mechanism contributes to its average time complexity of O(n log n).

The heap structure contributes to heap sort's efficiency by maintaining a binary tree where the parent node is always larger (Max Heap) or smaller (Min Heap) than its child nodes. This property allows for efficient element extraction and reheapification operations. By always replacing the root with the last unsorted element and ensuring the remaining elements adhere to the heap properties, heap sort maintains its O(n log n) complexity, efficiently managing data with structured priority .

Insertion Sort is more efficient than Bubble Sort in scenarios where the array is mostly sorted or when dealing with small datasets. This is because Insertion Sort minimizes the number of comparisons, as it only shifts elements necessary to insert the next sorted element in the correct position, resulting in fewer operations compared to the repetitive swapping in Bubble Sort .

Selection Sort's algorithmic approach involves repeatedly scanning the unsorted portion to find the minimum element and swapping it with the first unsorted position, leading to an O(n^2) time complexity due to its double loop structure. This inefficiency is especially pronounced in large datasets where the repeated scanning and swapping operations become significant, making it much slower compared to more advanced algorithms like Quick Sort or Merge Sort, which can achieve O(n log n) efficiency .

In the context of internal sorting, "passes" refer to complete iterations over the array where adjacent elements are compared and possibly swapped. This is a fundamental operation in sorting techniques like Bubble Sort and Selection Sort. Each pass moves elements incrementally towards their correct positions until the entire array is sorted .

You might also like