Untitled Untitled Untitled Untitled
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281
// Bubble sort in Java
import java.util.*;
class Main {
static void bubbleSort(int[] arr){
int size = arr.length;
for(int i=0;i<size-1;i++){
for(int j=0;j<size-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 countingSort(int[] arr){
// if(arr.length<=1){
// return;
// }
// int max= arr[0];
// for(int i=1;i<=arr.length-1;i++){
// if(arr[i]>max){
// max=arr[i];
// }
// }
// int[] count = new int[max+1];
// for(int i=0;i<arr.length;i++){
// count[arr[i]]++;
// }
// for(int j=1;j<arr.length;j++){
// count[j]+=count[j-1];
// }
//
// int[] output = new output[arr.length];
//
// for(int i=0;i<arr.length;i++){
// output[count[arr[i]]]=arr[i];
// count[arr[i]]--;
// }
// for(int i=0;i<arr.length;i++){
// arr[i]=count[i];
// }
// }
// static void insertionSort(int[] arr){
// if(arr.length<=1){
// return;
// }
// for(int i=1;i<=arr.length-1;i++){
// int ith=arr[i];
// int j=i-1;
// while(j>=0 && ith<arr[j]){
// arr[j+1]= arr[j];
// j--;
// }
// arr[j+1]=ith;
// }
// }
static void insertionSort(int[] arr){
if(arr.length<=1){
return;
}
for(int i=0;i<arr.length;i++){
int temp= arr[i];
int index=i-1;
while(index>=0 && arr[index]>temp){
arr[index+1]=arr[index];
index--;
}
arr[index+1]= temp;
}
}
static void mergeSort(int[] arr){
if(arr.length<=1) return;
int[] aux= new int[arr.length];
mergeSortHelper(arr,aux,0,arr.length-1);
}
static void mergeSortHelper(int[] arr, int[] aux, int start, int end){
if(start<end){
int mid= start+ ((end-start))/2;
mergeSortHelper(arr,aux, start, mid);
mergeSortHelper(arr,aux,mid+1,end);
merge(arr, aux, start, mid, end);
}
}
static void merge(int[] arr,int[] aux,int start,int mid,int end){
for(int i=start;i<=end;i++){
aux[i] = arr[i];
}
int i=start;
int k= start;
int j=mid+1;
// int n= end-start+1;
// int[] aux= new int[n];
while(i<=mid && j<=end ){
if(aux[i]<=aux[j]){
arr[k]=aux[i];
i++;
}else{
arr[k]=aux[j];
j++;
}
k++;
}
while(i<=mid ){
arr[k]=aux[i];
i++;
k++;
}
while(j<=end ){
arr[k]=aux[j];
j++;
k++;
}
}
static void quickSort(int[] arr){
if(arr.length<=1){
return;
}
quickSortHelper(arr,0, arr.length-1);
}
static void quickSortHelper(int[] arr, int start, int end){
if(start<end){
int pi= partition(arr,start,end);
quickSortHelper(arr,start,pi-1);
quickSortHelper(arr,pi+1,end);
}
}
static int partition(int[] arr, int start, int end){
int pivot = arr[end];
int i=start;
for(int j=start;j<end;j++){
if(arr[j]<=pivot){
swap(arr,i,j);
i++;
}
}
swap(arr,i,end);
return i;
}
// public static void mergeSort(int[] arr){
// if(arr.length<=1){
// return;
//
// }
// mergeSortHelper(arr,0,arr.length-1);
//
// }
// public static void mergeSortHelper(int[] arr, int start,int end){
// if(start<end){
// int mid= start+(end-start)/2;
// mergeSortHelper(arr,start,mid);
// mergeSortHelper(arr,mid+1,end);
// merge(arr, start,mid,end);
// }
//
// }
// public static void merge(int[] arr, int start, int mid,int end){
// int n1=mid-start+1;
// int n2=end-mid;
// int[] l= new int[n1];
// int[] m= new int[n2];
// int i,j;
// for( i=0;i<n1;i++){
// l[i]= arr[start+i];
// }
// for( j=0;j<n2;j++){
// m[j] = arr[mid+1+j];
// }
// i=0;
// j=0;
// int k=start;
// while(i<n1 && j<n2){
// if(l[i]<=m[j]){
// arr[k]=l[i];
// i++;
// }else{
// arr[k]=m[j];
// j++;
// }
// k++;
//
// }
// while(i<n1){
// arr[k]=l[i];
// i++;
// k++;
// }
// while(j<n2){
// arr[k]=m[j];
// j++;
// k++;
// }
// }
public static void swap(int[] arr,int index1,int index2){
int temp= arr[index1];
arr[index1]= arr[index2];
arr[index2]= temp;
}
public static void random(int[] arr, int start, int end){
Random rand = new Random();
int pivotIndex= rand.nextInt(end-start)+start;
swap(arr,pivotIndex,end);
}
// public static void quickSort(int[] arr){
// if(arr.length<=1){
// return;
// }
// quickSortHelper(arr,0,arr.length-1);
//
// }
// public static void quickSortHelper(int[] arr, int start, int end){
// if(start<end){
// int partitionIndex=partition(arr,start,end);
// quickSortHelper(arr,start,partitionIndex);
// quickSortHelper(arr,partitionIndex+1,end);
// }
// }
// public static int partition(int[] arr, int start, int end){
// random(arr,start,end);
// int pivot=arr[end];
// int i= start;
// for(int j=start;j<end;j++){
// if(arr[j]<pivot){
//
// swap(arr,i,j);
// i++;
// }
//
// }
// swap(arr,i,end);
// return i;
// }
public static void main(String[] args) {
// int[] data = { -2, 45, 0, 11, -9 };
int[] data = { 4, 2, 2, 8, 3, 3, 1 ,0,12,9};
// call method using class name
Main.quickSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
public static void selectionSort(int[] arr){
if(arr.length<=1){
return;
}
for(int i=0;i<arr.length-1;i++){
int minIndex=i;
for(int j=i+1;j<arr.length;j++){
if(arr[minIndex]>arr[j]){
minIndex=j;
}
}
swap(arr,minIndex,i);
}
}
}
Java
INFO