1. 버블 정렬
2. 선택 정렬
3. 삽입 정렬
4. 퀵 정렬
5. 합병 정렬(다음 글)
6. 힙 정(다음 글)
0. 정렬을 배우는 이유: 데이터 형태에 따른 시간 복잡도를 줄이기 위함.
0-1 시간복잡도:
버블 정렬, 선택 정렬, 삽입 정렬: O(n^2)
퀵 정렬: 최악->O(n^2) / 평균-> O(nlogn)
합병 정렬, 힙 정렬: 최악, 평균 -> O(nlogn)
1. 버블 정렬(Bubble Sort): 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식. 작은 숫자, 큰 숫자 순서로 있으면 내버려두고 큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경하는 방식 (다음 루프때는 (마지막-1)번째 자료까지 비교)
버블 정렬 단계
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6을 비교
4 < 6 이면 그대로
2단계 : [4, 6, 2, 9, 1]
6과 2를 비교
6 > 2 이므로 둘을 변경
>> [4, 2, 6, 9, 1]
3단계 : [4, 2, 6, 9, 1]
6과 9를 비교
6 < 9 이면 그대로
4단계 : [4, 2, 6, 9, 1]
9와 1를 비교
9 > 1 이므로 둘을 변경
>> [4, 2, 6, 1, 9]
이 과정에서 가장 큰 숫자인 9가 맨 뒤에 위치
큰 게 나오면 둘의 자리를 변경했으니 가장 맨 뒤에 감
따라서, 맨 뒷자리를 제외하고 다시 한 번 돌림
5단계 : [4, 2, 6, 1, 9]
4와 2을 비교
4 > 2 이므로 둘을 변경
>> [2, 4, 6, 1, 9]
6단계 : [2, 4, 6, 1, 9]
4와 6을 비교
4 < 6 이면 그대로
7단계 : [2, 4, 6, 1, 9]
6와 1을 비교
6 > 1 이므로 둘을 변경
>> [2, 4, 1, 6, 9]
두 번째로 큰 숫자인 6이 맨 뒤에서 두번째 위치(6과 9 비교x)
다시 한번 돌림
8단계 : [2, 4, 1, 6, 9]
2와 4을 비교
2 < 4 이면 그대로
9단계 : [2, 4, 1, 6, 9]
4와 1을 비교
4 > 1 이므로 둘을 변경
>> [2, 1, 4, 6, 9]
세 번째로 큰 숫자인 4가 맨 뒤에서 세번째 위치
마지막 비교만 하면 끝
10단계 : [2, 1, 4, 6, 9]
2와 1을 비교
2 > 1 이므로 둘을 변경
>> [1, 2, 4, 6, 9]
버블 정렬 코드구현
#중간에 다 정렬돼도 끝날때까지 반복
def bubblesort(arr):
for i in range(len(arr) - 1):
# 이미 구한 최댓값은 범위에서 제외
for j in range(len(arr) - 1 - i):
if arr[j] > arr[j + 1]:
arr[j + 1], arr[j] = arr[j] + arr[j + 1]
return arr
2. 선택 정렬(Selection Sort): 첫번째 요소와 뒤에 나머지 요소를 비교해, 가장 작은 값(큰 값)과 첫번째 요소 자리 바꿈. 두번째 요소도 뒤에 나머지(첫번째 제외)와 비교해 교환하는 방식
선택 정렬 단계
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6과 2와 9와 1을 차례차례 비교
그 중 가장 작은 1과 맨 앞 자리인 4를 교체
>> [1, 6, 2, 9, 4]
가장 작은 숫자인 1이 맨 앞에 위치
맨 앞자리를 제외하고 다시 한 번 반복
2단계 : [1, 6, 2, 9, 4]
6과 2와 9와 4를 차례차례 비교
그 중 가장 작은 2와 두번째 앞 자리인 6을 교체!
>> [1, 2, 6, 9, 4]
3단계 : [1, 2, 6, 9, 4]
6과 9와 4를 차례차례 비교
그 중 가장 작은 4와 세번째 앞 자리인 6을 교체
>> [1, 2, 4, 9, 6]
4단계 : [1, 2, 4, 9, 6]
9와 6을 비교
그 중 가장 작은 6과 네번째 앞 자리인 9을 교체
>> [1, 2, 4, 6, 9]
버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만,
실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용제일 작은 요소를 바꾸는 방식과 달리 중간중간에 작은 값이 나올때마다 바꿔주는 방식도 선택정렬이라 함
선택 정렬 코드구현
def selectionsort(arr):
for i in range(len(arr) - 1):
min = i
# min에 제일 작은 값의 인덱스를 저장 후, 처음 요소와 같지 않으면 교환
for j in range(i+1, len(arr)):
if arr[min] > arr[j]:
min = j
if min != i:
arr[min],arr[i] = arr[i],arr[min]
return arr
3. 삽입 정렬(Insertion Sort): 하나씩 올바른 위치에 정렬하는 방법
선택 정렬은 계속 끝까지 비교해서 하나씩 바꾸는 방식이라면, 삽입 정렬은 다음 인덱스로 넘어갈때마다 정리하는 방식
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4는 현재까지 정렬되어 있는 구역
정렬하는 구역에 6 추가
4, 6 이 되는데 4 < 6 이므로 그대로
>> [4, 6, 2, 9, 1]
2단계 : [4, 6, 2, 9, 1]
4, 6 은 현재까지 정렬되어 있는 구역
정렬하는 구역에 2 추가
4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경
4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경
>> [2, 4, 6, 9, 1]
3단계 : [2, 4, 6, 9, 1]
2, 4, 6 은 현재까지 정렬되어 있는 구역
정렬하는 구역에 9 추가
2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로
>> [2, 4, 6, 9, 1]
4단계 : [2, 4, 6, 9, 1]
2, 4, 6, 9 는 현재까지 정렬되어 있는 구역
정렬하는 구역에 1 추가
2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경
2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경
2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경
2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경
>> [1, 2, 4, 6, 9]
삽입 정렬 코드구현
def insertionsort(arr):
#맨 앞에거는 안해도 되기 때문에 인덱스가 0이 아닌 1부터 시작, 끝까지 해야함
for i in range(1, len(arr)):
#뒤에서부터 비교하면서 와야하기 때문에 뒤에서부터 -1씩 더하는 range씀
for j in range(i,0,-1):
#앞에게 뒤에거보다 크면 위치 바꿈
if arr[j-1] > arr[j]:
arr[j-1], arr[j] = arr[j], arr[j-1]
else:
break
return arr
4. 퀵 정렬(Quick sort): 분할 정복(Divide and Conquer)을 통해 주어진 배열을 정렬하는 알고리즘. 배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눔(Divide). 그리고 그 사이에 기준(pivot)을 놓는 작업을 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤(Conquer) 결과를 합치는 방법
[1, 6, 2, 9, 4] # 정렬되지 않은 배열
1단계: [1, 6, 2, 9, 4]
마지막 원소인 4를 pivot
pivot보다 작은 집합의 인덱스 i를 -1로 설정
(i=-1)
2단계: [1, 6, 2, 9, 4]
j를 0에서부터 3까지 확인
j가 0이므로 지금 살펴보고 있는 값은 1 입니다.
1는 pivot(4)보다 작읍니다.
i를 1 증가시켜 0으로 만듭니다.
i 와 j 의 위치를 바꿉니다.
i와 j가 동일하므로 아무 일도 일어나지 않습니다.
(i=0, j=0)
3단계: [1, 6, 2, 9, 4]
j를 1 증가시켜 1로 만듭니다.
지금 살펴보고 있는 값은 6 입니다.
6은 pivot(4)보다 큽니다
넘어갑니다.
(i=0, j=1)
4단계: [1, 6, 2, 9, 4]
j를 1 증가시켜 2로 만듭니다.
지금 살펴보고 있는 값은 2 입니다.
2는 pivot(4)보다 작습니다.
i를 1 증가시켜 1로 만듭니다.
i(1) 와 j(2) 의 위치를 바꿉니다.
배열은 [1, 2, 6, 9, 4]가 됩니다.
(i=1, j=2)
5단계: [1, 2, 6, 9, 4]
j를 1 증가시켜 3으로 만듭니다.
지금 살펴보고 있는 값은 9 입니다.
9는 pivot(4)보다 큽니다.
넘어갑니다.
(i=1, j=3)
6단계: j를 0부터 3까지 모두 살펴보았습니다.
i는 pivot보다 작은 집합의 범위를 나타내므로, i+1과 pivot의 위치를 바꿉니다.
배열은 [1, 2, 4, 9, 6] 이 됩니다.
7단계: [1, 2]와 [9, 6]을 대상으로 1~6단계를 반복합니다.
결과적으로 [1, 2, 4, 6, 9]가 됩니다.
정렬이 끝났습니다.
퀵 정렬 코드구현
기준을 잡고 그 값보다 작으면 앞에 밀어 넣는 형식의 알고리즘
def quicksort(arr, start, end):
#pivot보다 작은구간은 문제 없지만, pivot보다 큰 구간은 마지막에서 start보다 end가 커져 에러나기때문에
#어차피 정렬 다 된것이므로 마지막꺼는 반환 안해도 됨
#함수 이해하려면 if절 다음꺼부터 보세요~~~
if start > end:
return
i = start-1 #i는 pivot보다 작은것들을 담을 준비
pivot = arr[end] #끝에 있는 요소를 기준으로 잡음
#시작부터 끝보다 1작을때까지(끝에 요소는 pivot)
for j in range(start, end):
#j는 현재 보고있는 곳, i는 pivot보다 작은것들이 들어갈 공간들
#현재 보고있는 것이 기준(pivot)보다 작다면 왼쪽 시작점부터 차근차근 채움
#i의 초기 값이 정렬하려는 공간의 시작점이므로 i+1의 의미가 왼쪽 처음부터 차근차근 넣겠다는 얘기
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
#pivot을 큰거와 작은거 사이에 넣음(i까지는 작은게 들어가있음)
arr[i+1], arr[end] = arr[end], arr[i+1]
#pivot보다 작은것들은 정렬이 안되어있으니
#start를 처음으로 end를 i로 (pivot은 i+1에 위치해있으니까) 재귀함수를 불러 작은것들이 다 정렬되게 함
quicksort(arr, start, i)
#pivot보다 큰것들도 정렬이 안되어있으니
#큰것들은 pivot보다 다 오른쪽에 있는것이므로 start를 i+2(pivot은 i+1에 위치해있으니까)
#end를 끝으로 재귀함수를 불러 큰것들이 다 정렬되게 함
quicksort(arr, i + 2, end)
return arr
'알고리즘' 카테고리의 다른 글
| 유클리드 호제법 (약수 개수, 최대 공약수, 최소 공배수) (0) | 2024.07.09 |
|---|---|
| 알고리즘 4 (합병 정렬, 힙 정렬) (0) | 2024.06.28 |
| 파이썬 미로 탈출 경로 찾기 / 순열 생성하기 (0) | 2024.06.20 |
| 알고리즘 2 (BFS, 백 트래킹, 이진탐색) (1) | 2024.06.17 |
| 알고리즘 1 (그래프, DFS) (0) | 2024.06.14 |