[알고리즘] 선택 정렬과 빅 오(Big O)

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다.

---

선택 정렬

선택 정렬은 아래와 같은 단계를 따른다.

 

1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정한다.
한 셀씩 이동하면서 현재까지 가장 작은 값을 기록한다.(실제로는 그 인덱스를 변수에 저장)
변수에 들어 있는 값보다 작은 값이 들어 있는 셀을 만나면 변수가 새 인덱스를 가리키도록 값을 대체한다.

 

2. 최솟값이 어느 인덱스에 있는지 알았으므로 그 인덱스의 값과 패스스루를 처음 시작했을 때의 값을 교환한다.
패스스루를 시작했을 때 인덱스는 첫 패스스루에서는 인덱스 0일 것이고, 두 번째 패스스루에서는 인덱스 1일 것이다.

 

3. 매 패스스루는 1, 2 단계로 이뤄진다.
배열 끝에서 시작하는 패스스루에 도달할 때까지 패스스루를 반복한다.
마지막 패스스루에서는 배열이 완벽히 정렬되어 있을 것이다.

 

더 자세히 선택 정렬 살펴보기

 

배열 [4, 2, 7, 1, 3]을 선택 정렬로 정렬해보자.

 

첫 번째 패스스루 시작

인덱스 0에 들어 있는 값을 확인하며 시작한다.

이 값이 지금까지 본 유일한 값이므로 이 인덱스를 변수에 저장한다.

 

1단계 : 현재 최솟값과 2를 비교한다.

 

2는 4보다 작으므로 2가 현재까지의 최솟값이 된다.

 

2단계 : 현재 최솟값과 다음 값인 7을 비교한다. 7은 2보다 크므로 2가 여전히 최솟값이다.

 

3단계 : 현재 최솟값과 1을 비교한다.

1은 2보다 작으므로 1이 새로운 최솟값이 된다.

 

4단계 : 현재 최솟값인 1과 3을 비교한다. 배열의 끝에 도달했으므로 전체 배열의 최솟값이 1로 결정되었다.

 

5단계 : 1이 최솟값이므로 1과 인덱스 0(패스스루를 시작했던 인덱스)의 값을 교환한다.

최솟값을 배열 맨 앞으로 옮겼으니 이제 최솟값이 배열 내에 올바른 위치에 있게 되었다.

 

두 번째 패스스루 시작

첫 번째 셀, 즉 인덱스 0은 이미 정렬됐으므로 두 번째 패스스루는 다음 셀인 인덱스 1부터 시작한다.

인덱스 1의 값은 2이며, 이 값이 두 번째 패스수루의 현재 최솟값이다.

 

6단계 : 현재 최솟값과 7을 비교한다. 2는 7보다 작으므로 2는 여전히 최솟값이다.

 

7단계 : 현재 최솟값과 4를 비교한다. 2는 4보다 작으므로 2는 여전히 최솟값이다.

 

8단계 : 현재 최솟값과 4를 비교한다. 2는 4보다 작으므로 2는 여전히 최솟값이다.

배열의 끝에 도달했다.

이 패스스루의 최솟값이 이미 올바른 위치에 있으니 교환하지 않아도 된다.

이로써 아래와 같은 생태로 두 번째 패스스루가 끝났다.

 

세 번째 패스스루 시작

7이 들어 있는 인덱스 2에서 시작한다.

7은 세 번째 패스스루에서 현재까지의 최솟값이다.

 

9단계 : 4와 7을 비교한다.

4가 새로운 최솟값이다.

 

10단계 : 4보다 작은 3이 나타났다.

이제 3이 새로운 최솟값이다.

 

11단계 : 배열의 끝에 도달했으므로 3과 패스스루를 시작했던 값, 즉 7을 교환한다.

이제 3이 배열 내에 올바른 위치에 있게 되었다.

 

이 시점에서는 우리는 정렬이 모두 되었음을 알지만, 컴퓨터는 아직 모르므로 네 번째 패스스루를 시작해야 한다.

 

네 번째 패스스루 시작

인덱스 3에서 패스스루를 시작한다.

4가 현재까지의 최솟값이다.

 

12단계 : 4와 7을 비교한다.

4가 여전히 이 패스스루의 최솟값이고 올바른 위치에 있으니 교환하지 않아도 된다.

마지막 셀을 제외한 모든 셀이 올바르게 정렬 됐고, 마지막 셀 역시 당연히 올바른 순서이므로 이제 전체 배열이 올바르게 정렬됐다.

 

 

선택 정렬의 효율성

선택 정렬은 비교와 교환, 두 종료의 단계를 포함한다.

5개의 원소를 포함하는 배열 예제로 돌아가면, 총 10번의 비교를 해야 했다.

 

총 4 + 3 + 2 + 1 = 10번의 비교다.

즉, 원소 N개가 있을 때 (N - 1) + (N - 2) + (N - 3) + ... + 1번의 비교다.

 

교환은 한 패스스루 당 최대 한 번이 일어난다.

배열이 역순으로 정렬된 최악의 시나리오에서는 버블 정렬과 달리 비교할 때마다 빠짐없이 교환을 한 번 해야 한다.

 

표로 보는 것과 같이 선택 정렬은 버블 정렬 보다 대략 절반 정도의 단계 수를 가지고 있다.

즉, 선택 정렬이 두 배 정도 더 빠르다.

 

 

선택 정렬과 빅 오

선택 정렬은 약 절반정도 버블 정렬보다 적은 단계수를 가지고 있지만 둘 다 모두 O(N²)로 빅 오를 표현 한다.

선택 정렬이 버블 정렬 보다 절반정도 단계수가 적으니, O(N² / 2)로 표현하는 게 올바르게 표현한 것이라고 생각할지 모르지만, 빅 오 표기법은 상수를 무시한다.

즉, 빅 오 표기법은 지수가 아닌 수는 포함하지 않는다.

• N / 2단계가 필요한 알고리즘은 O(N)으로 표현
• N² + 10단계가 필요한 알고리즘은 O(N²)으로 표현
• 2N 단계가 필요한 알고리즘은 O(N)으로 표현
• O(N)보다 100배 느린 O(100N)이라 해도 마찬가지로 O(N)

 

빅 오 카테고리
빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다.
왜냐하면 일반적인 카테고리로만 분류해도 현저한 차이를 나타내기 충분하기 때문이다.

예를 들어, O(N) 알고리즘과 O(N²) 알고리즘을 비교할 때 두 효율성간 차이가 너무 커서 O(N)이 실제로 O(N / 2)든 O(100N)이든  별로 중요하지 않다.

빅 오 표기법은 데이터가 늘어날 때 알고리즘 단계 수가 장기적으로 어떤 궤적을 그리는지가 중요하다.
O(N)에 어떤 수를 곱하든 데이터가 커지다 보면 언젠가 결국 O(N²)이 더 느려진다는 사실을 깨달으면 완전히 이해가 간다.

 

선택 정렬과 버블 정렬은 어쨌든 같은 카테고리에 속하더라도 서로 처리 속도가 다르다.

따라서 빅 오에서 다른 카테고리에 속하는 알고리즘을 대조할 때는 빅 오가 완벽한 도구지만 같은 카테고리에 속하는 두 알고리즘이라면 어떤 알고리즘이 더 빠를지 알기 위해 더 분석해야 한다.