정렬

정렬 알고리즘은 Comparisons방식과 Non-Comparisons방식으로 나눌 수 있다.

Comparisons방식은 비교 방식으로 종류는 다음과 같다.

• 버블 정렬(Bubble Sort)
• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort)
• 합병 정렬(Merge Sort)
• 힙 정렬(Heap Sort)
• 퀵 정렬(Quick Sort)

Non-Comparisons방식의 종류는 다음과 같다.

• 계수 정렬(Counting Sort)
• 기수 정렬(Radix Sort)

버블 정렬

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 ➡️ O(n²)

• 장점
  • 구현이 간단함
• 단점
  • 하나의 요소가 한쪽 끝에서 다른 끝으로 이동하기 위해서 배열에서 모든 다른 요소들과 교환되어야 함
  • 교환(swap)이 많이 일어난다