su3inni
commented
1 year ago 정렬 알고리즘
0. Intro - bubble sort
- 버블 정렬은 정렬 알고리즘 중에 가장 비효율적일 것
- 배열의 아이템을 모두 쭉 살펴보고
- 연달아 있는 아이템 2개의 순서가 잘못된 경우 아이템의 순서를 바꾼다.
- 시간복잡도는 항상 O(n^2) 이다.
- stable sort
1. Merge sort
- 퀵 정렬보다는 느리지만 일정한 실행속도뿐만아니라 Stable sort 이다.
- divide and conquer 의 진수를 보여주는 알고리즘이다.
- 더 이상 쪼갤 수 없을 때 까지 분할한 후
- 분할이 끝나면 정렬하며 conquer한다.
A = [2,8,7,1,3,5,6,4] lo = 0 hi = len(A)-1
def mergesort(arr): if len(arr)<2: return arr
mid = len(arr)//2
low_arr = mergesort(arr[:mid])
high_arr = mergesort(arr[mid:])
merged_arr=[]
l,h=0,0
while l<len(low_arr) and h<len(high_arr):
if low_arr[l]<high_arr[h]:
merged_arr.append(low_arr[l])
l+=1
else:
merged_arr.append(high_arr[h])
h+=1
merged_arr +=low_arr[l:]
merged_arr +=high_arr[h:]
return merged_arrsortA = mergesort(A) print(sortA)
### 1-2. Stable sort vs. UnStable sort
+ 안정 정렬의 경우
+ **중복된 값**을 **입력 순서와 동일하게 정렬**한다.
### 1-3. merge sort를 충분히 설명하고 sort()함수를 이용하는 것도 나쁘지 않을 것
### 2. Quick sort
+ pivot을 기준으로 좌우를 나누는 특징을 가지고 있다.
+ Partition-Exchange sort 라고도 불린다.
+ pivot 보다 작으면 왼쪽 크면 오른쪽과 같은 방식으로 파티션을 분리한다.
+ 연결 리스트에서 퀵 정렬 적용이 어렵다.
+ pivot을 원하는 형태로 설정하기 어려우며
+ 이미 정렬되어있을 경우 불균형 리스트로 나뉘기 때문이다. A = [2,8,7,1,3,5,6,4] lo = 0 hi = len(A)-1
def quicksort(A,lo,hi): def partition(lo,hi):
가장 마지막 값을 pivot으로 설정
pivot = A[hi]
left = lo
for right in range(lo,hi):
if A[right]<pivot:
A[left],A[right]=A[right],A[left]
left+=1
A[left],A[hi] = A[hi],A[left]
return left
if lo < hi :
pivot = partition(lo,hi)
quicksort(A,lo,pivot-1)
quicksort(A,pivot+1,hi)quicksort(A,lo,hi)
### 2-2. Quick sort vs. Merge sort
+ 퀵소트의 경우 **항상 일정한 성능을 보이는 merge sort**와 달리
+ 정렬이 되어있는 경우 O(n^2)이 되는 버블정렬과 같은 성능을 보일 수 있다.
+ **입력값의 영향을 많이 받는 정렬알고리즘**이다!!
> **정렬된 리스트일 경우 무의미**하다.
+ 퀵소트의 경우 merge sort와 달리
+ Unstable sort 이다.
### 3. python의 내장함수 `.sort()`와 `sorted()`
+ Timsort를 사용한다.
+ list 객체에만 사용할 수 있는 sort()
+ 기존 리스트가 정렬된 리스트로 대체된다.
+ 리스트는 mutable한 객체이기 때문이다.
+ 모든 이터러블 객체에 쓸 수 있는 sorted()
+ 리스트, 딕셔너리 , 문자열 ,set
+ 새로운 리스트 객체를 리턴한다.
### Timsort 알고리즘
+ 실제 데이터는 대부분 정렬되어있을 것이라는 가정을 기반한 알고리즘
+ 삽입 정렬과 병합정렬을 적절하게 조합한 알고리즘이다.
+ ref : https://questionet.tistory.com/61
정렬 알고리즘
검색 알고리즘
그래프 알고리즘