[ALGORITHM] 정렬

정렬

• 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
• 정렬은 프로그램 작성시 빈번하게 필요
• 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수 

---

버블정렬 (Bubble sort)

https://en.wikipedia.org/wiki/Bubble_sort

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

---

선택정렬 (Selection sort)

https://en.wikipedia.org/wiki/Merge_sort

• 주어진 데이터 중, 최소값을 찾은뒤 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함, 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복하는 정렬 알고리즘

---

삽입정렬 (Insertion sort)

https://en.wikipedia.org/wiki/Insertion_sort

• 두번째 인덱스부터 시작하여, 해당 인덱스 앞에 있는 데이터(B) 부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스를 복사함, 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

---

병합정렬 (Merge sort)

https://en.wikipedia.org/wiki/Merge_sort

• 재귀용법을 활용한 정렬 알고리즘
• 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈 뒤 각 부분 리스트를 재귀적으로 합병하여 정렬을 반복하여 다시 하나의 정렬 리스트로 만듬

---

퀵정렬 (Quick sort)

https://en.wikipedia.org/wiki/Quicksort

• 기준점 (Pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 것을 반복하여 정렬
• 왼쪽 + 기준점 + 오른쪽

---

자바 정렬 함수

	Primitive 원소 정렬	Object 원소 정렬
정렬방식	Dual-Pivot Quick Sort	Tim Sort (선택정렬 / 합병정렬 합침)
최선 시간복잡도	O(N)	O(N)
최악 시간복잡도	O(N2)	O(NlogN)
평균 시간복잡도	O(NlogN)	O(NlogN)

• 자바 Arrays.sort 함수는 Primitive 타입 정렬할때랑 Object 정렬할때 사용하는 정렬 알고리즘이 다름