[Algorithm] 정렬 알고리즘 완.전.정.복 1편 (버블, 선택, 삽입)

정렬 알고리즘이란?

-> 데이터를 정해진 기준에 따라 의미있는 구조로 재설정하는 것을 말한다. 즉, n개의 입력이 주어지면 내가 원하는 기준에 따라 데이터를 정렬하는 방식이다. 

ex) 1 ~ 10의 숫자가 무작위로 배치되어있다면, 이를 오름차순으로, 혹은 내림차순으로 설정하여 데이터를 순서대로 설정하는 것을 말한다.

 

정렬 알고리즘에는 대표적인 6가지의 알고리즘이 존재한다.

이를 총 2편에 나눠서 배울 것이며, 시간이 가장 느릴 방식부터, 가장 빠른 방식까지 알아보도록 하겠다. 

버블 정렬	주어진 데이터의 인접 요소끼리 비교하고, 기준에 따라 swap하는 형식. O(N^2)
선택 정렬	전체 데이터를 비교한 뒤, 기준에 맞는 데이터를 앞으로 보내는 것을 반복하는 형식. O(N^2)
삽입 정렬	대상을 선택하고, 정렬된 영역에서 적절한 위치에 배치하는 것을 반복하는 형식. O(N^2) / O(N)

 

들어가기 전!

정렬에서는 Best, Average, Worst 3가지를 구분해서 시간복잡도를 계산한다.

Best는 이미 정렬된 데이터일 경우, Worst는 가장 시간이 오래 걸리는 형태로 배치된 데이터일 경우를 의미한다.

아마 삽입 정렬에서 좀 더 자세히 다룰 예정이다!

 

(모든 예제는 {3 4 2 1 5} 형태의 배열을 오름차순으로 정렬하는 것을 기준으로 한다.)

---

1. 버블 정렬 (Bubble Sort)

두 인접한 데이터를 비교하고, swap하며 정렬해나가는 방식을 의미한다. 

데이터 비교를 반복하다보면, 가장 마지막 배열의 요소가 정렬되게 된다. 이 과정을 반복한다.

구현을 매우 간단하게 할 수 있지만, 시간복잡도가 O(N^2)이므로, 다른 정렬알고리즘보다 속도가 느린 편이다.

Best, Average, Worst 모두 동일한 시간복잡도를 가진다.

 

동작 방식

3 4 2 1 5 -> 3과 4를 비교했을 때, 이미 정렬되어 있기에 swap 없음.

3 2 4 1 5 -> 4와 2를 비교했을 때, 4가 더 크기에 swap.

3 2 1 4 5 -> 4와 1을 비교했을 때, 4가 더 크기에 swap.

3 2 1 4 5 -> 4와 5를 비교했을 때, 이미 정렬되어 있기에 swap 없음.

-> 가장 큰 요소 5가 배열의 제일 마지막에 정렬된다. 이미 정렬된 배열을 제외한 채로 위 과정을 반복한다.

---

2. 선택 정렬 (Selection Sort)

데이터 전체를 확인하고, 최소나 최대 데이터를 졍렬되지 않은 배열의 가장 앞 요소에 배치시켜 정렬해나가는 방식을 의미한다. 정렬된 요소들을 제외한 채, 다시 나머지 데이터를 확인하고 배치시키는 것을 반복한다.

이는 (1) 최솟값 혹은 최댓값을 찾고, 이를 (2) 정렬되지 않은 배열의 첫 데이터와 swap하는 것이 핵심이다.

시간복잡도가 O(N^2)이며, Best, Average, Worst 모두 동일한 시간복잡도를 가진다.

 

동작 방식

3 4 2 1 5 -> 데이터 전체를 확인. 1이 가장 작은 데이터임.

1 4 2 3 5 -> 1과 3을 swap. 

1 4 2 3 5 -> 1을 제외한 정렬되지 않은 데이터 전체를 확인. 2가 가장 작은 데이터임.

1 2 4 3 5 -> 2와 4를 swap. 

-> 이처럼 첫 요소부터 정렬된다. 이 과정을 반복한다.

---

3. 삽입 정렬 (Insertion Sort)

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를, 정렬 기준에 의거한 적절한 위치에 삽입시켜 정렬해나가는 방식을 의미한다. 삽입시킨 현재 위치에서, 다음 위치의 데이터의 적절한 위치를 확인하는 과정을 반복한다.

이는 선택 데이터를 적절한 위치에 삽입하는 것이 가장 핵심이다. (이동시키는 요소는 두 번째부터)

시간복잡도는 Average와 Worst일 때는 O(N^2)이지만, Best(이미 정렬되어있는 경우)일 떄는 O(N)을 가진다.

 

동작 방식

3 4 2 1 5 -> 두 번째 요소부터 시작. 4의 적절한 위치를 확인. (첫 요소는 정렬된 데이터 범위)

3 4 2 1 5 -> 4의 위치는 현재가 적절함. 다음 2의 적절한 위치를 확인.
(현재 위치 4에서 정렬된 데이터를 비교할 때, 현재 위치의 앞 요소부터 비교 시작함.)

2 3 4 1 5 -> 2의 위치를 앞으로 이동시켜 배치함. 다음 1의 적절한 위치 확인. (2를 배치할 때, 3 4를 뒤로 이동시킴)

-> 이 과정을 배열의 끝까지 반복한다. 

 

ex) 1 2 3 4 5로 가정하자. 2부터 이동시킬 경우, 자신의 앞 요소만 비교하더라도 2의 위치는 제자리임을 알 수 있다. 다른 원소들도 마찬가지이기에 한번씩만 비교하므로, 시간복잡도가 O(N)이 된다.

 

예시 문제

11399번: ATM

위 알고리즘을 익힌 뒤, 풀기 적절한 문제라고 생각한다.

 

1. 먼저 주어진 시간을 보고, 문제의 조건을 계산해본다.

N의 최댓값이 1000이고, 시간 제한이 1초이기에 O(N^2)까지의 정렬알고리즘 어떤 것도 사용해도 문제를 해결할 수 있다.

 

2. 주어진 배열을 정렬한다.

문제를 읽어보면, 배열이 정렬되었을 때 ATM에서 인출하는 시간이 총 시간이 최소가 되기 때문에, 각 사람들의 인출시간을 오름차순으로 정렬해야한다. 위 3가지 알고리즘 중 하나를 택해 정렬한다.

 

3. 문제에서 원하는 값을 출력한다.

정렬한 뒤, 문제에서는 사람들이 기다렸던 인출시간의 합을 구해야하기에,

앞사람 모두의 인출시간 합 + 자신의 인출시간을 계산하고, 이 총합을 출력한다.

 

아래 코드는 필자가 조금 마음대로(?) 풀어낸 정답이다. 

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;
	vector<int> vec(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> vec[i];
	}

	int min = 1001;
	int point = 0;
	int sum = 0;

	for (int i = 0; i < N; i++) {
		min = 1001; // 선택 정렬 사용
		for (int j = i; j < N; j++) {
			if (min > vec[j]) {
				min = vec[j];
				point = j;
			}
		}
        
		int temp = vec[point];
		vec[point] = vec[i];
		vec[i] = temp;
        // temp를 이용한 swap 과정
	}

	for (int i = N - 1; i >= 0; i--) {
		for (int j = i; j >= 0; j--) {
			sum += vec[j]; // 합 계산
		}
	}

	cout << sum;


	return 0;
}

 

코드 리뷰는 언제나 환영입니다!