Sorting

Merge sort

 

A. concept

: 두 sorted list를 합친다. 각각 리스트의 맨첨 애를 비교해서 작은 애를 새로운 리스트에 넣는 방식

-> 리스트를 1개 될때까지 다 절반으로 divide 한 담에 차례로 merge 합니다

처음에는 sorted안되어있으니까 다 1개인걸로 쪼개놓으면 sorted니까 쪼개서 합치는 것!!

 

B. Code

 

 

C. Analysis

: O(nlogn) !! - (worst average 둘다)

T(1)=1, T(n)=2T(n/2)+n 

알고리즘 정리한거 참고

---

Quick Sort

= 분할 정복  divide-and conquer 알고리즘. (그대로 해결할 수 없는 문제를 작은문제로 분할하여 문제 해결함)

1. 피벗 하나를 정해서 앞에는 피벗보다 작은걸 배치, 뒤에는 피벗보다 큰걸 배치 (Partition 작업)

2. 피벗 앞부분에 대해 quicksort (재귀)

3. 피벗 뒷부분에 대해 quicksort

 

Partition 알고리즘

각 배열에서 양끝에서 움직임

오른쪽- 큰애들, 왼쪽-작은애들

이때 최대한 간 담에 왼쪽에 큰거, 오른쪽에 작은거가오면 두개 교환!

그리구 다햇으면 small+1과 pivot을 swap!

 

Code

 

---

Heapsort

: heap으로 만들어서 root하나씩 빼서 정렬하는 것

https://juny02.tistory.com/63?category=895499 

Heapsort

복잡도 : O(nlogn) 

( worst, average 둘다 )

---

Radix sort

radix = 주어진 데이터를 구성하는 기본 요소의 개수. 10진수는 10이 radix 머 이런거?

쨋든

radix sort -> 자릿수 비교해서 하는거

1. 가장 낮은자리수 비교해서 정렬

2. 점점 자릿수 올라가면서 비교해서 정렬 끗

아래자릿수부터 비교한거 (같은자릿수를 같은 칸에 넣음..;;)

Code

아직못함 쏘리 ㅠㅠ