Summary

• slow(good for small inputs) | | Insertion Sort | $O(n^2)$ | Yes | Yes | * in-place
• slow(good for small inputs) | | Selection Sort | $O(n^2)$ | No | Yes | * in-place
• slow(good for small inputs) | | Merge Sort | $O(nlogn)$ | Yes | No | * sequential data access
• fast (good for huge inputs) | | Quick Sort | $O(nlogn)$ | No or Yes | Yes or No | * in-place, randomized
• fastest (good for large inputs) |

In-Place

추가적인 메모리 사용량이 입력 데이터의 크기에 상관없이 일정하게 유지되는 특성 → 입력 배열 내부에서 요소들의 위치를 직접 교환(swap)하는 방식으로 정렬이 이루어짐.

Stable

정렬 과정에서 동일한 값들의 상대적인 순서가 유지되는지? → 입력에 동일한 값을 가진 레코드가 여러 개 있을 경우, 그 레코드들이 정렬 후에도 원래의 순서를 유지해야함.

• Bubble Sort : 인접한 두 원소를 비교하여 정렬하는 방식으로, 동일한 값에 대해서는 원래 순서가 유지됨.

  → Stable

• Insertion Sort : 각 반복에서 원소를 적절한 위치에 삽입하는 방식, 동일한 값의 원소들 사이의 순서가 변경되지 않음.

  → Stable

• Selection Sort : 주어진 배열에서 최솟값(or 최댓값)을 찾은 후, 그 값을 배열의 맨 앞(or 맨 뒤)와 교환하는 방식으로 배열의 모든 요소에 대해 반복하는데, 이 과정에서 동일한 값을 가진 요소의 상대적 순서가 변경될 수 있음.

  → Non-Stable

• Merge Sort : 분할 정복 알고리즘을 사용하여 정렬하며, 동일한 값을 가진 원소들의 상대적 순서가 유지됨.

  → Stable

• Quick Sort : 분할 정복 알고리즘을 사용하지만, 분할 과정에서 동일한 값의 원소들이 원래 순서를 유지하지 못할 수 있음.

  → Non-Stable