정렬 알고리즘에 대해서 아는대로 설명해주세요.

정렬 알고리즘은 주어진 데이터를 특정한 기준에 따라 순서대로 나열하는 알고리즘입니다. 다양한 정렬 알고리즘이 존재하며, 각각의 알고리즘은 자체적인 특징과 성능 특성을 가지고 있습니다. 아래는 몇 가지 대표적인 정렬 알고리즘에 대한 설명입니다.

1. 버블 정렬 (Bubble Sort):
   • 서로 인접한 두 원소를 비교하여 순서에 맞지 않은 경우 교환하는 방식으로 동작합니다.
   • Pass를 반복하면서 가장 큰 원소가 마지막으로 이동합니다.
   • 시간 복잡도: O(n^2)
   • 장점: 구현이 간단하다.
   • 단점: 성능이 좋지 않으며, 대부분의 상황에서는 비효율적입니다.
2. 선택 정렬 (Selection Sort):
   • 주어진 리스트에서 최솟값을 찾아 맨 앞의 원소와 교환하는 방식으로 동작합니다.
   • 정렬된 부분과 정렬되지 않은 부분으로 나누어진다.
   • 시간 복잡도: O(n^2)
   • 장점: 추가 메모리가 필요하지 않다.
   • 단점: 느린 속도, 비효율적인 알고리즘.
3. 삽입 정렬 (Insertion Sort):
   • 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분에 삽입합니다.
   • 시간 복잡도: O(n^2)
   • 장점: 작은 규모의 데이터나 이미 정렬된 데이터에 대해 효과적이다.
   • 단점: 대량의 데이터에 대해서는 비효율적이다.
4. 병합 정렬 (Merge Sort):
   • 분할 정복(divide and conquer) 방법을 사용하여 리스트를 반으로 나눈 후, 각 부분을 정렬하고 병합하는 방식으로 동작합니다.
   • 시간 복잡도: O(n log n)
   • 장점: 안정적이고 대규모 데이터에도 효과적이다.
   • 단점: 추가 메모리가 필요하다.
5. 퀵 정렬 (Quick Sort):
   • Pivot을 선택하고 Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 정렬하는 방식으로 동작합니다.
   • 시간 복잡도: O(n log n) - 평균, O(n^2) - 최악
   • 장점: 평균적으로 빠르고 추가 메모리가 적게 필요하다.
   • 단점: 최악의 경우에는 성능이 나빠질 수 있다.
6. 힙 정렬 (Heap Sort):
   • 최대 힙 또는 최소 힙을 구성하여 데이터를 정렬하는 방식으로 동작합니다.
   • 힙을 구성하는 과정과 힙에서 최대(또는 최소) 값을 추출하여 정렬하는 과정으로 이루어집니다.
   • 시간 복잡도: O(n log n)
   • 장점: 추가 메모리가 필요하지 않고, 불안정 정렬에서 안정적인 정렬로 변환 가능하다.
   • 단점: 상대적으로 구현이 복잡하다.