728x90
- 나누어 풀어보기
- 선택 정렬(Selection sort) : 가장 작은 숫자가 적힌 카드를 찾아 맨 왼쪽에 놓고, 나머지 카드 중에서 가장 작은 숫자를 찾아 맨 왼쪽 카드 다음에 놓고, 이를 반복하여 모든 카드를 정렬한다.
- 버블 정렬(Bubble sort) : 첫 번째 숫자와 두 번째 숫자를, 두 번째 숫자와 세 번째 숫자를, 세 번째 숫자와 네 번째 숫자를 ,... 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
- 힙 정렬(Heap sort) : 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만들고 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장한다. 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.
- 퀵 정렬(Quick sort) : 맨 왼쪽 숫자를 피벗으로 삼는다. 피벗과 각 숫자를 비교하여 피벗보다 작거나 같은 숫자들을 왼쪽으로 큰 숫자들은 오른쪽으로 나누고, 피벗을 그 사이로 옮긴다. 피벗보다 작거나 같은 부분을 동일한 방법으로 정렬한다. 피벗보다 큰 부분을 동일한 방법으로 정렬한다.
# 퀵 정렬 함수 정의
def quick_sort(arr):
# 재귀 종료 조건: 배열의 길이가 1 이하이면 이미 정렬된 상태
if len(arr) <= 1:
return arr
# 피벗 선택 (여기서는 리스트의 첫 번째 요소를 피벗으로 선택)
pivot = arr[0]
# 피벗을 기준으로 작은 값과 큰 값으로 나누기
less = [x for x in arr[1:] if x <= pivot] # 피벗 이하
greater = [x for x in arr[1:] if x > pivot] # 피벗 초과
# 재귀적으로 정렬 후 병합
return quick_sort(less) + [pivot] + quick_sort(greater)
# 테스트용 리스트
arr = [7, 2, 1, 6, 8, 5, 3, 4]
# 퀵 정렬 실행
sorted_arr = quick_sort(arr)
print(sorted_arr)[1, 2, 3, 4, 5, 6, 7, 8] => 코드 실행 결과
- 합병 정렬(Merge Sort)
합병 정렬은 크기가 n인 입력을 n/2크기 2개로 분할하고, 각각에 대해 같은 방법으로 합병 정렬을 수행한 후, 2개의 각각 정렬된 부분을 합병
합병(Merge) 2개의 각각 정렬된 리스트를 합치어 정렬하는 것
분할 정복(Divide-and-Conquer) 알고리즘 : 입력을 분할하여 분할된 입력 각각에 대한 문제(부분 문제)를 같은 방법으로 해결한 후 취합하여 문제를 해결하는 알고리즘
- 현재 입력 크기가 1이면 return
- 현재 입력을 반으로 나눈다.
- 앞부분을 동일한 방법으로 정렬
- 뒷부분을 동일한 방법으로 정렬
- 정렬된 앞부분과 뒷부분을 합병
# 합병 정렬 함수 정의
def merge_sort(arr):
# 재귀 종료 조건: 배열의 길이가 1 이하이면 이미 정렬된 상태
if len(arr) <= 1:
return arr
# 배열을 두 부분으로 나누기
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# 재귀적으로 두 부분을 정렬
left_sorted = merge_sort(left)
right_sorted = merge_sort(right)
# 두 정렬된 부분을 병합
return merge(left_sorted, right_sorted)
# 두 정렬된 리스트를 병합하는 함수
def merge(left, right):
sorted_list = []
i = j = 0
# 두 리스트를 비교하며 정렬된 결과 생성
while i < len(left) and j < len(right):
if left[i] <= right[j]:
sorted_list.append(left[i])
i += 1
else:
sorted_list.append(right[j])
j += 1
# 남은 요소를 추가
sorted_list.extend(left[i:])
sorted_list.extend(right[j:])
return sorted_list
# 테스트용 리스트
arr = [7, 2, 1, 6, 8, 5, 3, 4]
# 합병 정렬 실행
sorted_arr = merge_sort(arr)
print(sorted_arr)[1, 2, 3, 4, 5, 6, 7, 8] => 코드 실행 결과
- 어떤 입력에 대해서도 T(n) = O(nlogn) 시간 보장
- [단점] => 합병을 위해 입력 크기의 보조 메모리가 필요
- K 번째 작은 수 찾기
- 피벗을 랜덤하게 선택
- 피벗과 각 숫자를 비교하여 피벗보다 작은 숫자들을 왼쪽으로, 큰 숫자들을 오른쪽으로 나누고, 피벗을 그 사이에 둠
- K번째 작은 숫자가 피벗이면 탐색 성공
- K번째 작은 숫자가 피벗보다 작은 부분에 있으면, 작은 부분에서 동일한 방법으로 탐색
- 피벗보다 큰 부분에 있으면, K를 수정하여 큰 부분에서 동일한 방법으로 탐색
평균 경우 수행 시간 : O(n)
728x90