[알고리즘 개념] 정렬

정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 기준에 맞게 정렬하여 출력하는 알고리즘이다. 

다양한 알고리즘이 존재하고, 알고리즘 별 공간 복잡도와 시간 복잡도도 다르기 때문에 상황에 알맞은 알고리즘을 찾아 사용하는 것이 적절하다.

 

 

안전 정렬, 불안전 정렬

 

정렬은 같은 값(key)의 위치가 고정되느냐 고정되지 않느냐에 따라 안전 정렬과 불안전 정렬로 나뉜다.

같은 값인 a1, a2가 있을 때 정렬된 후에도 a1, a2 순서를 유지하면 안전 정렬,

순서가 변한다면 불안전 정렬이다.

 

 

내부 정렬, 외부 정렬

 

데이터의 크기가 주 기억장소 용량보다 큰지 작은지에 따라 나뉜다.

데이터의 크기가 주 기억장소 용량보다 적을 경우 내부 정렬로 기억장소를 활용하여 정렬한다.

클 경우에는 외부 정렬로 외부 기억장치를 사용하여 정렬한다.

 

 

 

1. 선택정렬

 

선택 정렬은 정렬이 된 부분과 정렬되지 않은 부분으로 나뉜다.

정렬 되지 않은 부분 중 가장 작은 값을 선택하여 정렬 부분의 가장 끝에 붙여준다 (오름차순 기준)

[기본 로직]
1. 정렬되지 않은 부분의 맨 앞에서부터, 맨 뒤까지 탐색하여 가장 작은 값을 찾는다.
2. 그 값을 현재 인덱스의 값과 바꿔준다 (초기 인덱스는 0으로 정렬되지 않은 부분의 맨 앞과 같은 위치이다)
3. 정렬되지 않은 부분은 1 줄어들고, 정렬된 부분은 1 증가한다.
4. 현재 인덱스 위치를 1 증가시키고, 위 과정을 반복한다.

- 시간 복잡도

비교 횟수는 n, n-1, n-2... , 1로 시간 복잡도는 O(n^2)이다.

 

- 공간 복잡도

공간 복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.

 

- 장점

선택 정렬은 교환 횟수보다 비교 횟수가 많은 알고리즘이다.

따라서, 많은 교환이 일어나야 하는 자료 상태에서 효율적으로 사용할 수 있다.

또한 구현이 쉽다.

 

- 단점

시간이 오래 걸리는 정렬 방식이다.

 

-특징

비교 횟수보다 교환 횟수가 적은 정렬 알고리즘이다.

많은 교환이 일어나야 하는 자료 상태에서 효율적으로 사용될 수 있다.

불안전 정렬이다.

 

 

2. 삽입 정렬

 

삽입 정렬 또한 정렬이 된 부분과 되지 않은 두 부분으로 나누어 진행된다.

정렬되지 않은 부분의 맨 앞의 값을 정렬된 부분에서의 알맞은 위치를 찾아 그 위치에 삽입하는 정렬 알고리즘이다.

 

[기본 로직]
1. 현재 인덱스의 값을 별도의 변수에 저장한다 (초기 인덱스는 1)
2. 삽입 변수와 정렬된 부분의 비교 인덱스 값과 비교한다. (비교 인덱스 = 현재 인덱스 -1)
3. 삽입 변수가 더 작으면 비교 인덱스를 -1 하며 비교를 반복한다.
4. 만약 삽입 변수가 더 크다면, 비교 인덱스 +1에 삽입 변수를 저장한다.

- 시간 복잡도

삽입 정렬은 초기 데이터의 정렬 상태에 따라 영향을 받는다.

최악의 경우는 역으로 정렬되어 있는 경우로 n-1, n-2... ,1 개씩 비교를 반복하여 시간 복잡도는 O(n^2)이다.

최선의 경우는 이미 정렬되어 있는 경우로 원소 당 한 번씩 비교하면 되므로, 시간 복잡도는 O(n)이다.

 

- 공간 복잡도

같은 배열에서 진행되므로 공간 복잡도는 O(n)이다.

 

- 장점

구현이 쉽고, 최선의 경우 효율성이 좋다.

 

- 단점

최악의 경우 시간이 오래 걸린다.

 

- 특징

데이터의 초기 정렬 상태에 영향을 받는 정렬 알고리즘이다.

안전 정렬이다.

 

 

3. 버블 정렬

 

버블 정렬 또한 정렬이 된 부분과 되지 않은 두 부분으로 나누어 진행된다.

버블 정렬은 매번 정렬되지 않은 부분의 연속된 두 개 인덱스를 비교하여 정렬한다.

 

[기본 로직]
1. 현재 인덱스 값과 이전의 인덱스 값을 비교한다 (초기 인덱스는 1)
2. 이전 인덱스가 더 크다면, 현재 인덱스와 값을 바꿔준다.
3. 이전 인덱스가 작다면, 교환하지 않고 현재 인덱스를 +1 해준다.
4. 위 과정을 현재 인덱스가 정렬되지 않은 부분의 마지막에 위치할 때까지 반복한다.
5. 다시 현재 인덱스를 초기 인덱스 +1 해가며 다시 반복한다. 

- 시간 복잡도

버블 정렬의 비교 횟수는 n-1, n-2... , 1 개씩 비교를 반복하게 되므로 시간 복잡도는 O(n^2)이다.

 

- 공간 복잡도

같은 배열에서 진행되므로 공간 복잡도는 O(n)이다.

 

- 장점

구현이 쉽고 코드 자체가 직관적이다.

 

- 단점

비효율적으로 긴 시간이 걸린다. 

 

- 특징

자료의 교환이 발생 여부를 나타내는 flag 변수로 다음 단계를 실행하지 않고 정렬을 종료하여 개선 가능하다.

안정 정렬이다.

 

 

4. 합병 정렬

 

합병 정렬은 분할 정복 방식을 이용한 알고리즘이다.

분할된 두 배열을 정렬하여 하나의 새로운 배열에 저장하는 과정(합병)을 반복한다.

 

[기본 로직]
1. 주어진 배열을 반으로 쪼갠다.
2. 쪼갠 배열의 크기가 0이나 1일 때까지 반복한다.
3. 두 배열의 크기를 비교해가며 새로운 배열에 저장한다.
4. 정렬된 배열을 원래 배열에 저장해주며, 위 과정을 반복한다.

- 시간 복잡도

합병 정렬은 각 합병 단계마다 배열의 크기만큼의 비교 횟수가 존재한다.

합병 단계는 lg(n) 개가 되므로 시간 복잡도는 O(n*lg(n))이다.

 

- 공간 복잡도

합병 정렬을 새로운 배열을 저장하기 위한 배열이 필요하므로 공간 복잡도는 O(2n)이다.

 

- 장점

데이터의 초기 정렬 상태와 관계없이 안정적인 복잡도를 가진다

 

- 특징

안전 정렬이며, 외부 데이터를 필요로 하는 외부 정렬이다.

가장 많이 쓰이는 알고리즘 중 하나이다.

 

 

5. 퀵 정렬

 

퀵 정렬도 분할 정복을 이용하는 정렬 알고리즘이다.

퀵 정렬은 pivot을 설정하여, 배열을 pivot보다 큰 값과 작은 값으로 분류한다.

위 과정을 배열을 분할하며 분할된 배열의 크기가 1이 될 때까지 반복한다.

 

[기본 로직]
1. pivot을 설정한다. pivot은 보통 맨 앞이나 맨뒤, 혹은 전체 배열의 중간값 또는 랜덤 값으로 설정한다.
2. 인덱스를 저장하는 left, right변수를 생성한다.
3. left와 right와 pivot값을 비교하여 left가 pivot 값보다 작다면 인덱스를 증가, right가 pivot값보다 크다면 인덱스를 감소한다.
4. left와 right 값을 바꿔준다.
5. left < right를 만족할 때까지 반복한다.
6. 5번을 만족하면 left와 pivot을 바꿔준다.

- 시간 복잡도

퀵 정렬은 병합 정렬과 마찬가지로, 매 분할 단계마다 배열의 크기에 해당하는 비교 횟수가 필요하다.

분할 단계는 lg(n)이므로, 시간 복잡도는 O(n*ln(n))이다.

 

- 공간 복잡도

한 배열 안에서 비교가 일어나므로 공간 복잡도는 O(n)이다.

 

- 장점

가장 빠르다고 알려진 알고리즘이다. 

 

- 단점

pivot을 어떻게 설정하느냐에 따라 시간 복잡도가 달라진다.

최악의 경우는 이미 정렬되어 있는 경우로 시간 복잡도는 O(n^2)이다.

 

 

정렬 알고리즘 시간 복잡도 비교