[알고리즘]정렬 알고리즘

김피자·2023년 1월 17일

목록 보기

1/4

공부하게된 계기

정렬에 대한 이해없이 알고리즘 문제를 풀다보니 제출 시 런타임 에러가 자주 발생했다.
그래서 이번 글에서 대표적인 정렬 알고리즘 5가지에 대해 정리하고자 한다.
~~나는 멍청이니깐 최대한 이해가 쉬운 그림들로 찾아서 정리했당~~

정렬 알고리즘의 종류

버블 정렬(Bubble Sort)

선택 정렬(Selection Sort)

삽입 정렬(Insert Sort)

병합 정렬(Merge Sort)

퀵 정렬(Quick Sort)

위 정렬 알고리즘들의 성능은 빅오표기법으로 표현된다.

Big O 표기법과 시간복잡도

알고리즘의 성능을 판단하는 지표에는 시간복잡도와 공간복잡도가 있다.
1. 시간복잡도(Time Complexity) : 알고리즘 수행시간
2. 공간복잡도(Space Complexity) : 알고리즘 메모리 사용량

문제를 풀다보면 "이 알고리즘의 시간복잡도는 0 n 이다" 혹은 "0의 n제곱입니다" 이라 나와있거나 "O(n)"으로 작성되어 있는데 이것이 바로 빅오(Big O) 표기법이다.

O(n)의 의미는 아래와 같다.

이 함수는 n만큼의 데이터가 주어졌을 때, "최악"의 경우 n만큼의 리소스를 소모한다.

위에서 말한 리소스가 시간복잡도라면 시간, 공간복잡도라면 메모리 공간을 뜻한다.
~~하지만, 정렬알고리즘을 평가할 때는 주로 시간복잡도에 집중한다.~~

시간복잡도에 대해 쉽게 이해하기 위해 이진탐색 알고리즘의 시간복잡도를 살펴보자.

이미 정렬된 데이터의 특징은 어떤 값을 임의로 골랐을 때 해당 값을 고른 위치의 오른쪽에는 무조건 크거나 같은 값이 있고, 왼쪽은 무조건 작거나 같은 값이 있다는 것이다.

예를 들어, 컴퓨터가 어떤 값을 딱 골랐을 때(25) 찾고자 하는 값(10)이 고른 값보다 작다면 그 값(25)의 오른쪽(26, 27..)은 볼 필요도 없다는 뜻이다.

컴퓨터가 어떤 값을 고르는 위치가 후보군의 가운데인 탐색 알고리즘이 바로 이진탐색이다.

이진탐색을 잘 모르는 사람은 업다운 술게임 게임을 생각하면 된다.
1~100 사이에서 상대가 생각한 임의의 숫자를 맞추기위해 50이라는 중간값을 부르고 상대가 업 또는 다운을 하면 우리는 반대의 50개의 수는 버리고 나머지 50개 중에서 선택하면 된다.
이 게임에서 최악의 경우는 계속 업과 다운을 반복하다 O(logN)에 끝나는 것이고, 최선의 경우는 찾고자 하는 값을 처음부터 맞춰버린 상황 이때의 시간복잡도는 O(1)이 된다.

왜 정렬이 필요할까?

: 데이터를 정렬해야 하는 이유는 탐색을 위해서다.
사람은 수십에서 수백 개의 데이터를 다루지만 컴퓨터는 보통 백만개 이상이며, 데이터베이스의 경우 이론상 무한 개의 데이터를 다룰 수 있어야 한다. 탐색할 대상 데이터가 정렬이 되어있지 않다면, 순차 탐색 이외의 다른 알고리즘은 사용할 수 없지만, 데이터가 정렬되어 있다면 이진탐색이라는 강력한 알고리즘을 사용할 수 있다.

1. 버블정렬 (Bubble Sort)

버블정렬은 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.
거의 모든 상황에서 최악의 성능을 보이지만, 이미 정렬된 자료에서는 1번만 순회하면 되기 때문에 최선의 성능을 보여주는 알고리즘이다.
~~이미 정렬한 알고리즘을 다시 정렬하는 이유는 정렬알고리즘 자체는 데이터가 정렬되어 있는지 아닌지 모르고 작동하기 때문이다~~

버블정렬은 다음과 같이 작동한다.

1) 0번째 요소와 1번째 요소를 비교 후 정렬
2) 1번째 요소와 2번째 요소를 비교 후 정렬
....
n) n-1번째 요소와 n번째 요소를 비교 후 정렬

버블정렬 자바코드

public class bubble_sort {

	public static void main(String[] args) {
		int [] arr = {5,3,2,7,1};
		
		System.out.print("정렬 전 : ");
		for(int x : arr) {
			System.out.print(x+" ");
		}
		System.out.println();
		bubbleSort(arr);
		
		System.out.print("정렬 후 : ");
		for(int x : arr) {
			System.out.print(x+" ");
		}
	}

	private static void bubbleSort(int[] arr) {
		for(int i = 0; i < arr.length-1; i++) {
			// -i를 하는 이유 > 맨 마지막은 비교 안해도 됨
			for(int j = 0; j < arr.length-1-i; j++) { // 앞 숫자와 뒤 숫자 서로 비교할 반복문
				// j = 0일 때, arr[0] > arr[0+1]로 앞자리가 숫자가 더 크다면
				if(arr[j] > arr[j+1]) {
					int tmp = arr[j]; 
					arr[j] = arr[j+1]; 
					arr[j+1] = tmp; 
				}
			}
			System.out.print(i+1+"번째 과정 : ");
			for(int x : arr)
				System.out.print(x+" ");
			System.out.println();
		}
	}
}

O(n^2)

버블정렬의 시간 복잡도를 계산하면 best, worst, average case 모두
O(n^2)의 시간복잡도를 갖는다.
이미 정렬이 되어 있던 안되어 있던 n개의 input이 있을 때 n개에 대해 각각 n번 즉, for문을 2번 돌기 때문에(실제 교환이 안일어나도 비교는 계속함) 최상, 최악, 평균의 경우 모두 O(n^2)의 시간복잡도를 갖게된다.

2. 선택정렬 (Selection Sort)

선택정렬은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

1) 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
2) 두 번째 순서에는 두 번째 위치에 남은 값 중 최솟값을 넣는다
...
n) n-1 번째 순서에는 n-1 번째 위치에 남은 값 중 최솟값을 넣는다.

과정 설명

1) 주어진 배열 중 최솟값을 찾는다.
2) 그 값을 1번 위치한 값과 교체한다 (패스)
3) 1번 위치를뺀 나머지 리스트를 같은 방법으로 교체한다.

첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 최솟값을 찾아 첫 번째 위치에 두고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 두는 과정을 반복하며 정렬을 수행한다.

선택정렬 자바코드

public class Selection_sort {

	public static void main(String[] args) {
		int [] arr = {2,4,6,1,3,9,5};
		System.out.print("정렬 전 : ");
		for(int x : arr) {
			System.out.print(x+" ");
		}
		System.out.println();
		SelectionSort(arr);
		System.out.print("정렬 후 : ");
		for(int x : arr) {
			System.out.print(x+" ");
		}
	}

	private static void SelectionSort(int[] arr) {
		for(int i = 0; i<arr.length-1;i++) {
			// 최솟값 인덱스 찾아서 저장
			int min_index = i;
			for(int j = i+1; j< arr.length; j++) {
				if(arr[j]<arr[min_index]) {
					min_index = j;
				}
			}
			int temp = arr[min_index];
			arr[min_index] = arr[i];
			arr[i] = temp;
			
			System.out.print(i+1+"번째 과정 : ");
			for(int x : arr)
				System.out.print(x+" ");
			System.out.println();
		}
	}
}

O(n^2)

선택정렬의 경우, 현재 자료가 정렬이 되어있던말던 무조건 전체 리스트를 순회해가며 검사하기 때문에 버블정렬과 같이 Best,Avg, Worst 모두 O(n^2)의 시간복잡도를 가지고있다.

3. 삽입정렬 (Insertion Sort)

삽입정렬은 주어진 자료의 모든 요소를 앞에서부터 차례대로 정렬된 자료 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬이다.
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입합으로써 정렬을 완성하는 알고리즘이다.
~~매 순서마다 해당 원소를 삽일할 수 있는 위치를 찾아 해당 위치에 넣는다~~

예를들어 손안의 카드를 정렬한다고 생각해보자

1) 카드를 하나 고른다
2) 내가 가지고 있는 카드를 쭉 살펴본다
3) 카드가 들어가야할 순서에 카드를 껴 넣는다

작동원리

1) 0번 인덱스는 건너뛴다
2) 0~1번 인덱스 중 1번 인덱스 값이 들어가야할 위치를 찾아 넣는다
3) 0~2번 인덱스 중 2번 인덱스 값이 들어가야할 위치를 찾아 넣는다
...
n) 0~n번 인덱스 중 n번 인덱스 값이 들어가야할 위치를 찾아 넣는다

삽입정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽) 의 자료들과 비교해 삽입 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

삽입정렬은 Best의 경우 전체 자료를 한번만 순회하면 되기때문에 O(n)의 시간복잡도를 가지지만 Worst의 경우 O(n^2)의 시간복잡도를 가진다

삽입정렬 자바코드

ublic class Insertion_sort {

	public static void main(String[] args) {
		int [] arr = {3,2,4,1,6,5};
		System.out.print("정렬 전 : ");
		for(int x : arr) {
			System.out.print(x+" ");
		}
		System.out.println();
		insertion(arr);
		System.out.print("정렬 후 : ");
		for(int x : arr) {
			System.out.print(x+" ");
		}

	}

	private static void insertion(int[] arr) {
		for(int i=1; i<arr.length; i++) {
			// 정렬할 대상  
			int change = arr[i];
			
			// 이전 원소 
			int j = i - 1;
			
			// 정렬할 대상이 이전 원소보다 크기 전 까지 반복
			while(j>=0 && change < arr[j]) {
				arr[j+1] = arr[j];
				j--;
			}
			// 위 while문을 탈출하는 경우는 이전 원소가 정렬할 대상 원소보다 적다는 의미로
			// 정렬할 대상 원소는 이전 원소의 뒤에 와야한다.
			// 그러므로 정렬할 대상은 j+1에 위치하게 된다ㅏ
		
			arr[j+1] = change;
			System.out.print(i+"번째 정렬 : ");
			for(int x : arr) {
				System.out.print(x+" ");
			}
			System.out.println();
		}
	}
}

1번째 정렬

arr[0]의 3과 arr[1]의 2를 비교하여 2와 3의 자리를 바꿈

2번째 정렬

arr[1]의 3과 arr[2]의 4를 비교하여 자리를 바꾸지 않음arr[0]의 2와 arr[2]의 4를 비교하여 자리를 바꾸지 않음

3번째 정렬

arr[2]의 4와 arr[3]의 1을 비교하여 4와 1의 자리를 바꿈

2 3 1 4 6 5

arr[1]의 3과 arr[2]의 1을 비교하여 3과 1의 자리를 바꿈

2 1 3 4 6 5

arr[0]의 2와 arr[1]의 1을 비교하여 2와 1의 자리를 바꿈

1 2 3 4 6 5

...이런 느낌

O(n^2)

삽입정렬의 경우 최선의 경우 전체 자료를 한번만 순회하면 되기때문에 O(n)의 시간복잡도를 가지지만, 최악의 경우 O(n^2)의 시간복잡도를 가진다.

4. 병합정렬 (Merge Sort)

분할 정복법 중 하나로 큰 문제를 작은 여러 개의 문제로 쪼개서 각각 해결한 후 결과를 모아 원래의 문제를 해결하는 방법이다.
병합이라는 이름처럼 주어진 자료를 잘게 쪼갠 뒤 합치는 과정에서 정렬을 하는 알고리즘

예를들어 [6, 1, 5, 2]라는 자료를 받았다면

이 배열의 length가 1이 될때까지 리스트를 반으로 쪼갠다.
그럼 [6, 1] 과 [5, 2]로 쪼개지고
다시 [6], [1], [5], [2]가 된다.

각 리스트의 길이가 1이 되었으니 병합을 시작한다.

왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합한다.

[6]과 [1] 중 1이 더 작으므로 새로운 리스트에 1을 먼저 병합한다.
[1, 6] 생성

왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합한다.
[5]와 [2] 중 2가 더 작으므로 새로운 리스트에 2를 먼저 병합한다
[2, 5] 생성

이제 [1, 6]과 [2, 5]를 병합한다.
이 리스트들은 이미 정렬이 되어있기 때문에 작은 인덱스일 수록 작은 값을 가진다는 것이 보장되어 있다.

왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[1] 생성 [6]과 [2, 5]가 남았다.

왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[1, 2] 생성 [6]과 [5]가 남았다.

왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[1, 2, 5] 생성 [6]이 남았다.
남은 값이 1개이므로 그냥 병합해준다.

[1, 2, 5, 6] 정렬완료

위 글을보면 "왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합한다" 라는 과정이 반복되는 것을 알 수 있다.

병합정렬 자바코드

public class merge_sort {
	public static int [] arr;
	public static int [] temp;
	public static void main(String[] args) {
		arr = new int [] {2,1,8,0,7,5};
		temp = new int [arr.length];
		System.out.print("정렬 전 : ");
		printArray(arr);
		mergeSort(0, arr.length-1);
		System.out.println();
		System.out.print("정렬 후 : ");
		printArray(arr);
	}
	
	private static void mergeSort(int start, int end) {
		if(start<end) {
			int mid = (start+end)/2;
			//재귀 시작
			mergeSort(start, mid);
			mergeSort(mid+1, end);
			
			int p = start;
			int q = mid+1;
			int idx = p;
			
			while(p <= mid || q <= end) {
				if(q > end || (p <= mid && arr[p] < arr[q])) {
					temp[idx++] = arr[p++];
				}else {
					temp[idx++] = arr[q++];
				}
			}
			for(int i = start; i<= end; i++) {
				arr[i] = temp[i];                           
			}
		}
	}
	// 현재 배열의 상태 출
	private static void printArray(int[] arr) {
		for(int x : arr) {
			System.out.print(x+" ");
		}
		System.out.println();
	}
}

O(n log n)

같은 방식으로 계속 반복하여 병합하기 때문에 병합정렬은 보통 재귀함수로 구현한다.
또 병합정렬은 항상 O(n log n)의 시간복잡도를 가지기 때문에 효율적이다
그러나, 원소의 개수만큼 리스트를 쪼개고 따로 저장하고 있어야하기 때문에 O(n)의 공간 복잡도를 가지기도 한다.
한마디로 메모리를 차지해 수행속도를 얻는다고 생각하면 된다.

5. 퀵정렬 (Quick Sort)

퀵 정렬도 병합 정렬처럼 분할을 통한 정렬 방법이다.
두개의 차이라면 병합 정렬은 분할 단계에서는 아무것도 하지않고 분할만 하고 병합하는 과정에서 정렬을 수행한다면, 퀵 정렬은 분할 단계에서 중요한 작업들을 수행하고 병합시에 아무것도 하지않는다는 점이다.

정렬 과정

1) 피벗을 하나 선택한다.

2) 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.

3) 양 방향에서 찾은 두 원소를 교환한다.

4) 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때 까지 2번으로 돌아가 위 과정을 반복한다.

5) 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다. (Divide : 분할)

6) 인접한 부분리스트끼리 합친다. (Conqure : 정복)

뭔 개소리인가 싶어 2, 3번에 대해 더 설명하면
대부분 구현은 현재 리스트의 양 끝에서 시작하여 왼쪽에서는 피벗보다 큰 값을 찾고 오른쪽에서는 피벗보다 작은 값을 찾아 두 원소를 교환하는 방식이다.
그래야 피벗보다 작은 값은 왼쪽 부분에, 피벗보다 큰 값은 오른쪽 부분에 치우치게 할 수 있기 때문이다

그러면~ 피벗을 뭐 내가 아무렇게나 임의로 선택하냐? 그건 또 아니다.
대표적으로 피벗을 선택하는 방법에는 세 가지가 있다.

현재 부분 배열의 가장 왼쪽 요소가 피벗이 되는 방법

중간 원소가 피벗이 되는 방법

마지막 원소가 피벗이 되는 방법

3가지 방법의 특징은 '피벗'을 하나 설정하고 피벗보다 작은 값은 왼쪽에, 피벗보다 큰 값은 오른쪽에 위치하도록 하는 것이다.
~~이 과정을 파티셔닝(Partitioning)이라 한다.~~

이렇게 파티셔닝을 했다면 파티셔닝을 통해 배치 된 피벗의 위치를 기준으로 좌우 부분 리스트로 나눠 각각 리스트에 대해 재귀호출을 하면 된다.

여기까지 봤는데도 나처럼 이해가 안될 수도 있으니깐 다시 더 자세히 설명

[초기 배열]
6 9 20 3 5 10 7 11 15 1

배열의 가장 왼쪽 값을 피벗으로 설정했다
6 9 20 3 5 10 7 11 15 1
피벗을 기준으로 나머지 값에 대해 왼쪽부터는 피벗보다 큰 값을 오른쪽 부터는 피벗보다 작은 값을 찾는다
6 (9) 20 3 5 10 7 11 15 (1) // 피벗보다 큰 값 9, 피벗보다 작은 값 1

6 (1) 20 3 5 10 7 11 15 (9) // 둘의 위치 바꾸기

6 1 (20) 3 (5) 10 7 11 15 9 // 피벗보다 큰 값 20, 피벗보다 작은 값 5

6 1 (5) 3 (20) 10 7 11 15 9 // 둘의 위치 바꾸기
큰 값의 인덱스가 작은 값의 인덱스보다 더 높아지면 둘 중 작은 값을 피벗과 교환한다.
~~이때 피벗은 정렬 위치가 [확정]~~
6 1 5 (3) 20 10 7 11 15 9 > 3 1 5 [6] 20 10 7 11 15 9
6의 왼쪽 집합과 오른쪽 집합에서 각각 첫 번째 요소를 피벗으로 지정하고 두 집합의 퀵 정렬을 동시에 수행

3 1 5 [6] 20 10 7 11 15 9

3 (1) 5 [6] 20 10 7 11 15 9

(1) 3 5 [6] 20 10 7 11 15 9

[1 3 5 6] 20 10 7 11 15 9

[1 3 5 6] 20 10 7 11 15 (9)

[1 3 5 6] (9) 10 7 11 15 [20]

[1 3 5 6] 9 10 7 11 15 [20]

[1 3 5 6] 9 (10) (7) 11 15 [20]

[1 3 5 6] 9 (7) (10) 11 15 [20]

[1 3 5 6 7 9] 10 (11) (15) [20]

[1 3 5 6 7 9 10] 11 15 [20]

[1 3 5 6 7 9 10 11 15 20]

퀵정렬 자바코드


public class quick_sort {
    private static int arr[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    private static int number = arr.length;

    public static void main(String[] args) {
        quickSort(arr, 0, number-1);
        show();
    }
    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = start;
        int i = start + 1;
        int j = end;
        int temp;

        while (i <= j) { // 엇갈릴 때 까지 반복 j가 i보다 크거나 같으면 while문 종료
            while (i <= end && arr[i] < arr[pivot]) { // 피벗 값보다 큰 값을 만날 때 까지
                i++;
            }
            while (j > start && arr[j] >= arr[pivot]) { // 피벗 값보다 작은 값을 만날 때 까지
                j--;
            }
            if (i > j) { // 현재 엇갈린 상태라면
                temp = arr[j];
                arr[j] = arr[pivot];
                arr[pivot] = temp;
            } else {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        quickSort(arr, start, j-1);
        quickSort(arr, j+1, end);
    }
    public static void show() {
    	System.out.print("결과 : ");
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

평균 시간 복잡도 : O(nLog₂n)
최악 시간 복잡도 : O(N^2)

복잡해 보이지만 다른 정렬 알고리즘과 비교했을 때 가장 빠르다.
(하지만 코드짜는데 갈려나가는 시간이 다른 정렬에 비해 엄청난데요ㅠㅠㅠ)

퀵 정렬은 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐 아니라, 한번 결정된 피벗들이 추후 연산에서 제외되는 특성이 있어서 좋다고한다.

총평

단순(구현 간단)하지만 비효율적인 방법

> 버블정렬, 삽입정렬, 선택정렬

복잡(구현 개어려움)하지만 효율적인 방법

> 병합정렬, 퀵정렬

결론

정렬 5개 정리하는데 뻥안치고 나의 5시간이 갈렸다
특히 병합, 퀵정렬들 진짜 꿀밤한대씩 때려주고 싶다ㅡ_ㅡ
어 음...저는 그냥 엑셀로 정렬해서 주시면 안될까요?

참고
https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://evan-moon.github.io/2018/10/13/sort-algorithm/
https://velog.io/@dms873/Java-%EB%B2%84%EB%B8%94-%EC%A0%95%EB%A0%ACBubble-sort
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
https://itprogramming119.tistory.com/entry/23-%ED%80%B5-%EC%A0%95%EB%A0%AC

김피자

제로부터시작하는코딩생활

다음 포스트

[알고리즘]정렬 알고리즘

알고리즘

공부하게된 계기

정렬 알고리즘의 종류

Big O 표기법과 시간복잡도

왜 정렬이 필요할까?

1. 버블정렬 (Bubble Sort)

버블정렬 자바코드

2. 선택정렬 (Selection Sort)

선택정렬 자바코드

3. 삽입정렬 (Insertion Sort)

삽입정렬 자바코드

4. 병합정렬 (Merge Sort)

병합정렬 자바코드

5. 퀵정렬 (Quick Sort)

퀵정렬 자바코드

총평

결론

[알고리즘]재귀함수

0개의 댓글