Big-O가 알고리즘을 완벽하게 설명하는 건 아니다
각각 알고리즘은 Big-O를 가지고 있지만 각각 퍼포먼스는 다르다

Sorting

n 개의 숫자가 있을때 기준에 따라 순서대로 정렬하는 것

1. Buble Sort 버블정렬
2. Selection Sort 선택정렬
3. Insertion Sort 삽입정렬
4. Merge Sort 병합 정렬
5. Quick Sort 퀵 정렬
6. Heap sort 힙 정렬

1. Buble Sort 버블정렬

• 2개 숫자를 비교해서 왼쪽값 > 오른쪽값 이면 서로 교환하기
• 자주 사용하지 않는다. 좋은 알고리즘은 아니다
• O(n²)

  ex) 52631 순서대로 정렬하기
  2가지를 비교 후 왼쪽값 > 오른쪽값 이면 Swaps서로 교환하기
  계속 비교해서 교환하기를 거친다

2. Selection Sort 선택정렬

• 가장 작은 숫자를 변수에 저장했다가 1번째와 바꾸기
• 버블정렬과 다르게 n번 정렬안함. 매 싸이클마다 1번의 스왑만 함
• O(n²)

  ex) 52631 순서대로 정렬하기
  가장 작은 숫자의 위치를 변수에 저장한다
  가장 작은 숫자와 1번째 아이템 스왑
  정렬된 1제외하고 계속 진행
  적은 숫자찾고 1번째와 스왑하기

3. Insertion Sort 삽입정렬

• index [1]부터 시작해서 2개 서로 비교하여 큰 수를 오른쪽으로 옮기기
• 선택정렬보다 빠르다
• 필요한 아이템만 스캔한다
• 최악 O(n²) / 최고 O(n)

버블/선택/삽입 3가지 종류의 알고리즘이 각각 다른데 시간복잡도는 동일하다
그럴 때에는 최악의 시나리오 말고 평균 시나리오를 봐야한다.

4. Merge Sort 병합 정렬

• 분할정복(Divide and Conquer)
• Divide(분할) : 배열을 작은배열 2개로 나눈다.
  Conquer(정복) : 각각의 작은 배열들을 정렬한다.
  Combine(병합) : 정렬된 작은 배열들을 병합한다.
• O(nlogn)

5. Quick Sort 퀵 정렬

• 분할정복(Divide and Conquer)

1. 배열에서 한 축(pivot 피벗)을 선택한다.
2. 축을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 옮긴다.
3. 축을 제외한 왼쪽, 오른쪽 리스트를 다시 정렬한다.
   3-1) 분할된 왼쪽, 오른쪽 리스트에서 다시 pivot을 기준으로 2개로 나눈다.
   3-2) 재귀를 사용하여 부분 리스트들이 분할이 불가능할 때까지 반복한다.

6. Heap sort 힙 정렬

• 이진트리 기반으로 최대 힙 트리(내림차순)나 최소 힙 트리(오름차순)를 구성해 정렬한다
• O(nlogn)

Heap 힙 자료구조

• 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.
• 최댓값과 최솟값을 빠르게 찾을 수 있는 자료구조
  최대 힙 트리 : (부모노드의 키 값 >= 자식노드의 키 값)인 완전 이진 트리
  최소 힙 트리 : (부모노드의 키 값 <= 자식노드의 키 값)인 완전 이진 트리
  

정렬 시간복잡도 Time Complexity

알고리즘	평균 Avg	최선 Best	최악 Worst
버블 정렬	O(n²)	O(n²)	O(n²)
선택 정렬	O(n²)	O(n²)	O(n²)
삽입 정렬	O(n²)	O(n)	O(n²)
병합 정렬	O(nlogn)	O(nlogn)	O(nlogn)
퀵 정렬	O(nlogn)	O(nlogn)	O(n²)
힙 정렬	O(nlogn)	O(nlogn)	O(nlogn)
셸 정렬	O(n^1.5)	O(n)	O(n²)

참고

Sorting Algorithms Animations
https://hyos-inside.tistory.com/11
https://roytravel.tistory.com/37
https://code-lab1.tistory.com/24