[삽입 정렬] & [퀵 정렬] & [병합 정렬] & [기수 정렬]

 

삽입 정렬이란?

이미 정렬된 데이터 범위에서 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다.

시간복잡도도 O(㎡)로 느린 편이지만 구현하기 쉽다!

선택 데이터는 현재 정렬된 데이터 범위내에서 정확한 위치에 삽입하는 것이 중요하다.

 

 

 

퀵 정렬이란?

기준값(피벗)을 선정해 해당 값보다는 작은 데이터와 큰 데이터로 분류하는 것을 반족해 정렬하는 방식이다.

기준값에 따라 시간 복잡도에 많은 영향을 미치고 평균 시간 복잡도(O(nlogn))이며 최악의 경우에는 시간 복잡도가 O(㎡)! -> 시간복잡도가 불규칙하며 운이 따르는 알고리즘임 ㅜ.ㅜ

따라서 피벗을 설정하는 것이 가장 중요하며 투 포인터(start, end)를 설정하여 피벗과 비교하며 정렬한다.

오름차순으로 정렬

 

42 32 24 60 15 5 90 45   -> pivot: 45, start : 42, end: 90, 피벗은 무조건 오른쪽 값으로 설정한 상태.

42 32 24 60 15 5 90 45   -> pivot: :45, start: 32, end: 5, end<pivot 이므로 end는 stop

42 32 24 60 15 5 90 45

42 32 24 60 15 5 90 45   ->  60이 처음으로 피벗보다 큰 수이므로 60과 5 swap

42 32 24 5 15 60 90 45   ->  start와 end가 만나는 지점인 15와 피벗 비교, -> 피벗이 더 큼

42 32 24 5 15 45 60 90   ->  피벗 중심으로 왼쪽은 45 보다 작고, 오른쪽은 45 보다 큼. 15가 기준이 됨.

42 32 24 5 15 45 60 90   ->  pivot: 15 & 90, start : 42, end: 5 , start>end -> swap, 60과 90 비교

5 32 24 42 15 45 60 90   ->  pivot: 15, start : 32, end: 24, end>pivot -> end이동 -> start 지점과 만남

5 15 24 42 32 45 60 90   ->  32와 15 비교 -> swap

5 15 24 42 32 45 60 90   -> pivot: :32, start: 24, end: 42

5 15 24 32 42 45 60 90

전혀 퀵하지 않은,,,, 

 

 

병합 정렬이란? -> 활용하면 정말 좋은 알고리

분합 정복 방식(데이터를 나)을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다.

시간복잡도는 O(nlogn)이다.

2개의그룹을 병합하는 과정

투 포인터 개념을 사용해 왼쪽,오른쪽 그룹을 병합한다.

(나눈 두 그룹은 현재 정렬된 상태라고 가정)

 

24 32 42 60 5 15 45 90   -> 24와 5 비교 -> 5 

24 32 42 60 5 15 45 90   -> 24와 15 비교 -> 5 15

24 32 42 60 5 15 45 90   -> 24와 45 비교 -> 5 15 24

24 32 42 60 5 15 45 90   -> 32와 45 비교 -> 5 15 24 32

24 32 42 60 5 15 45 90   -> 42와 45 비교 -> 5 15 24 32 42

24 32 42 60 5 15 45 90   -> 60와 45 비교 -> 5 15 24 32 42 45

24 32 42 60 5 15 45 90   -> 60와 90 비교 -> 5 15 24 32 42 45 60

남은 90은 그냥 써주기, 최종 정렬된 배열 -> 5 15 24 32 42 45 60 90

 

기 정렬이란?

비교할 자릿수를 정한 후 자릿수만 비교하는 특이한 정렬이다.

시간복잡도도 O(kn)로 k는자릿수를 말한다,

기수 정렬은 10개의 큐(0~9)를 이용한다. 각 큐는 값의 자릿수를 뜻한다. 

난이도는 있지만  시간복잡도가 좋아서 활용해보면 좋음!