선택 정렬(Selection Sort)은 가장 작은(또는 가장 큰) 값을 찾아서 정렬되지 않은 부분의 첫 번째 원소와 교환하는 과정을 반복하여 정렬하는 알고리즘입니다.
선택 정렬은 선택 정렬 알고리즘이 수행될 때마다, 정렬되지 않은 부분에서 가장 작은(또는 큰) 값을 선택하고, 그 값을 정렬되지 않은 부분의 첫 번째 원소와 교환합니다. 이를 정렬되지 않은 부분이 없을 때까지 반복합니다. 선택 정렬 알고리즘은 단순하고 이해하기 쉬우며, 정렬이 이루어지는 과정에서 추가적인 메모리를 필요로 하지 않는 것이 장점입니다. 그러나, 삽입 정렬의 시간 복잡도는 **최선의 경우와 최악의 경우 모두 O(n^2)**입니다.
Q : 선택 정렬과 삽입정렬이 유사하다고 생각되는데 어떻게 생각해?
A : 네, 선택 정렬과 삽입 정렬은 둘 다 제자리 정렬(in-place sorting) 알고리즘으로서 입력된 리스트 내에서 정렬이 수행된다는 공통점이 있습니다. 또한 두 알고리즘 모두 비교 기반의 정렬 알고리즘이며, 정렬된 부분 리스트와 정렬되지 않은 부분 리스트를 유지하면서 진행됩니다.
A : 하지만 두 알고리즘의 핵심적인 차이점은 "비교 과정"에서 발생합니다. 선택 정렬은 주어진 리스트에서 최솟값을 찾아서 해당 값을 맨 앞에 있는 값과 교체하는 방식으로 정렬을 수행합니다. 반면 삽입 정렬은 정렬되지 않은 부분 리스트에서 하나씩 원소를 선택하여 이미 정렬된 부분 리스트의 적절한 위치에 삽입하는 방식으로 정렬을 수행합니다.
삽입 정렬 : 정렬 되지 않은 리스트에서 무작위 값을 가져와 적절한 위치에 배치함
선택 정렬 : 정렬 되지 않은 리스트에서 최솟값을 가져와 정해진 위치에 배치함