Sorting Algorithms Implementation In java

 

Selection Sort Program in java

Code:

import java.util.*;

import java.lang.*;

import java.io.*;

//selection Sort

class Test {

public static void main(String[] args){

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

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

int minVal = arr[i];

int ind = i;

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

if(arr[j] < minVal){

ind = j;

minVal = arr[j];

}

}

//swap with minimum 

int temp = arr[i];

arr[i] = minVal;

arr[ind] = temp;

}

for(int i : arr){

System.out.print(i+" ");

}

}

}

 Bubble Sort Program in java

Code::

import java.util.*;

import java.lang.*;

import java.io.*;

//Bubble Sort

class Test {

public static void main(String[] args){

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

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

//the last val is at its coorect Position

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

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

//swap

int temp = arr[j];

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

arr[j+1] = temp;

}

}

}

for(int i : arr){

System.out.print(i+" ");

}

}

}

Optimized code if the right part of the array is sorted

code:

import java.util.*;

import java.lang.*;

import java.io.*;

//Bubble Sort

class Test {

public static void main(String[] args){

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

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

//the last val is at its coorect Position

int swap = 0;

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

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

swap = 1;

//swap

int temp = arr[j];

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

arr[j+1] = temp;

}

}

if(swap==0){

break;

}

}

for(int i : arr){

System.out.print(i+" ");

}

}

}

Insrtion Sort Program in java

Code:

import java.util.*;

import java.lang.*;

import java.io.*;

//Insertion Sort

class Test {

public static void main(String[] args){

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

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

int hole = i;

int val = arr[i];

while(hole>0 && arr[hole-1]>val){

arr[hole] = arr[hole-1];

hole--;

}

arr[hole] = val;

}

for(int i : arr){

System.out.print(i+" ");

}

}

}

Merge Sort Program in java

Code ::

import java.util.*;

import java.lang.*;

import java.io.*;

class Test {

static int n1 = 0,n2=1,n3=0;

public static void main(String[] args){

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

mergeSort(arr);

for(int i : arr){

System.out.print(i+" ");

}

}

public static void mergeSort(int[] arr){

int n = arr.length;

if(n<2){

return;

}

int mid = n/2;

int[] left = new int[mid];

int[] right = new int[n-mid];

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

left[i] = arr[i];

}

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

right[i-mid] = arr[i];

}

mergeSort(left);

mergeSort(right);

merge(left,right,arr);

}

public static void merge(int[] left,int[] right,int[] arr){

int i = 0;

int j = 0;

int k = 0;

while(i<left.length && j<right.length){

if(left[i]<right[j]){

arr[k] = left[i];

i++;

}else{

arr[k] = right[j];

j++;

}

k++;

}

while(i!=left.length){

arr[k] = left[i];

i++;

k++;

}

while(j!=right.length){

arr[k] = right[j];

j++;

k++;

}

}

}

 Quick Sort Program in java

Code::

import java.util.*;

import java.lang.*;

import java.io.*;

//Quick Sort

class Test {

public static void main(String[] args){

int[] arr = {8,7,3,4,11,13,14,2,17};

quickSort(arr,0,arr.length-1);

for(int i : arr){

System.out.print(i+ " ");

}

}

public static void quickSort(int[] arr,int s,int e){

if(s>=e){

return;

}

int pIndex = partition(arr,s,e);

quickSort(arr,s,pIndex-1);

quickSort(arr,pIndex+1,e);

}

public static int partition(int[] arr,int s,int e){

int pivot = arr[e];

int pIndex = s;

for(int i=s;i<=e-1;i++){ 

if(arr[i] <= pivot){

int temp = arr[i];

arr[i] = arr[pIndex];

arr[pIndex] = temp;

pIndex++;

}

}

int temp = arr[e];

arr[e] = arr[pIndex];

arr[pIndex] = temp;

return pIndex;

}

}