목차
1. 버블 정렬
2. 버블 정렬 그림으로 이해
3. 선택 정렬
4. 선택 정렬 그림으로 이해
5. 코드
6. 느낀점
정렬에는 다양한 종류가 있다.
그중에서도 이번 장에서는 상대적으로 익히기 쉬운 버블 정렬과 선택 정렬에 대해서 공부해보자.
버블 정렬
버블 정렬은 데이터의 인접한 요소끼리 비교를 한 후 swap하여 정렬하는 알고리즘이다.
버블 정렬의 시간 복잡도는 O(n^2)으로 효율적이진 않다.
버블 정렬 그림으로 이해
우리는 아래와 같은 리스트 형태로 저장된 데이터를 버블 정렬을 이용하여 오름차순 정렬하려고 한다.
아래와 같이 1번 째 부분과 2번 째 부분을 비교한다. 이때 1번 째 부분의 데이터가 더 크니 SWAP해준다.
이번에는 2번 째 부분과 3번 째 부분을 비교한다. 이때 2번 째 부분의 데이터가 더 크니 SWAP해준다.
이 과정을 반복하면 정렬된 부분이 생긴다.
이 정렬된 부분을 계속해서 늘려나가 리스트의 크기만큼 커지도록 하면 최종적으로 오름차순이 된다.
선택 정렬
선택 정렬은 이름 그대로 남은 리스트의 최소or최대를 찾아 맨 앞과 SWAP하는 과정을 반복하여 정렬하는 알고리즘이다.
선택 정렬 역시 시간 복잡도 O(n^2)이다.
선택 정렬 그림으로 이해
아래와 같은 리스트가 존재한다.
우리는 선택 정렬을 이용해 아래 리스트를 오름차순 정렬을 할 것이다.
현재는 전체가 남은 부분이기 때문에 전체중에 최솟값을 찾는다.
이때 1이 최소이므로 선택한다.
현재 남은 부분에서 가장 앞은 7이므로 7과 1을 SWAP한다.
이렇게되면 정렬된 부분과 남은 부분으로 나누어지는데
정렬된 부분을 계속 늘려나가 최종적으로 전체가 정렬될 때까지 반복하면 된다.
다음은 최종적으로 리스트가 정렬될 때까지 선택정렬을 반복한 것을 시각화 한 것이다.
이렇게 선택정렬을 반복해서 최종적으로 오름차순으로 정렬할 수 있었다.
이제 코드를 통해 버블 정렬과 선택정렬을 어떻게 구현하는지 살펴보자.
코드
버블 정렬(Bubble Sort)
num = [7, 6, 1, 3, 4, 2]
N = len(num)
for i in range(N):
for j in range(i + 1,N):
if num[i] > num[j]: # Swap
temp = num[i]
num[i] = num[j]
num[j] = temp
print(num)선택 정렬(Selection Sort)
num = [7, 6, 1, 3, 4, 2]
N = len(num)
for i in range(N):
MinIdx = i # 최솟값 인덱스 초기화
for j in range(i + 1,N):
if num[MinIdx] > num[j]: # 인덱스 초기화 조건
MinIdx = j
temp = num[MinIdx] # Swap
num[MinIdx] = num[i]
num[i] = temp
print(num)느낀점
사실 버블 정렬과 선택 정렬보다는 퀵 정렬이나 병합 정렬을 더 많이 쓸 것이다.
하지만 초반에 다루기 쉬운 정렬에 대해서 완벽하게 숙지를 하고 나가면 좋을 것같다고 생각했다.
