파이썬 SW문제해결 기본 - LIST 1
05 Sort(정렬)-버블 정렬
05. Sort
① 정렬 개요
▣ 정렬(Sort)이란?
- 2개 이상의 자료를 특정 기준에 따라 순서대로 재배열하는 것이다.
- 작은 값부터 큰 값 : 오름차순(ascending)
- 큰 값부터 작은 값 : 내림차순(descending)
▣ 대표적인 정렬 방식의 종류
- 버블 정렬 : 인접한 두 원소를 검사하여 정렬하는 방법이다. (최악: O(n^2) / 평균: O(n^2))
- 카운팅 정렬 : 각 항목의 개수를 센(Counting) 후에 정렬하는 방법이다. (최악: O(n+k) / 평균: O(n+k))
- 선택 정렬 : 최솟값을 찾아 정렬되지 않은 맨 앞의 값과 교체하는 방법이다. (최악: O(n^2) / 평균: O(n^2))
- 삽입 정렬 : 모든 요소를 이미 정렬된 리스트와 비교하며 위치를 찾아 삽입하는 방법이다. (최악: O(n^2) / 평균: O(n^2))
- 퀵 정렬 : 하나의 요소(피벗)를 기준으로 리스트를 나눠가며 재귀적으로 정렬하는 방법이다. (최악: O(n^2) / 평균: O(nlogn))
- 병합(합병) 정렬 : 원소를 하나만 포함하는 n개의 리스트로 분할하고 각 리스트를 병합하며 정렬하는 방법이다. (최악: O(nlogn) / 평균: O(nlogn))
위 나열한 정렬 방식 중 이번 포스팅에서는 버블 정렬과 카운팅 정렬(은 다음 포스팅에 있다)만을 다룬다. 나머지는 추후에 차차 다룰 예정이다.
② 버블 정렬
▣ 버블 정렬
- 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식이다.
- 정렬 과정
1) 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.
2) 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬된다.
3) 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양 같아서 '버블 정렬'이라고 한다.
- 최악 시간 복잡도 : O(n^2) // 평균 시간 복잡도 : O(n^2)
▣ [55, 7, 78, 12, 42]를 버블 정렬(오름차순)하는 과정
첫 번째 반복
두 번째 반복
세 번째 반복(이미 정렬은 완료됐지만 컴퓨터는 정렬의 완료 여부를 알 수 없기에 계속 반복한다.)
네 번째 반복
다섯 번째 반복
- 버블 정렬의 과정은 위와 같다. 내가 일일이 그림으로 만들며 포스팅하는 데는 이유가 있다. 바로 저번 포스팅에서 언급했던 시간 복잡도를 직접 따라가며 계산하고 이해해보기 위함이다.
- [7, 12, 42, 55, 78]을 버블 정렬하기 위해 비교는 10번, 교환은 5번 수행됐다.
- 버블 정렬의 시간 복잡도는 위에서 언급됐듯 O(n^2)이다.
- 파이썬으로 이를 구현해보면 다음과 같다.
def bubbleSort(x): #x는 정렬할 LIST
length = len(x)-1
for i in range(length):
for j in range(length-i):
if x[j] > x[j+1]:
x[j], x[j+1] = x[j+1], x[j]
return x
원래 계획은 이번 포스팅에서 버블 정렬과 카운팅 정렬을 모두 다루는 것이었으나, 예상외로 포스팅 길이가 길어졌다. 카운팅 정렬은 바로 다음 포스팅에 이어 작성하겠다.
'SWEA() > Intermediate_Learn' 카테고리의 다른 글
| [SWEA]4828. 파이썬 SW문제해결 기본 - LIST 1 : min max (0) | 2021.10.17 |
|---|---|
| [SWEA]파이썬 SW문제해결 기본 - LIST 1 : Sort(정렬)-카운팅 정렬 (0) | 2021.10.16 |
| [SWEA]파이썬 SW문제해결 기본 - LIST 1 : Greedy Algorithm (0) | 2021.10.13 |
| [SWEA]파이썬 SW문제해결 기본 - LIST 1 : Exhaustive Search(완전 탐색) (0) | 2021.10.12 |
| [SWEA]파이썬 SW문제해결 기본 - LIST 1 : 알고리즘, 리스트 (0) | 2021.10.11 |