📌 문제

[2750] 수 정렬하기

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

⬇️ 입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

⬆️ 출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

💡 코드

🔹 버블 정렬 (Bubble Sort)

1. 버블 정렬 : 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 ➡️ 회전이 끝날 때 마다, 큰 수가 뒤쪽으로 이동하여 고정되는 형태
   
   

import java.io.*;
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[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		for(int i=n-1;i>0;i--) {
			for(int j=0;j<i;j++) {
				if(arr[j] > arr[j+1]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
	
		for(int i=0;i<n;i++)
			bw.write(arr[i] + "\n");

		br.close();
		bw.close();
	}
}	

🔹 삽입 정렬 (Insertion Sort)

2. 삽입 정렬 : 두 번째 자료부터 그 앞의 자료들과 비교하여 삽입할 위치를 지정하여 정렬하는 알고리즘 ➡️ 회전이 끝날 때마다 지정한 자리에 자료를 삽입하는 형태
   

import java.io.*;
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[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		int i, j, key;
		for(i=1;i<n;i++) {
			key = arr[i];
			
			for(j=i-1;j>=0 && arr[j]>key;j--)
				arr[j+1] = arr[j];
	
			arr[j+1] = key;
		}
	
		for(i=0;i<n;i++)
			bw.write(arr[i] + "\n");

		br.close();
		bw.close();
	}
}	

🔹 선택 정렬 (Selection Sort)

3. 선택 정렬 : 첫 번째 자료부터 뒤 쪽 자료들을 차례대로 비교하여 최솟값과 자리를 교환하는 알고리즘 ➡️ 회전이 끝날 때 마다, 작은 수가 앞쪽으로 이동하여 고정되는 형태

import java.io.*;
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[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		for(int i=0;i<n-1;i++) {
			int idx = i;;
			
			for(int j=i+1;j<n;j++) {
				if(arr[j] < arr[idx]) idx = j;
			}
			
			int tmp = arr[i];
			arr[i] = arr[idx];
			arr[idx] = tmp;
		}
	
		for(int i=0;i<n;i++)
			bw.write(arr[i] + "\n");

		br.close();
		bw.close();
	}
}