알고리즘- 선택정렬과 삽입정렬의 개념을 설명하고 두 가지 중 더 활용도가 높은 정렬 알고리즘이 무엇인지 학습자 본인의 의견을 토대로 서술해보시오 – 2025 | 파일첨부

–

선택정렬(Selection Sort)은 정렬되지 않은 리스트에서 가장 작은(또는 가장 큰) 요소를 찾아 맨 앞의 요소와 교환하는 과정을 반복하여 전체를 정렬하는 알고리즘이다. 즉, 첫 번째 루프에서는 리스트 전체에서 가장 작은 값을 찾아 첫 번째 자리와 바꾸고, 두 번째 루프에서는 두 번째 이후의 리스트에서 가장 작은 값을 찾아 두 번째 자리와 바꾸는 식으로 진행된다.

이 알고리즘의 가장 큰 특징은 교환 횟수가 적다는 것이다. 각 루프마다 한 번의 교환만 수행되기 때문에, 교환 비용이 높은 경우에는 유리할 수 있다. 그러나 그에 반해 비교 횟수는 상당히 많아, 전체적으로 효율이 낮은 편이다. 시간복잡도는 최선, 평균, 최악 모두 O(n²)이다.

선택정렬은 구현이 간단하고, 추가적인 메모리를 사용하지 않는(in-place) 정렬이라는 장점이 있지만, 입력 데이터가 이미 정렬되어 있어도 항상 동일한 비교 횟수를 가지므로 비효율적이다.

2. 삽입정렬의 개념과