1. 병합정렬
자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.
앞서 말한 버블 정렬, 삽입정렬, 선택정렬에 비해 속도가 빠르다는 장점이 있음.
분할 단계
1단계 : 8, 1, 4, 3, 2, 5, 10, 6
2단계 : 8, 1, 4, 3 2, 5, 10, 6
3단계 : 8, 1 4, 3 2, 5 10, 6
4단계 : 8 1 4 3 2 5 10 6
병합 단계
1단계 : 8 1 4 3 2 5 10 6
그냥 병합하는 것이 아닌 각 숫자의 크고 작음을 비교해서 병합한다.
2단계 : 1, 8 3, 4 2, 5 6, 10
3단계 : 1, 3, 4, 8 2, 5, 6, 10
4단계 : 1, 2, 3, 4, 5, 6, 8, 10
반복수행하는 부분이 있기 때문에 재귀함수를 쓴다.
def mSort(ns):
#분할단계
#갯수가 2보다 작을때까지 쪼갠다
if len(ns)<2:
return ns
midIdx = len(ns) // 2
leftNums = mSort(ns[0:midIdx])
rightNums = mSort(ns[midIdx:len(ns)])
#병합단계
mergeNums = []
leftIdx = 0; rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
#자리바꿈
if leftNums[leftIdx] < rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
mergeNums = mergeNums + leftNums[leftIdx:]
mergeNums = mergeNums + rightNums[rightIdx:]
return mergeNums
nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(mSort(nums))
2. 퀵정렬
기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
1단계 : 8, 1, 4, 3, 2, 5, 4, 10, 6, 8 ---기준값5
2단계 : 1, 4, 3, 2, 4 5 8, 10, 6, 8 ---기준값 3, 6
3단계 : 1, 2 3, 4, 4 5 6 8, 8, 10 ---기준값 4, 8
4단계 : 1, 2 3, 4, 4 5 6 8, 8, 10
def qSort(ns):
if len(ns)<2:
return ns
midIdx = len(ns)//2
midVal = ns[midIdx]
smallNums = []; sameNums = []; bigNums = []
for n in ns:
if n < midVal:
smallNums.append(n)
elif n == midVal:
sameNums.append(n)
else:
bigNums.append(n)
return qSort(smallNums) + sameNums +qSort(bigNums)
nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(qSort(nums))
sameNums 이외의 것들은 다시 qSort를 돌려서 얻어낸다.
'코딩 > 알고리즘' 카테고리의 다른 글
재귀 알고리즘, 하노이의 탑 (0) | 2023.02.09 |
---|---|
[비교] 최빈값, 근삿값, 평균 알고리즘 (0) | 2023.02.08 |
[비교] 최댓값, 최솟값 알고리즘 (0) | 2023.02.06 |
[정렬] 선택정렬 알고리즘 (0) | 2023.01.31 |
[정렬] 삽입정렬 알고리즘 (0) | 2023.01.31 |