[백준] 2750 수 정렬하기(Arrays.sort, 선택, 삽입, 퀵)

문제

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

입력

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

출력

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

예제 입력 1 복사

5
5
2
3
4
1

예제 출력 1 복사

1
2
3
4
5

---

1. Arrays.sort 사용하기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.io.IOException;

public class Main {

	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr); 
		for(int val:arr) {
			System.out.println(val);
		}
	}
}

2. 선택정렬 사용하기

선택정렬(첫번째 인덱스부터 시작해 뒤의 인덱스들의 값과 비교) : 제일 기본 시간복잡도는 On2

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

public class Main {

	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		selection_sort(arr);  
		for(int val:arr) {
			System.out.println(val);
		}
	}
	public static void selection_sort(int[] arr) {
		for(int i=0;i<arr.length;i++) {
			for(int j=i+1;j<arr.length;j++) {
				if(arr[i]>arr[j]) {
					swap(arr,j,i);
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
	}
}

3. 삽입정렬 사용하기

삽입정렬(선택한 요소를 앞쪽의 알맞은 위치에 삽입하는 작업 반복 정렬): On2(최선일때O(N))

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

public class Main {

	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		insertion_sort(arr); 
		for(int val:arr) {
			System.out.println(val);
		}
	}
    
	public static void insertion_sort(int[] arr) {
		for(int i=1;i<arr.length;i++) {
			int temp = arr[i];
			int j;
			for(j=i; j>0 && arr[j-1] > temp; j--) {
				arr[j] = arr[j-1];
			}
			arr[j] = temp;
		}
	}
}

---

4. 퀵정렬 사용하기

피벗(기준)을 삼아서 기준 보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 두고 재귀 수행하며 정렬(분할정복)

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

public class Main {

	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		quick_sort(arr,0,arr.length-1);  
		for(int val:arr) {
			System.out.println(val);
		}
	}

	public static void quick_sort(int[] a, int start, int end) {
		if(start>=end) return; // left가 right보다 크거나 같으면 정렬할 원소가 1개 이하, 정렬 x
		int pl = start;
		int pr = end;
		int pivot = a[(start+end)/2];
		
		while(pl<=pr) {
			while(a[pl]<pivot) {
				pl++;  // 피벗보다 큰 데이터를 찾을 때까지 반복
			}
			while(a[pr]>pivot) {
				pr--;  // 피벗보다 작은 데이터를 찾을 때까지 반복
			}
			if(pl<=pr) {  // 작은값이 오른쪽보다 더 커지지 않을 때만
				swap(a,pl,pr); // 서로의 값 교환
				pl++;
				pr--;
			}
		}
		if(start<pr)quick_sort(a,start,pr);
		if(end>pl) quick_sort(a,pl,end);
	}
	
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

 

• 처음에 정렬을 접했을 때는 이게 무슨 소리인가.. 이게 뭐냐.. 이런 느낌이었다면 한 번 봤더니 어떻게 로직이 구현되는 것인지 이해가 됐다. 
• StringBuilder를 써서 출력해도 되는데 맨 마지막에 항상 \n이 더 추가된다..!
• 속도는 Arrays.sort가 136, 선택정렬이 144, 삽입정렬이 148, 퀵정렬이 148이었다. 퀵정렬이 빠르다고 해서 기대를 했는데 삽입정렬과 같아서 놀랐다.. 알고보니 

퀵정렬은 대표적인 '분할 정복' 알고리즘으로 평균속도가 O(N*log N)이다. (하지만 항상 N*logN은 아니고 pivot값에 따라 최악 시간 복잡도는 O(N^2)가 될 수 있다.예)이미 정렬이 되어 있는 경우)

• Arrays.sort가 제일 빠를 줄은 몰랐다..
• swap 메서드는 이제.. 눈 감고도.. 할 수 있을 것 같다.. 이해했다구..!

---

2022.01.26 - [멀티캠퍼스 풀스택 과정/알고리즘] - 알고리즘1-6. 정렬(Sorting): 버블정렬, 선택정렬, 삽입정렬, 퀵정렬

알고리즘1-6. 정렬(Sorting): 버블정렬, 선택정렬, 삽입정렬, 퀵정렬

https://st-lab.tistory.com/250

자바 [JAVA] - 퀵 정렬 (Quick Sort)

https://12216715011126.tistory.com/39

[2750] 수 정렬하기 - 퀵정렬 (java)