정렬 알고리즘 (버블 정렬,선택 정렬)

저번 셔플에 이어 금요일의 주제는 정렬 알고리즘 (버블,선택)이다.

정렬은 우리가 원하는 대로 순차적으로 1..2..3....100까지 되게 하는것이다.

 

그 목적을 이루기 위해 여러 알고리즘들이 있는데.. 가장 접근하기 쉬운 버블 정렬과 선택 정렬 알고리즘을 알아보자.

 

먼저 버블정렬은 간단하게 말하면, 앞과 뒤를 교환하는것이다.

 

여기 무작위로 섞인 카드가 있다고 해 보자.

 

2,1,5,3,4 이것을 정렬하고 싶다.

 

그렇다면!! 맨 앞부터 (앞과 그 옆) 두개의 카드를 골라 비교한다.  그래서 첫 번째 카드 2와 근접한 카드 1을 골라서

 

서로 비교를 한다. 2가 1보다 크니까 서로 위치를 바꾼다. 그러면 1,2가 된다. 그렇다면 이제 두 번째 카드를 고른다. 

 

두 번째 카드는 2이다. (아까 바꿨으니까) 그리고 그와 근접한 오른쪽 카드 5를 비교한다. 

2는 5보다 크지 않다. 그대로 둔다. 다음 세 번째 카드 5를 고르고 그 옆에 있는 카드 3을 고른다.

둘이 비교하면 5는 3보다 크니 서로 위치를 교환한다. 12354가 된다.

마지막으로 네 번째 카드 5와 그 옆에 카드 4를 골라 비교한다. 5는 4보다 크니 위치를 교환한다.

즉 12345 정렬이 되었다. 버블 정렬은 이런식으로 진행된다.

 

이번 예시는 운이 좋아서 한번으로 정렬이 되었는데 

 

이 정렬 과정을 반복해야지 정렬이 되는 경우도 있다. 

 

예 : 5,2,3,1,4

 

그렇다면 어떻게 정렬을 해야 할까? 

 

이 버블 정렬 알고리즘의 규칙을 살펴보면 큰수가 계속 뒤로 밀려나는것을 알 수 있다.

 

즉 한번 반복할 때 마다 거기 있는 제일 큰 수는 정확한 위치에 있다는것을 알 수 있다.

 

그렇다면, 한번 반복할 때 마다 맨 뒷자리를 감소시키면서 반복하면 정렬 알고리즘이 완성된다.

 

이제 개념을 알았으니 코드로 구현을 해 보자.

 

배열을 받고~

 

이중 for문을 돈다.

 

여기서 i는 맨 끝에 정렬된 위치를 의미한다. 

 

j는 0부터 i까지 비교를 해서 정렬을 한다.

 

for문에서 i - 1번까지 하는 이유는 마지막 수 + 1을 해버리면 Index Out Exception이 발생하기 때문.. 따라서 -1을 해주면 자연스럽게 + 1을 해도 괜찮.

 

쨋든 핵심은 비교를 통해 서로의 위치를 교환해서 제일 큰 수를 뒤로 미뤄두고 또 다시 반복해서 미뤄두고 ...이것을 반복하면 정렬이 되는것!

 

완성했으니 이제 선택 정렬을 알아보자..

 

선택 정렬은 최소값을 찾아서 맨 앞에 위치시키는것!

 

다시 무작위의 카드 다섯장이 있고 선택 정렬을 진행한다면 다음과 같이 진행된다.

 

먼저 배열의 요소들중에 최소값을 찾는다. 그것을 맨 앞에 위치시킨다.

 

이번 패턴도 맨 앞에 자리는 최소값이라는 보장이 된다. 따라서 그 다음 반복시에는 맨 첫번째를 굳이 확인 안해도 된다.

 

그래서 맨 앞에 자리를 +1 증가시키고 또다시 최소값을 찾는 형태로 진행이 된다. 

 

이것을 코드로 구현 해 본다면 다음과 같다.

이번에는 i가 증가하는 형태.. 다시 말하지만 첫 번째 부터 최소값이 보장되니까.. 증가하는것!

그래서 i부터 (최소값 부터 배열의 길이까지) 최소값을 탐색한다.

 

그래서 최소값 인덱스를 구한 뒤, 첫 번째 위치와 인덱스의 위치를 서로 교환한다. 

 

이런식으로 정렬이 진행된다는 사실~~

 

두 정렬 알고리즘의 시간 복잡도는 동일하다. 하지만 선택 정렬이 조금 더 우수한 성능을 보여준다고 한다.

 

왜냐하면.. 버블 정렬은 반복마다 무조건 교환을 하게 되어있다.

 

하지만 선택 정렬은 최소값을 구했을때만 교환을 하기 때문에 교환 횟수가 적다. 그만큼 더 빠를 수 있다는 소리이다.