[Programming] 정렬(힙 정렬 제외 오름차순 정렬 기준)

[속도느림/ 구현단순]

1. 선택정렬 : 0부터 n번째 자리에 순서대로 최솟값을 찾아 앞에 배치

2. 삽입정렬 : 배열의 두번째 index부터 시작하여 앞 index값과 비교해 더 작은 수일 경우 지속적으로 swap하여 앞으로 끌어오는 정렬

3. 버블정렬 : 배열([0,1], [1,2], [2,3])앞뒤 두 index를 비교하며 swap

[속도빠름/ 구현복잡]

1. 합병정렬 : 배열 중앙기준 지속적으로 반으로 나눈 후 새로운 배열을 할당한 뒤 기존 나뉜 쌍으로 부분배열의 값 중 작은값을 채워넣는 방식

2. 셀 정렬 : 배열길이/2 만큼의 간격을 늘리고 간격수만큼 배열을 나눈뒤 각 배열을 삽입정렬한다. 이후 기존 간격/2하여 동일하게 반복

3. 퀵 정렬 : 분할, 정복, 결합 3단계로 나뉜다. 0 index를 pivot 으로 두고 pivot 왼쪽 (pivot 보다 작은 수의 배열), pivot 오른쪽 (pivot 보다 큰 수의 배열)으로 2개의 부분배열로 분할한 뒤 각 부분배열을 정렬한다. 부분 배열의 크기가 작지 않다면 순환 호출을 이용하여 다시 분할하여 정렬(정복) 한다. 각 부분 배열들의 정렬이 완료되면 결합한다.

 

4. 힙정렬(내림차순) : 이진트리의 일종으로 부모노드는 index/2, 왼쪽 자식은 index*2, 오른쪽자식은 index*2+1로 정렬, 
삽입) 마지막 index에 새로운 값을 삽입 한뒤 index/2(홀수일경우 나머지 버리기)한 부모노드를 찾아 비교하여 swap
최대힙삭제) 최대힙(루트노드)삭제 후 힙의 마지막 노드를 루트로 가져온뒤 힙 정렬을 다시 한다.

 

 

참고사이트

https://m.blog.naver.com/jsky10503/221249976761

https://sylagape1231.tistory.com/17

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

https://imgur.com/3sUWVY2