PS/Sorting

정렬 개념 정리 (with JAVA)

닻과매 2022. 2. 18. 09:40

* 바킹독, 위키피디아 등을 참고하여 작성함.

 

목차

1. O(N^2) 시간복잡도 정렬 알고리즘 - 선택 정렬, 버블 정렬

2. O(NlogN) 시간복잡도 정렬 알고리즘 - 병합 정렬, 퀵소트

3. Non-comparison sorts: 카운팅 정렬, 기수 정렬

4. JAVA에서의 사용

 

※ 구분

stable sort: 크기가 같은 원소들끼리 정렬 후에도 원래의 유지하는 정렬 알고리즘(↔ unstable sort)

comparison sort: 우리가 일반적으로 아는, 원소의 값끼리 비교하여 정렬하는 알고리즘(↔ non-comparison sort)

 

 

1. O(N^2) 시간복잡도 정렬 알고리즘

  • 일반적으로 구현하기 쉽다.
  • 실제로 쓰이지 않으며, '선택 정렬과 버블 정렬의 차이점을 설명하여라'와 같은 지엽적인 질문을 받을 가능성도 매우 낮다. 따라서 한번 쓱 보고 넘어가면 된다.

 

1) 선택 정렬 (Selection Sort)

배열을 N번 순회하면서 각 순회마다 가장 작은/큰 원소를 찾아서 앞/뒤 index의 원소랑 swap을 반복하여 정렬하는 알고리즘.

선택정렬 시각화.

 

코드

더보기 
static void SelectionSort(int[] nums) {
    int N = nums.length;
    for (int i = N-1; i > 0; i--) {
        int maxIdx = 0;
        // 가장 큰 원소 찾기
        for (int j = 0; j < i; j++) {
            if (nums[maxIdx] < nums[j]) maxIdx = j;
        }

        // 바꾸기
        int temp = nums[maxIdx];
        nums[maxIdx] = nums[i];
        nums[i] = temp;
    }
}

 

2) 거품 정렬 (Bubble Sort)

  • 배열을 N-1번 순회하면서 각 순회마다 인접한 두 원소의 크기를 비교하여 정렬하는 알고리즘

버블정렬 시각화.

 

코드

더보기 
static void BubbleSort(int[] nums) {
    int N = nums.length;
    for (int i = 0; i < N-1; i++) { // N
        for (int j = 0; j < N-1; j++) {
            if (nums[j] > nums[j+1]) {
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
        }
    }
}

 

 

2. O(NlogN) 정렬 알고리즘

 

1) 병합 정렬(Merge Sort)

  • 재귀적으로 수열을 나눠 합쳐 정렬하는 정렬 알고리즘
  • 정렬되어있는 길이가 M인 리스트와 길이가 N인 리스트를 길이가 M+N인 정렬된 리스트로 합치는 데 걸리는 시간이 O(M+N)임을 이용한다. (참고 문제: 백준 11728 배열 합치기 https://www.acmicpc.net/problem/11728)
    • 부분수열을 어떻게 정렬을 시키나요? : 길이가 1인 수열은 정렬되어 있으니 수열을 잘게 쪼갠 후, 길이가 1인 수열에서부터 합치기!
  • Stable한 정렬 알고리즘이다.

 

 

 

Merge Sort의 작동 알고리즘

 

※ merge sort 구현 시 주의사항 (출처: https://www.acmicpc.net/board/view/31887)

병합 정렬을 할 때, merge를 수행할 때마다 배열의 전체 크기, 혹은 right만큼을 할당하고 해제하기를 반복하면 안 됩니다. 크기가 N인 메모리를 할당하는 것은 O(N) 시간이 걸리고, merge가 O(N)번 호출되기 때문에 총 시간복잡도가 O(N^2)이 됩니다. 이를 해결하기 위한 방법으로는,

1. 복사를 하기 위한 큰 배열 하나를 미리 할당해두고 계속 사용

2. merge가 담당하는 구간의 크기(right - left + 1)만큼만 메모리를 할당 등이 있습니다.

 

 

코드

더보기 
static void mergeSort(int start, int end) {
    if (end == start + 1) return;
    int mid = (start + end) / 2;
    mergeSort(start, mid);
    mergeSort(mid, end);
    merge(start, end);
}
	
// temp: 길이가 정렬할 배열 nums와 같은 길이의 int array
static void merge(int start, int end) {
    int mid = (start + end) / 2;
    int left = start;
    int right = mid;
    for (int i = start; i < end; i++) {
        if (left == mid) temp[i] = nums[right++];
        else if (right == end) temp[i] = nums[left++];
        else if (nums[left] <= nums[right]) temp[i] = nums[left++]; // stable하도록 등호도 포함
        else temp[i] = nums[right++];
    }
    for (int i = start; i < end; i++) nums[i] = temp[i];
}

 

2) 퀵소트(Quicksort)

  • 일반적으로 가장 빠른 알고리즘이라 많은 라이브러리의 정렬은 퀵소트를 기반으로 한다.
  • But, 퀵소트는 worst case O(N^2)이므로 절대 코딩테스트에서 퀵소트를 사용하면 안 된다! (참고 문제: 백준 2751 수 정렬하기 2 https://www.acmicpc.net/problem/2751)

 

코드

더보기 
static void quicksort(int start, int end) {
		if (end <= start + 1) return;
		
        int pivot = nums[start];
		int left = start+1;
		int right = end-1;
		
		// pivot이 올 위치를 기준으로 왼쪽은 pivot보다 작은 값, 오른쪽은 pivot보다 큰 값이 오도록 정렬
		while (true) {
			while (left <= right && nums[left] <= pivot) left++;
			while (left <= right && nums[right] >= pivot) right--;
			if (left > right) break;
			int temp = nums[left];
			nums[left] = nums[right];
			nums[right] = temp;
		}
        
		// pivot을 pivot이 있어야 할 위치로 보내기
		int temp = nums[start];
		nums[start] = nums[right];
		nums[right] = temp;
		
		// 재귀
		quicksort(start, right);
		quicksort(right+1, end);
	}

quicksort의 worst case

3. Non-comparison sorts

1) 카운팅 정렬(Counting Sort)

  • 주어진 물체가 나온 횟수를 센 후, 순서대로 물체를 나온 횟수만큼 출력하여 정렬하는 알고리즘.
  • 1~R 사이의 정수가 N번 나올 때, 이를 정렬하는 시간 복잡도는 N+R이며 공간 복잡도도 N+R이다.
  • N이 R과 가까울 때 쓰면 좋다. 다만 메모리를 많이 활용하기에 수의 범위 R이 천만 미만 정도일 때 사용을 고려한다.

 

코드 (백준 15688번: 수 정렬하기 5 https://www.acmicpc.net/problem/15688)

더보기 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws IOException{
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[2000001];
		// 숫자를 세줌: 이 문제에서는 숫자가 -1000000 ~ 1000000으로 오기에, 편의상 백만을 더해준다.
		for (int i = 0; i < N; i++) arr[Integer.parseInt(br.readLine())+1000000] += 1;
		
		// 각 숫자가 몇 번 나왔는지 읽은 후 출력
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i]; j++) {
				sb.append(i-1000000+"\n");
			}
		}
		System.out.println(sb.toString());
	}

}

 

2) 기수 정렬 (Radix Sort)

  • 자리수 별로 정렬하는 과정을 반복하여 정렬하는 알고리즘
  • 자리수(대체로 10)만큼의 queue를 두어, 1의 자리, 10의 자리, .... 마다 갖는 0~9 값을 대응하는 queue에 넣어줌
  • floating point값도 정렬이 가능하다.

 

예시)

주어진 list [170, 45, 75, 90, 2, 802, 24, 66] 를 radix sort로 정렬하는 방법

1의 자리로 정렬:

{170, 90}, {}, {802, 2}, {}, {24}, {45, 75}, {66}, {}, {}, {}

합치면:

[170, 90, 802, 2, 24, 45, 75, 66]

10의 자리로 정렬:

{802, 02}, {}, {24}, {}, {45}, {}, {66}, {170, 75}, {}, {90}

합치면:

[802, 2, 24, 45, 66, 170, 75, 90]

100의 자리로 정렬:

{002, 024, 045, 066, 075, 090}, {170}, {}, {}, {}, {}, {}, {}, {802}, {}

합치면:

[2, 24, 45, 66, 75, 90, 170, 802]

 

다만, List와 같은 동적 array를 사용할 수 있는 환경이라면 library에서 구현되어 있는 sort를 사용하면 되므로, 실제로 사용할 일은 별로 없으니 알고리즘 정도만 알아두면 된다.

 

코드

더보기 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;

public class RadixSort {
	static int[] nums = {170, 45, 75, 90, 2, 802, 2, 66};
	static int d = 3; // 최대 3자리 수: 가변적으로 할 수도 있음.
	static ArrayList<ArrayDeque<Integer>> list = new ArrayList<ArrayDeque<Integer>>();
	
	public static void main(String[] args) {
		for (int i = 0; i < 10; i++) {
			list.add(new ArrayDeque<Integer>());
		}
		radixSort(1);
		System.out.println(Arrays.toString(nums));
	}
	
	static void radixSort(int cnt) {
		if (cnt > d) return;

		// 올바른 queue에 넣어주기
		for (int num: nums) {
			list.get((num % (int) Math.pow(10, cnt)) / (int) Math.pow(10, cnt-1)).offer(num);
		}
		
		// queue에서 차례대로 빼주기
		int idx = 0;
		for (int i = 0; i < 10; i++) {
			int size = list.get(i).size();
			for (int j = 0; j < size; j++) {
				nums[idx++] = list.get(i).poll();
			}
		}
		
		// 다음 자리수: 재귀적으로 짰음, for문도 가능
		radixSort(cnt+1);
	}
}

 

정리

이름 Best Average Worst Memory Stable
Selection Sort N^2 N^2 N^2 1 Yes
Bubble Sort N* N^2 N^2 1 Yes
Merge Sort NlogN NlogN NlogN N Yes
Quicksort NlogN NlogN N^2 1 No
Counting sort - N + R N + R N + R Yes
Radix sort - ND ND - Yes

* Bubble sort 구현 과정에서 swap했는지를 체크하는 boolean 변수를 넣으면 Best case는 O(N)번 연산.

출처: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms 

 

 

4. JAVA에서의 사용

1) library내 sort 함수

  • Arrays.sort(list): array 'list'를 오름차순 정렬
  • Arrays.sort(list, comparator.reverseorder()): array 'list'를 내림차순 정렬
  • Arrays.sort(list, comparator): comparator(람다식으로 구현)에 따라 정렬
  • Collections.sort(list): ArrayList 등의 collections 'list'를 내림차순 정렬
  • Collections.sort(list, comparator): comparator(람다식으로 구현)에 따라 정렬

※ Java에서 Arrays.sort에 primitive type array를 전달하면 dual-pivot quicksort를 수행하기 때문에 최악의 경우 O(N^2)이 된다. 왠만하면 괜찮으나 저격 케이스가 있을 수도 있으므로 Collections.sort를 사용하자.

 

2) 정렬 기준이 없을 때, 기준 식 세우기

백준 11650: 좌표 정렬하기 문제를 예시로 한다.

 

I. Interface 'Comparable'를 implements하여 compareTo() method를 override, 기준을 정의

코드

더보기 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		List<Pair> coords = new ArrayList<Pair>();
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			coords.add(new Pair(a, b));
		}
		Collections.sort(coords);
		for (int i = 0; i < n; i++) {
			System.out.println(coords.get(i));
		}
	}	
}

class Pair implements Comparable<Pair>{
	private int x;
	private int y;
	
	public Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
    // compareTo Overriding하기
	@Override
	public int compareTo(Pair o) {
		if (o.x == x) {
			return Integer.compare(y, o.y);
		}
		return Integer.compare(x, o.x);
	}
	
	@Override
	public String toString() {
		return x+" "+y;
	}
}

 

II. sort에서 정렬 기준에 맞는 람다식 세워서 정렬하기

코드

더보기 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[][] coords = new int[n][2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			coords[i][0] = Integer.parseInt(st.nextToken());
			coords[i][1] = Integer.parseInt(st.nextToken());
		}
        
        // 람다식으로 정렬 기준 세우기
		Arrays.sort(coords, (e1, e2)->{
			if (e1[1] == e2[1]) {
				return Integer.compare(e1[0], e2[0]);
			}
			return Integer.compare(e1[1], e2[1]);
		});
		for (int i = 0; i < n; i++) {
			sb.append(coords[i][0]+ " " + coords[i][1]+"\n");
		}
		System.out.println(sb);
	}

}

 

연습 문제

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x0E.md

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x0F.md 

https://programmers.co.kr/learn/courses/30/parts/12198

'PS > Sorting' 카테고리의 다른 글

백준 16455번: K번째 수 찾는 함수 (Java)  (0) 2022.08.16
백준 5648번: 역원소 정렬 (JAVA)  (0) 2022.04.06
백준 18870번: 좌표 압축 (Python)  (0) 2021.10.21
백준 10814번: 나이순 정렬 (Python)  (0) 2021.10.20
10989번: 수 정렬하기  (0) 2021.10.20

'PS/Sorting'의 다른글

  • 현재글정렬 개념 정리 (with JAVA)

관련글

댓글

티스토리툴바