정렬 알고리즘의 핵심은 교환, 선택, 삽입!
-
내부정렬과 외부정렬
- 내부정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우
- 외부정렬 : 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우
-
버블 정렬
-
이웃한 두 원소의 대소관계를 비교(단순 교환 정렬)
# [Do it! 실습 6-1] 버블 정렬 알고리즘 from typing import MutableSequence def bubble_sort(a: MutableSequence) -> None: """버블 정렬""" n = len(a) # a의 길이 n , 0에서 n-1까지 i 반복 # n-1에서 i까지, -1씩 j 반복 // 마지막 인덱스에서 처음 인덱스까지 # j-1 > j 이면 j-1에 j값을, j에 j-1값을 넣어줌(**교환**) # j 한 바퀴 도는게 패스 하나 # i가 반복하는 횟수 = 패스 횟수 for i in range(n - 1): for j in range(n - 1, i, -1): if a[j - 1] > a[j]: a[j - 1], a[j] = a[j], a[j - 1] if __name__ == '__main__': print('버블 정렬을 수행합니다.') num = int(input('원소 수를 입력하세요.: ')) **x = [None] * num # 원소 수가 num인 배열을 미리 생성** for i in range(num): x[i] = int(input(f'x[{i}] : ')) // input(f'x[{i}] : ') 이게 f가 뭘까 bubble_sort(x) # 배열 x를 버블 정렬 print('오름차순으로 정렬했습니다.') for i in range(num): print(f'x[{i}] = {x[i]}') -
개선1 : 교환 횟수에 따른 패스 중단
- 각 패스내에서 교환이 일어나는 횟수를 카운트
- 패스가 끝나고 교환 횟수가 0이면
- 이미 정렬이 완료된 것이므로 함수 종료
-
개선2 : 마지막 교환 인덱스에 따른 패스 스킵
- 각 패스내에서 교환이 일어나는 인덱스를 저장
- 패스가 끝나고 마지막으로 교환이 일어난 인덱스까지의 패스를 스킵
- 마지막으로 교환이 일어난 인덱스부터 다시 진행
-
셰이커 정렬 : 버블정렬을 개선한 정렬방법으로, 앞뒤방향으로 번갈아가면서 패스를 진행
- 마지막 교환 인덱스를 저장하기 위한 변수 last = right로 초기화 // 뒤에서부터 올거니까
- left는 처음인덱스(0), right는 마지막인덱스(len(a)-1)로 초기화
- 전체를 정렬하기 위한 while문의 조건 : left<right // 뒤에서 오는 커서(right)와 앞에서 오는 커서(left)가 겹치면 중단
- 앞,뒤 방향 정렬은 각각 for문으로 작성
- for j in range(right, left, -1) // 정렬안된 뒤에서 앞으로 -1씩 이동
- for j in range(left, right) // 정렬안된 앞에서 뒤로 1씩 이동
- 각 for문 안에서 교환이 일어날때 last에 해당 인덱스(j)를 저장
// 앞으로 오는 건 j-1 > j 를 비교
// 뒤로 가는 건 j > j+1 을 비교 - for문이 완료되면(패스가 끝나면) last를 left와 right에 업데이트
- 앞뒤로 스킵하면서 진행하다가 (left는 뒤를 향해, right는 앞을 향해)
교환이 없는 패스가 오면 last가 업데이트가 안되고
지난 last가 left or right 커서에 업데이트 되면서(같은 인덱스를 가리키게됨)
다음 패스를 시작하기 위한 조건문에서 (left<right : False) 종료
[ ] 예제 코드 넣기
-
-
단순 선택정렬
-
가장 작은 원소부터 선택해 알맞은 위치로 옮겨서 정렬
-
배열 안에서 가장 작은 원소를 찾음
→ 맨 앞 원소와 교환
→ 그럼 맨 앞은 정렬된거 -
이어서 정렬되지 않은 원소들 중 가장 작은 값을 찾고
→ 정렬되지 않은 가장 앞쪽 원소와 교환
→ 을 반복 -
단순선택정렬에서 교환과정은 다음과 같습니다.
- 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택
- a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환
-
이걸 n-1번 반복하면 정렬이 완료됨
# [Do it! 실습 6-6] 단순 선택 정렬 알고리즘 구현 from typing import MutableSequence def selection_sort(a: MutableSequence) -> None: """단순 선택 정렬""" n = len(a) for i in range(n - 1): min = i # 정렬 할 부분에서 가장 작은 원소의 인덱스 for j in range(i + 1, n): if a[j] < a[min]: min = j a[i], a[min] = a[min], a[i] # 정렬 할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환 if __name__ == '__main__': print('단순 선택 정렬을 수행합니다.') num = int(input('원소 수를 입력하세요.: ')) x = [None] * num # 원소 수가 num인 배열을 생성 for i in range(num): x[i] = int(input(f'x[{i}] : ')) selection_sort(x) # 배열 x를 단순 선택 정렬 print('오름차순으로 정렬했습니다.') for i in range(num): print(f'x[{i}] = {x[i]}') -
단순 선택 정렬 알고리즘에서 원솟값을 비교하는 횟수는 (n^2 - n)/2
-
서로 이웃하지 않는 원소를 교환하므로 안정적이지 않음
→ 중복된 숫자를 교환
-
-
단순 삽입 정렬
-
셀 정렬
-
퀵 정렬
- 가장 빠른 정렬 알고리즘
- 피벗(중심축) : 그룹을 두개로 나누는 기준
- 배열 나누기
- pl x pr
왼쪽커서, 피벗(중심축), 오른쪽커서를 설정 - pl pr
왼쪽커서는 오른쪽으로, 오른쪽커서는 왼쪽으로 피벗과 값을 비교하면서 진행
왼쪽값이 피벗보다 크거나 오른쪽값이 피벗보다 작을때 멈춰서 값 교환 - 가운데에서 교차되거나 마주칠때도 값 교환
- 피벗을 지나쳐서 pr<pl이 되면 그러니까 pl≤pr 이 성립하지 않으면 끝남
- 피벗과 일치하는 그룹이 생기는 케이스는 pl>pr+1 일때 뿐
- left ( [0] ) 부터 pl ( [pl-1] ) 까지가 피벗 이하인 그룹
pr ( [pr+1] ) 부터 right ( [n-1] ) 까지가 피벗 이상인 그룹
- pl x pr
- 퀵정렬 만들기
-
분할 정복 알고리즘, 재귀 호출
# [Do it! 실습 6-10] 퀵 정렬 알고리즘 구현 from typing import MutableSequence def qsort(a: MutableSequence, left: int, right: int) -> None: """a[left] ~ a[right]를 퀵 정렬""" pl = left # 왼쪽 커서 pr = right # 오른쪽 커서 x = a[(left + right) // 2] # 피벗(가운데 요소) while pl <= pr: # 실습 6-10과 같은 while 문 while a[pl] < x: pl += 1 while a[pr] > x: pr -= 1 if pl <= pr: a[pl], a[pr] = a[pr], a[pl] pl += 1 pr -= 1 if left < pr: qsort(a, left, pr) if pl < right: qsort(a, pl, right) def quick_sort(a: MutableSequence) -> None: """퀵 정렬""" qsort(a, 0, len(a) - 1) if __name__ == '__main__': print('퀵 정렬을 수행합니다.') num = int(input('원소 수를 입력하세요.: ')) x = [None] * num # 원소 수가 num인 배열을 생성 for i in range(num): x[i] = int(input(f'x[{i}]: ')) quick_sort(x) # 배열 x를 퀵 정렬 print('오름차순으로 정렬했습니다.') for i in range(num): print(f'x[{i}] = {x[i]}')
-
- 비재귀적 퀵정렬
# [Do it! 실습 6-12] 퀵 정렬 알고리즘 구현(비재귀적인 퀵 정렬) from stack import Stack # 실습 4C-1의 파일 import from typing import MutableSequence def qsort(a: MutableSequence, left: int, right: int) -> None: """a[left] ~ a [right]를 퀵 정렬(비재귀 버전)""" **range = Stack(right - left + 1) # 스택 생성** **range.push((left, right))** while not range.is_empty(): **pl, pr = left, right = range.pop()** # 왼쪽, 오른쪽 커서를 꺼냄 x = a[(left + right) // 2] # 피벗(중앙 요소) while pl <= pr: while a[pl] < x: pl += 1 while a[pr] > x: pr -= 1 if pl <= pr: # 실습 6-10, 실습 6-11과 같음 a[pl], a[pr] = a[pr], a[pl] pl += 1 pr -= 1 **if left < pr: range.push((left, pr))** # 왼쪽 그룹의 커서를 저장 **if pl < right: range.push((pl, right))** # 오른쪽 그룹의 커서를 저장 def quick_sort(a: MutableSequence) -> None: """퀵 정렬""" qsort(a, 0, len(a) - 1) if __name__ == '__main__': print('비재귀적인 퀵 정렬') num = int(input('원소 수를 입력하세요.: ')) x = [None] * num # 원소 수가 num인 배열을 생성 for i in range(num): x[i] = int(input(f'x[{i}]: ')) quick_sort(x) # 배열 x를 퀵 정렬 print('오름차순으로 정렬했습니다.') for i in range(num): print(f'x[{i}] = {x[i]}') - 스택
- 피벗 선택하기
- 시간복잡도
-
병합 정렬
-
힙 정렬
-
선택 정렬을 응용한 알고리즘
-
힙의 특성을 이용하여 정렬하는 알고리즘
- 힙 : 부모의 값이 자식의 값보다 항상 크다(작다)는 조건을 만족하는 완전 이진 트리
- 그래서 루트가 가장 큰 값임
- 완전 이진 트리
- 트리 : 각 원소를 의미하는 노드들이 연결된 계층 구조
- 루트 : 가장 윗부분에 위치한 부모가 없는 노드
- 부모노드, 자식노드, 형제노드
- 완전 : 부모는 왼쪽 자식부터 추가하여 모양을 유지함
- 이진 : 부모가 가질 수 있는 최대 자식 수가 2개
- 트리 : 각 원소를 의미하는 노드들이 연결된 계층 구조
-
부모와 자식간의 대소관계는 일정하지만 형제사이의 대소관계는 일정하지 않음
(부분 순서 트리) -
힙을 배열에 저장하기
-
가장 위쪽에 있는 루트를 a[0]에 저장
-
한단계 아래에서 왼쪽에서 오른쪽원소로 따라감
-
배열의 인덱스값을 1씩 증가시키면서 각 원소를 저장
0 1 23 4 5 6
7 8 9
-
-
뭐 대충 이런 순서
-
이런 순서로 힙을 배열에 저장하면 규칙이 생김
-
원소 a[i]에서
- 부모 : a[(i-1)//2]
- 왼쪽 자식 : a[i*2+1]
- 오른쪽 자식 : a[i*2+2]
-
힙 정렬의 특징 :: 힙에서 최댓값은 루트에 위치한다.
- 힙에서 최댓값인 루트를 꺼냄
- 루트 이외의 부분을 힙으로 만듦
- 꺼낸 값을 나열하면 정렬된 배열
- 힙 정렬에서 루트를 꺼내면 남은 원소로 구성한 트리도 힙이 되도록 재구성 해야함
-
루트를 삭제한 힙의 재구성
- 힙에서 루트인 최댓값을 꺼냄
- 비어있는 루트 위치에 힙의 마지막 원소를 이동
→ 이동한 원소 외에는 힙 상태를 유지함
→ 원소만 알맞은 자리를 찾아가면 됨 - 바로 아래 자식 노드부터 봄
→ 힙을 구성하려면 최댓값이 부모가 되어야 함
→ 자식중에 더 큰 원소와 교환 - 다음 자식들 중에서도 더 큰 값과 교환
- 원소가 트리 가장 아랫부분(리프, leaf)으로 이동하거나, 자식이 원소보다 작을 때까지 4번 반복
- 정리하면
- 루트를 꺼냄
- 마지막원소(가장하단오른쪽)를 루트로 이동
- 루트에서 시작해서 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복
자식의 값이 작거나 리프의 위치에 도달하면 종료
-
힙 정렬 알고리즘
- 힙의 루트 a[0]에 있는 최댓값을 배열의 맨 끝 원소 a[n-1]과 교환
- 최댓값을 이동했으니 a[n-1]은 정렬을 마침
- a[0] ~ a[n-2]의 원소를 힙으로 만듦
- 두번째로 큰 값이 루트 a[0]에 오고
- 이걸 다시 꺼내서 아직 정렬하지 않은 부분의 맨 끝 원소 a[n-2]와 교환
- 그럼 a[n-2] ~ a[n-1] 은 정렬이 완료됨
- 마찬가지로 a[0] ~ a[n-3] 까지를 힙으로 만들고
- 다음 루트와 아직 정렬하지 않은 부분의 맨 끝 원소와 교환하는 것을 반복
- 힙정렬
- 정리하면
- i값을 n-1로 초기화
- a[0]과 a[i]를 교환
- a[0], a[1], ... , a[i-1]을 힙으로 만듦
- i를 1씩 감소시키면서 2,3번을 반복하고 i가 0이 되면 종료
- 힙 정렬 알고리즘을 수행하기 전에 배열을 반드시 힙으로 만들어야함!
-
배열을 힙으로 만들기
- 루트를 삭제한 힙을 재구성하려면 마지막 원소를 루트로 이동시켜서 알맞은 위치까지 아래로 옮겨야 했듯이
- 힙이 아닌 서브트리에 대해서도 이 방법을 적용할 수 있음
- 가장 아랫부분의 작은 서브트리부터 상향식(bottom-up)으로 진행하여 전체 배열을 힙으로 만듦
- 가장 아랫부분 오른쪽 서브트리의 힙을 만들고, 같은단계 왼쪽 서브트리도 힙을 만듦
- 한단 계 위로 이동해서 오른쪽, 왼쪽 순으로 다시 힙을 만듦
- 루트까지 올라가서 루트에 있는 숫자까지 알맞은 위치로 내려보내면 힙이 만들어짐
- 실습
-
시간복잡도
- 단순 선택 정렬의 시간복잡도는 O(n^2)
- 힙 정렬의 시간복잡도는 O(nlogn)
-
heapq 모듈도 있음
-
-
도수 정렬
- 도수 분포표를 이용한 정렬
- 원소의 대소관계를 판단하지 않고 빠르게 정렬하는 알고리즘(분포수세기 정렬)
- 도수 분포표처럼 특정 계급내에 해당하는 개수를 분포시켜서 정렬을 획득
- 1단계 : 도수 분포표 만들기
- 정렬할 숫자가 들어있는 배열a말고
- 도수 분포표를 만들 배열f가 필요함(개수는 정렬할 숫자의 최댓값+1)
- 배열f는 0으로 초기화
- 배열 a의 값에 해당하는 배열 f의 인덱스에 1을 증가시킴 // for문으로 a 한바퀴
- 2단계 : 누적 도수 분포표 만들기
- 배열 f 안에서 앞 인덱스(i-1)의 값(f[i-1])을 뒤 인덱스(i)에 누적시킴 // f[i] += f[i-1]
// i랑 i-1을 쓸거면 1부터 max+1까지, i+1이랑 i를 쓸거면 0부터 max까지
- 배열 f 안에서 앞 인덱스(i-1)의 값(f[i-1])을 뒤 인덱스(i)에 누적시킴 // f[i] += f[i-1]
- 3단계 : 작업용 배열(b) 만들기
- 원래 배열 a와 도수 분포표 배열 f를 이용해 정렬된 숫자를 담을 배열 b를 만듦 // 크기는 a랑 똑같
- 배열 a를 뒤(n-1)에서부터 스캔해올거임
- 배열 a가 가진 값에 해당하는 f의 인덱스를 찾고 해당 인덱스의 값을 -1 시킴
→ f[a[i]] -= 1 - 배열 f의 값(방금 1 감소시킨 값)을 인덱스로 가지는 배열b로 감
- 거기다 a[i]값 대입 → b[f[a[i]]] = a[i]
- 끝까지 하고나면 b에 정렬됨
- 4단계 : b에 있는 거 a로 복사
- for문 이용해서 복사
- // 이건 꼭 안해도 되는거 같음
