// 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); } } }