Sorting

// BUBBLE SORT( STABLE AND ADAPTIVE)


import java.util.*;
public class Main
{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n =sc.nextInt();
		int a[] = new int[n];
		for(int i=0;i<n;i++){
		    a[i] =sc.nextInt();
		}
		
		for(int i=0;i<n-1;i++){
		    boolean flag = true;
		    for(int j=0;j<n-1-i;j++){
		        if(a[j]>a[j+1]){
		             flag = false;
		            int temp = a[j];
		            a[j] =a[j+1];
		            a[j+1] =a[j];
		        }
		    }
		    if(flag==true){
		        break;
		    }
		}
		System.out.print(Arrays.toString(a));
	}
}

// INSERTION SORT(STABLE AND ADAPTIVE)

import java.util.*;
public class Main
{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n =sc.nextInt();
		int a[] = new int[n];
		for(int i=0;i<n;i++){
		    a[i] =sc.nextInt();
		}
		
		for(int i=1;i<n-1;i++){
		    int j=i-1;
		    while(j>=0 && a[j]>a[j+1]){
		        int temp = a[j];
		        a[j] = a[j+1];
		        a[j+1] = a[j];
		        j--;
		    }
		    
		    
		}
		System.out.print(Arrays.toString(a));
	}
}
// SELECTION SORT(NEITHER ADAPTIVE NOR STABLE)
import java.util.*;
public class Main
{
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int n =sc.nextInt();
	    int a[] = new int[n];
	    for(int i=0;i<n;i++){
	        a[i]=sc.nextInt();
	    }
	    selectionsort(a);
		
	}public static void selectionsort(int arr[])
	{
	    int n = arr.length;
	    int minindex;
	    for(int i=0;i<n-1;i++){
	         minindex =i;
	         for(int j=i+1;j<n;j++){
	             if(arr[j]<arr[minindex]){
	                 minindex =j;
	             }
	         }
	         int temp = arr[i];
	            arr[i]  = arr[minindex];
	            arr[minindex] = temp;
	            System.out.println("in "+ i+"swap"+Arrays.toString(arr));
	    }
	    return ;
	}
}



// MERGE SORT(FOR TWO DIFFERENT SORTED ARRAY)
import java.util.*;

public class Main
{
	public static void main(String[] args) {
//		System.out.println("Hello World");
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int a[] = new int[m];
        for(int i=0;i<m;i++){
            a[i] = sc.nextInt();
        }
        int n = sc.nextInt();
        int b[] = new int[n];
        for(int i=0;i<n;i++){
            b[i] = sc.nextInt();
        }
        int c[] = new int[m+n];
        mergesort(a,b,c);
        System.out.println(Arrays.toString(c));
	}
	public static void mergesort(int a[] ,int b[] ,int c[]){
	    int m = a.length;
	    int n = b.length;
	    int i=0;
	    int j=0;
	    int k =0;
	     while(i<m && j<n){
	         if(a[i]<b[j]){
	             c[k] =a[i];
	             k++;
	             i++;
	         }
	         else{
	             c[k] = b[j];
	             j++;
	             k++;
	         }
	     }
	     while(i<m){
	         c[k++] = a[i++];
	     }
	     while(j<n){
	         c[k++] = b[j++];
	     }
	     return;
	}
}