Sort

Insertion Sort (삽입 정렬)

• 이미 정렬된 파일에 새로운 데이터를 순서에 맞게 삽입시켜 정렬하는 방식으로 두 번째 값부터 시작해 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘
• 구현이 간단하고 쉬우며 작은 크기의 배열에 효과적이다.
• 최선의 경우 O(n)의 성능을 가지지만, 평균적으로는 O(n^2)의 시간 복잡도를 가진다.

Bubble Sort (버블 정렬)

• 버블 정렬는 서로 인접한 두 원소를 비교, 교환하여 정렬하는 알고리즘
• 작은 규모의 배열에서 빠른 성능을 보이지만 배열이 이미 정렬되어 있는 경우에도 모든 요소를 비교하므로 성능이 떨어진다.
• 평균적으로 O(n^2)의 시간 복잡도를 가진다.

Merge Sort (병합 정렬)

• 주어진 리스트를 절반으로 나누고 각각 정렬한 후 두개의 정렬된 리스트를 병합하여 정렬하는 알고리즘
• 즉, Divide and Conquer 알고리즘을 사용하여 동작
• 안정적인 정렬 알고리즘으로 모든 경우에 일관된 성능을 보이며 대규모 배열에 대해서도 효과적이다
• 추가적인 메모리 공간이 필요하다
• 평균 및 최악의 경우에도 O(n log n)의 시간 복잡도를 가진다.

Quick Sort (퀵 정렬)

• 주어진 리스트에서 기준 원소를 선택(pivot)하고 원소보다 작으면 왼쪽으로 크면 오른쪽으로 분할하여 정렬하는 알고리즘
• Divide and Conquer 알고리즘을 사용하여 동작
• 평균적으로 빠른 성능을 보이는 정렬 알고리즘이지만 피벗 선택에 따라 성능이 달라질 수 있다.
• 추가적인 메모리 공간이 필요 없다.
• 최악의 경우에는 O(n^2), 평균적으로는 O(n log n)의 시간 복잡도를 가진다.