정렬

: 흩어져 있는 데이터를 키 값을 이용하여 순서대로 열거하는 알고리즘

삽입 정렬 O(n)~O(n^2)

맨 앞부터 비교해서 오른쪽으로 비교하려는 값으로 이동
비교하려는 값을 기준으로 왼쪽에 있는 값들을 비교하여 적절한 위치에 삽입
비교하려는 값보다 큰 값들은 뒤로 밀림

버블 정렬 O(n^2)

첫째값 vs 둘째값 -> 스왑
스왑된 리스트에서 둘째값 vs 셋째값 -> 스왑
해당 내용을 리스트 마지막 원소까지 반복하면 1회전.
더 이상 정렬할게 없을때까지 위의 내용 반복

선택 정렬 O(n^2)

리스트 첫번째 위치의 값과 두번째 값을 비교하고 스왑
스왑된 리스트에서 첫번째위치와 세번째값을 비교하고 스왑
이렇게 첫번째 위치와 마지막위치가 값을 비교하고 스왑하면 1회전.
더 이상 정렬할게 없을때까지 위의 내용 반복

합병 정렬 Merge O(nlogn)

분할 정복 알고리즘 기반
배열의 원소가 1개 밖에 남지 않을때까지 반으로 쪼개서 재배열하여 원래 크기로 합침

퀵 정렬 ~o(n^2)

분할 정복 알고리즘 기반
매우 빠른 속도

• 하나의 피벗 테이블을 기준으로 두개의 비균등한 크기로 분할하고 분할된 리스트 정렬 후 부분 리스트 합침

합병정렬 VS 퀵 정렬

기준	퀵	합병
부분 배열	여러 비율로	항상 반으로
최악 시간복잡도	O(n^2)	O(nlogn)
사용용도	작은 크기 배열	어느 DB든 적절히 사용
정렬방식	내부	외부
별도저장공간	X	O

예시 : 삽입 vs 버블 vs 선택

{8,5,6,2,4}

• 삽입

회전수	정렬결과	설명
초기	8 5 6 2 4
1회전	5 8 6 2 4	첫번째값(8) vs 두번째값(5) 비교하여 5를 8 앞에 삽입
2회전	5 6 8 2 4	1,2번째값(5,6) vs 세번째값(6) 비교하여 1,2번째 사이에 6 삽입
3회전	2 5 6 8 4	1,2,3번째값(5,6,8) vs 네번째값(2) 비교하여 맨 앞에 2 삽입
4회전	2 4 5 6 8	1,2,3,4번째값(2,5,6,8) vs 다섯번째값(4) 비교하여 1,2,번째 사이에 4 삽입

최종 : 2 4 5 6 8 (4회전 검색)

• 버블

회전수	정렬결과	설명
초기	8 5 6 2 4
1회전	5 8 6 2 4	첫번째(8) vs 두번째(5) 비교하고 스왑
	5 6 8 2 4	두번째(8) vs 세번째(6) 비교하고 스왑
	5 6 2 8 4	세번째(8) vs 네번째(2) 비교하고 스왑
	5 6 2 4 8	네번째(8) vs 다섯번째(4) 비교하고 스왑
2회전	5 6 2 4 8	첫번째(5) vs 두번째(6) 비교하고 스왑
	5 2 6 4 8	두번째(6) vs 세번째(2) 비교하고 스왑
	5 2 4 6 8	세번째(6) vs 네번째(4) 비교하고 스왑
	5 2 4 6 8	네번째(6) vs 다섯번째(8) 비교하고 스왑
3회전	2 5 4 6 8	첫번째(5) vs 두번째(2) 비교하고 스왑
	2 4 5 6 8	두번째(5) vs 세번째(4) 비교하고 스왑
	...	...
4회전	2 4 5 6 8	종료

최종 : 2 4 5 6 8 (4회전 검색)

• 선택

회전수	정렬결과	설명
초기	8 5 6 2 4
1회전	5 8 6 2 4	첫번째(8) vs 두번째(5) 비교하고 스왑
	5 8 6 2 4	첫번째(5) vs 세번째(6) 비교하고 스왑
	2 8 6 5 4	첫번째(5) vs 네번째(2) 비교하고 스왑
	2 8 6 5 4	첫번째(2) vs 다섯번째(4) 비교하고 스왑
2회전	2 6 8 5 4	두번째(8) vs 세번째(6) 비교하고 스왑
	2 5 8 6 4	두번째(6) vs 네번째(5) 비교하고 스왑
	2 4 8 6 5	두번째(5) vs 다섯번째(4) 비교하고 스왑
3회전	2 4 6 8 5	세번째(8) vs 네번째(6) 비교하고 스왑
	2 4 5 8 6	세번째(6) vs 다섯번째(5) 비교하고 스왑
4회전	2 4 5 6 8	네번째(8) vs 다섯번째(6) 비교하고 스왑

최종 : 2 4 5 6 8 (4회전 검색)