2021년03월07일 37번
[소프트웨어 개발] 퀵 정렬에 관한 설명으로 옳은 것은?
- ① 레코드의 키 값을 분석하여 같은 값끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬한다.
- ② 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환한다.
- ③ 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬한다.
- ④ 임의의 레코드 키와 매개변수(h)값만큼 떨어진 곳의 레코드 키를 비교하여 서로 교환해 가면서 정렬한다.
(정답률: 53%)
문제 해설
연도별
진행 상황
0 오답
0 정답
퀵 정렬은 분할 정복 알고리즘의 하나로, 주어진 배열을 두 개의 부분 배열로 분할하고 각 부분 배열을 재귀적으로 정렬하는 방식으로 동작한다. 이 때, 퀵 정렬은 pivot 값을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할하며, 이 과정에서 레코드의 이동이 발생한다.
하지만, 퀵 정렬은 pivot 값을 잘 선택하지 못하면 최악의 경우 O(n^2)의 시간 복잡도를 가지게 된다. 따라서, 퀵 정렬에서는 pivot 값을 잘 선택하는 것이 중요하며, 이를 위해 다양한 방법들이 제안되고 있다.
또한, 퀵 정렬은 대부분의 경우에 다른 정렬 알고리즘보다 빠르게 동작하며, 특히 대용량 데이터를 정렬할 때 유용하다.