정렬

public class start {
	private static int[] num = {2, 1, 3, 4, 5, 27, 8, 6}; 
			
	public static void main(String[] args) {
		bubbleSort(num, num.length);
		for (int a : num) {
			System.out.print(a + " "); }


	}
	
	public static void bubbleSort(int[] a, int length) {
		int room;
		int temp;
		for(int i=length-1; i>0; i--) {
			for(int j=0; j<i; j++) {
				if(a[j]>a[j+1]) {
					temp=a[j+1];
					a[j+1]=a[j];
					a[j]=temp;
				}
			}
		}
	}
	
}

//버블정렬이다. 버블정렬은 연속된 두개의 자리를 비교하면서,
//총 5개의 방이 있으면, 4번을 반복해서, 
//앞에서부터 두개씩 바꾸어 나가면서 끝까지 바꾸어나가고, 
//끝까지 바꾸면, 그 끝의 위치를 -1하여 그 앞까지 바꾸는 식이다.

public class start {
	private static int[] num = {2, 1, 3, 4, 5, 27, 8, 6}; 
			
	public static void main(String[] args) {
		selectionSort(num, num.length);
		for (int a : num) {
			System.out.print(a + " "); }


	}
	
	public static void selectionSort(int[] a, int length) {
		int room;
		int temp;
		
		for(int i=length-1; i>0; i--) {
			room=i;
			for(int j=i-1; j>=0; j--) {
				if(a[room]<a[j]) {
					room=j;
				}
			}
			temp=a[i];
			a[i]=a[room];
			a[room]=temp;
		}
	
	}
	
}

//가장 기본적인 선택정렬이다. 선택정렬은 맨 뒤에서 혹은 맨 앞에서부터 차례대로 지나가면서,
//젤 큰 원소를 뒤로 ,혹은 젤 작은 원소를 앞으로 빼어내는 식이다.
//이 코드는 뒤에서 부터 큰 수를 빼왔다.

public class start {
	private static int[] num = {2, 1, 3, 4, 5, 27, 8, 6}; 
			
	public static void main(String[] args) {
		insertionSort(num, num.length);
		for (int a : num) {
			System.out.print(a + " "); }


	}
	
	public static void insertionSort(int[] a, int length) {
		int temp;
		
		for(int i=1; i<length; i++) {
			for(int j=i; j>0; j--) {
				if(a[j-1]>a[j]) {
					temp=a[j-1];
					a[j-1]=a[j];
					a[j]=temp;				
					}
			}	
		}
	}
	
}

//삽입 정렬이다. 삽입정렬은 첫번째가 완료된 정렬이라 생각하고서, 그다음 인덱스부터, 
//점점 아래 인덱스로 비교하면서 작은값을 앞쪽으로 정리하는 것ㅅ이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		int n=Integer.parseInt(br.readLine());
		int[] num=new int[10000001];
		for(int i=0; i<n; i++) {
			num[Integer.parseInt(br.readLine())]++;
		}
		
		for(int i=0; i<num.length; i++) {
			if(num[i]==0) {
				continue;
			}
			else {
				for(int j=0; j<num[i]; j++) {
					bw.write(i+"\n");
				}
			}
		}
		bw.flush();
	}
}

//기수정렬, 주어지는 수의 범위를 모두 int배열에 저장하고서,
//수가 주어질때마다 그 수에해당하는 방을 ++해준다.
//그러고나서 마지막에, 각각의 방에 갯수만큼 출력,
//즉 수가 5 5 3 4 2 1로 들어온다면, 각각 
//1번방,2번방,3번방,4번방 +1, 5번방은 +2를 하고서, 
//각각의 방의 수만큼 숫자를 출력한다.
//방이 +1인 방들은
//1, 2, 3,4 
//5번방은 2개이므로, 
//1/2/3/4/55/

ArrayList<Integer> num=new ArrayList<>();
		int n=Integer.parseInt(br.readLine());
		for(int i=0; i<n; i++) {
			num.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(num);
		for(Integer e: num) {
			bw.write(e+"\n");
		}
        
 
 //collection.sort를 이용한 정렬. 이경우에는 퀵, 삽입, 선택, 버블정렬보다 시간복잡도는 낮으나,
 //각 숫자가 한개씩만 나오는 경우 즉 중복이 없는 경우에는 기수정렬에 2배가량 압도적으로 밀린다.
 //기수정렬의 효율성이 어떻게 보면, 반복이 없는 케이스에서는 거의 넘사벽