Scribd
Upload
5 views10 pages

Java Sorting and Searching Algorithms

The document provides examples of various sorting algorithms including Quick Sort, Merge Sort, and Shell Sort, along with their implementations in Java. It also includes examples of linear search algorithms for finding elements in an array. Each algorithm is demonstrated with sample outputs before and after sorting or searching.

Uploaded by

Rehan Hussain
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
5 views10 pages

Java Sorting and Searching Algorithms

The document provides examples of various sorting algorithms including Quick Sort, Merge Sort, and Shell Sort, along with their implementations in Java. It also includes examples of linear search algorithms for finding elements in an array. Each algorithm is demonstrated with sample outputs before and after sorting or searching.

Uploaded by

Rehan Hussain
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

DURGASOFT

quickSortDesc(a,lIndex,lp-1);
quickSortDesc(a,lp+1,hIndex);
}
}
class Test
{
public static void main(String[] args)
{
Random r = new Random();
int a[] = new int[10];
for(int i=0;i<[Link];i++)
a[i] = [Link](100);
[Link]("before sorting=====>"+[Link](a));
[Link](a,0,[Link]-1);
[Link]("after sorting desc=>"+[Link](a));
}
}

output:
-------
before sorting=====>[27, 61, 26, 63, 57, 36, 14, 20, 33, 40]
after sorting desc=>[63, 61, 57, 40, 36, 33, 27, 26, 20, 14]

merge sort:
-----------
divide and combine

Ex:
---
import [Link].*;

class Demo
{
static void mergeSort(int[] a,int n)
{
if(n<2) //base condition
return;
int mid=n/2;
int l[] = new int[mid];
int r[] = new int[n-mid];
int i;
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
201  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
for(i=0;i<mid;i++)
l[i]=a[i];
for(i=mid;i<n;i++)
r[i-mid]=a[i];
mergeSort(l,mid);
mergeSort(r,n-mid);
merge(a,l,r,mid,n-mid);
}
static void merge(int a[],int l[],int r[],int left,int right){
int i=0,j=0,k=0;
while(i<left && j<right){
if(l[i]<=r[j])
a[k++]=l[i++];
else
a[k++]=r[j++];
}
while(i<left)
a[k++]=l[i++];
while(j<right)
a[k++]=r[j++];
}
}

class Test
{
public static void main(String[] args)
{
Random r = new Random();
int[] a = new int[10];

for(int i=0;i<[Link];i++)
{
a[i] = [Link](100);
}

[Link]("Before Sorting====> "+[Link](a));


[Link](a,[Link]);
[Link]("After Sorting====> "+[Link](a));
}
}

output:
-------
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
202  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
Before Sorting====> [61, 36, 17, 78, 23, 36, 58, 47, 11, 9]
After Sorting====> [9, 11, 17, 23, 36, 36, 47, 58, 61, 78]

Ex:
---
import [Link].*;

class Demo
{
static void mergeSort(int[] a,int n)
{
if(n<2) //base condition
return;
int mid=n/2;
int l[] = new int[mid];
int r[] = new int[n-mid];
int i;
for(i=0;i<mid;i++)
l[i]=a[i];
for(i=mid;i<n;i++)
r[i-mid]=a[i];
mergeSort(l,mid);
mergeSort(r,n-mid);
merge(a,l,r,mid,n-mid);
}
static void merge(int a[],int l[],int r[],int left,int right){
int i=0,j=0,k=0;
while(i<left && j<right){
if(l[i]>=r[j])
a[k++]=l[i++];
else
a[k++]=r[j++];
}
while(i<left)
a[k++]=l[i++];
while(j<right)
a[k++]=r[j++];
}
}

class Test
{
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
203  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
public static void main(String[] args)
{
Random r = new Random();
int[] a = new int[10];

for(int i=0;i<[Link];i++)
{
a[i] = [Link](100);
}

[Link]("Before Sorting====> "+[Link](a));


[Link](a,[Link]);
[Link]("After Sorting====> "+[Link](a));
}
}

output:
-------
Before Sorting====> [14, 82, 65, 12, 60, 44, 80, 96, 52, 35]
After Sorting====> [96, 82, 80, 65, 60, 52, 44, 35, 14, 12]

shell sorting:
--------------
Ex:
---
import [Link].*;

class Demo
{
static void shellSortAsc(int[] a,int n)
{
int gap,i,j,temp;
for(gap=n/2;gap>=1;gap=gap/2)
{
for(j=gap;j<n;j++)
{
for(i=j-gap;i>=0;i=i-gap)
{
if(a[i+gap]>a[i])
break;
else
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
204  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
{
temp=a[i+gap];
a[i+gap]=a[i];
a[i]=temp;
}
}
}
}
}
}

class Test
{
public static void main(String[] args)
{
Random r = new Random();
int[] a = new int[10];

for(int i=0;i<[Link];i++)
{
a[i] = [Link](100);
}

[Link]("Before Sorting====> "+[Link](a));


[Link](a,[Link]);
[Link]("After Sorting====> "+[Link](a));
}
}

output:
-------
Before Sorting====> [5, 9, 68, 8, 60, 7, 89, 31, 35, 15]
After Sorting====> [5, 7, 8, 9, 15, 31, 35, 60, 68, 89]

Ex:
---
import [Link].*;

class Demo
{
static void shellSortDesc(int[] a,int n)
{
int gap,i,j,temp;
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
205  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
for(gap=n/2;gap>=1;gap=gap/2)
{
for(j=gap;j<n;j++)
{
for(i=j-gap;i>=0;i=i-gap)
{
if(a[i+gap]<a[i])
break;
else
{
temp=a[i+gap];
a[i+gap]=a[i];
a[i]=temp;
}
}
}
}
}
}

class Test
{
public static void main(String[] args)
{
Random r = new Random();
int[] a = new int[10];

for(int i=0;i<[Link];i++)
{
a[i] = [Link](100);
}

[Link]("Before Sorting====> "+[Link](a));


[Link](a,[Link]);
[Link]("After Sorting====> "+[Link](a));
}
}

output:
-------
Before Sorting====> [86, 70, 36, 98, 4, 59, 58, 41, 44, 14]
After Sorting====> [98, 86, 70, 59, 58, 44, 41, 36, 14, 4]

DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,


206  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
searching algo:
---------------
it is used to check whether an obj is existed in the array or not.

Linear and Binary search

Ex:
---
import [Link].*;

class Demo
{
static int linearSearch(int a[],int key){
int i,index=-1;
for(i=0;i<[Link];i++){
if(key==a[i])
{
index=i;
break;
}
}
return index;
}
}

class Test
{
public static void main(String[] args)
{
Scanner obj = new Scanner([Link]);
int[] a = {10, 11, 12, 13, 11, 12, 11, 8, 19, 11};
[Link]("Array="+[Link](a));
[Link]("Enter key element to search:");
int key = [Link]();

[Link]([Link](a,key));
}
}

output:
-------
C:\prakashclasses>java Test
Array=[10, 11, 12, 13, 11, 12, 11, 8, 19, 11]
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
207  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
Enter key element to search:
8
7

C:\prakashclasses>java Test
Array=[10, 11, 12, 13, 11, 12, 11, 8, 19, 11]
Enter key element to search:
11
1

C:\prakashclasses>java Test
Array=[10, 11, 12, 13, 11, 12, 11, 8, 19, 11]
Enter key element to search:
99
-1

Ex:
---
import [Link].*;

class Demo
{
static ArrayList linearSearch(int a[],int key){
int i,c=0;
ArrayList list = new ArrayList();
for(i=0;i<[Link];i++){
if(key==a[i])
{
[Link](i);
c++;
if(c>=2)
break;

}
}
return list;
}
}

class Test
{
public static void main(String[] args)
{
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
208  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
Scanner obj = new Scanner([Link]);
int[] a = {10, 11, 12, 13, 11, 12, 11, 8, 19, 11};
[Link]("Array="+[Link](a));
[Link]("Enter key element to search:");
int key = [Link]();

[Link]([Link](a,key));
}
}

output:
-------
C:\prakashclasses>java Test
Array=[10, 11, 12, 13, 11, 12, 11, 8, 19, 11]
Enter key element to search:
11
[1, 4]

C:\prakashclasses>java Test
Array=[10, 11, 12, 13, 11, 12, 11, 8, 19, 11]
Enter key element to search:
10
[0]

C:\prakashclasses>java Test
Array=[10, 11, 12, 13, 11, 12, 11, 8, 19, 11]
Enter key element to search:
12
[2, 5]

Ex:
---
import [Link].*;

class Demo
{
static ArrayList linearSearch(int a[],int key){
int i;
ArrayList list = new ArrayList();
for(i=0;i<[Link];i++){
if(key==a[i])
[Link](i);
}
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
209  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
return list;
}
}

class Test
{
public static void main(String[] args)
{
Scanner obj = new Scanner([Link]);
int[] a = {10, 11, 12, 13, 11, 12, 11, 8, 19, 11};
[Link]("Array="+[Link](a));
[Link]("Enter key element to search:");
int key = [Link]();

[Link]([Link](a,key));
}
}

output:
-------
C:\prakashclasses>java Test
Array=[10, 11, 12, 13, 11, 12, 11, 8, 19, 11]
Enter key element to search:
10
[0]

C:\prakashclasses>java Test
Array=[10, 11, 12, 13, 11, 12, 11, 8, 19, 11]
Enter key element to search:
12
[2, 5]

C:\prakashclasses>java Test
Array=[10, 11, 12, 13, 11, 12, 11, 8, 19, 11]
Enter key element to search:
11
[1, 4, 6, 9]

Ex:
---
import [Link].*;

class Demo
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
210  88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]

You might also like