void bubble_sort(int arr[]){

int len=arr.length;

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

for(int j=i+1;j<N;j++){

if(arr[i]>arr[j]){

int temp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

}}}

}

Time Complexity - O(n) O(n^2) O(n^2)

void selection_sort(int arr[]) {

int N=arr.length;

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

for(int j=i+1;j<N;j++) {

int min_index=i;

if(arr[j]<arr[min_index]) {

min_index=j;

}

}

if(min_index!=i) {

int temp=arr[i];

arr[i]=arr[min_index];

arr[min_index]=temp;

}

}

}

Time Complexity - O(n^2) O(n^2) O(n^2)

void insertion_sort(int arr[]) {

int N=arr.length;

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

int key=arr[i];

int j=i-1;

while(j>=0 && arr[j]>arr[i]) {

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

j--;

}

arr[j+1]=key;

}

}

Time Complexity - O(n) O(n^2) O(n^2)

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

int p=left;

int q=mid+1;

int A[]=new int[right-left+1];

int k=0;

for(int i=left;i<=right;i++){

if(p>mid)

A[k++]=arr[q++];

else if(q>right)

A[k++]=arr[p++];

else if(arr[p]<arr[q])

A[k++]=arr[p++];

else

A[k++]=arr[q++];

}

for(int i=0;i<k;i++)

arr[left++]=A[i];

}

void merge_sort(int arr[],int left,int right) {

if(left<right){

int mid=(left + right)/2;

merge_sort(arr,left,mid);

merge_sort(arr,mid+1,right);

merge(arr,left,mid,right);

}

}

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

Time Complexity - O(n*log n) O(n*log n) O(n*log n)

void partition(int arr[],int left,int right){

int pivot=arr[right];

int i=left-1;

for(int j=left;j<right;j++){

if(arr[j]<pivot){

i++;

int temp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

}

int temp=arr[i+1];

arr[i+1]=arr[right];

arr[right]=temp;

}

void quick_sort(int arr[],int left,int right) {

if(left<right){

int point=partition(arr,left,right);

quick_sort(arr,left,point-1);

quick_sort(arr,point+1,right);

}

}

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

Time Complexity - O(n*log n) O(n*log n) O(n^2)

void max_heapify(int arr[],int N,int index){

int largest=arr[index];

int left=2*index;

int right=left+1;

if(left<=N && arr[left]>arr[largest])

largest=left;

if(right<=N && arr[right]>arr[largest])

largest=right;

if(largest!=index){

int temp=arr[largest];

arr[largest]=arr[index];

arr[index]=temp;

max_heapify(arr,N,largest);

}

}

void heap_sort(int arr[]) {

int N=arr.length;

for(int i=N/2;i>=1;i--) {

max_heapify(arr,N,i);

}

}

heap_sort(arr);

Time Complexity - O(n*log n) O(n*log n) O(n*log n)

void counting_sort(int arr[],int N) {

int count[]=new int[256];

int output[]=new int[N];

for(int i=0;i<N;i++)

count[arr[i]]++;

for(int i=1;i<256;i++)

count[i]+=count[i-1];

for(int i=N-1;i>=0;i--){

output[count[arr[i]]-1]=arr[i];

count[arr[i]]--;

}

for(int i=0;i<N;i++)

arr[i]=output[i];

}

counting_sort(arr);

Time Complexity - O(n+k) O(n+k) O(n+k) ( k->range of input )

void counting_sort(int arr[],int N,int exp) {

int count[]=new int[10];

int output[]=new int[N];

for(int i=0;i<N;i++)

count[(arr[i]/exp)%10]++;

for(int i=1;i<10;i++)

count[i]+=count[i-1];

for(int i=N-1;i>=0;i--){

output[count[(arr[i]/exp)%10] - 1]=arr[i];

count[(arr[i]/exp)%10]--;

}

for(int i=0;i<N;i++)

arr[i]=output[i];

}

void radix_sort(int arr[],int N){

int max=getMax(arr);

for(int exp=1;max/exp>0;exp*=10)

counting_sort(arr,N,exp);

}

radix_sort(arr,N);

Time Complexity - O(n*k) O(n*k) O(n*k) or O(d*(n+k))

void bucket_sort(int arr[],int N) {

Vector<Float>[] bucket=new Vector[N];

for(int i=0;i<N;i++)

bucket[i]=new Vector<Float>();

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

int index=arr[i]*N;

bucket[index].add(arr[i]);

}

for(int i=0;i<N;i++)

Collections.sort(bucket[i]);

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

for(int j=0;j<bucket[i].size();j++)

arr[index++]=bucket[i].get(j);

}

}

bucket_sort(arr,N);

Time Complexity - O(n+k) O(n+k) O(n^2)