정렬이란 주어진 데이터를 크기 순서대로 또는 일정한 기준에 따라 정리하는 것을 말한다. 정렬은 데이터를 검색하거나 비교할 때 효율적으로 처리하기 위해 필요하다.

선택 정렬

선택 정렬은 주어진 리스트에서 가장 작은 값을 찾아서 맨 앞의 위치와 교환하고, 그 다음 작은 값을 찾아서 두 번째 위치와 교환하는 과정을 반복하여 정렬을 완성하는 알고리즘이다.

선택 정렬은 구현이 간단하며, 정렬이 필요한 데이터 수가 적을 때는 효율적인 알고리즘이지만, 데이터 수가 많아질수록 성능이 떨어진다.

선택 정렬의 시간 복잡도는 $O(n^2)$이다.

선택 정렬의 과정

1. 주어진 리스트에서 가장 작은 값을 찾는다.
2. 가장 작은 값과 맨 앞의 값을 교환한다.
3. 리스트의 남은 값들 중 가장 작은 값을 찾아서 두 번째 위치와 교환한다.
4. 2-3번 과정을 리스트의 마지막 값까지 반복한다.

선택 정렬의 장단점

장점

• 구현하기 쉽다.
• 정렬이 필요한 데이터 수가 적을 때는 효율적인 알고리즘이다.

단점

• 데이터 수가 많아질수록 성능이 떨어진다.
• 시간 복잡도는 $O(n^2)$으로, 대규모 데이터에서는 느리다.
• 안정성이 보장되지 않는다.

버블 정렬