정렬의 종류에는 어떤 것들이 있나요?
-
버블 정렬 (Bubble Sort)
: 이웃한 두 원소를 비교하여 조건에 맞지 않는 경우 서로 교환하는 방식으로 동작합니다.
최선, 평균, 최악: (O(n^2)) -
선택 정렬 (Selection Sort)
: 리스트에서 가장 작은 원소를 찾아 첫 번째 위치와 교환하고, 그 다음으로 작은 원소를 두 번째 위치와 교환하는 방식입니다.
최선, 평균, 최악 (O(n^2)) -
삽입 정렬 (Insertion Sort)
: 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분에서 하나씩 원소를 선택하여 적절한 위치에 삽입하는 방식입니다.
최선 O(n), 평균, 최악 : O(n^2) -
병합 정렬 (Merge Sort)
: 리스트를 반으로 나눈 뒤 각각을 정렬하고, 정렬된 두 개의 리스트를 합쳐 전체 리스트를 정렬하는 방식입니다.
최선, 평균, 최악: O(n log n) -
퀵 정렬 (Quick Sort)
: 기준 원소를 선택한 뒤, 기준보다 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 분할하여 정렬하는 방식입니다.
최선: O(n log n), 평균, 최악: O(n^2) -
힙 정렬 (Heap Sort)
: 최대 힙을 구성한 뒤, 최대값을 루트로 이동시키고 힙을 다시 구성하여 정렬하는 방식입니다.
최선, 평균, 최악: O(n log n) -
기수 정렬 (Radix Sort)
: 정렬할 데이터를 자리수 별로 비교하여 정렬하는 방식으로, 주로 숫자를 정렬할 때 사용됩니다.
최선, 평균, 최악: O(d * (n + k))
n은 정렬할 요소의 수
k는 각 요소의 범위 (예: 0부터 9까지의 숫자인 경우 k=10)
d는 정렬할 요소의 자릿수입니다.
- 계수 정렬 (Counting Sort)
: 정수의 개수를 세어 정렬하는 비교 기반 정렬이 아닌 정수 정렬 알고리즘입니다.
최선, 평균, 최악: O(n + k)
n은 정렬할 요소의 수
k는 각 요소의 범위 (예: 0부터 9까지의 숫자인 경우 k=10)
삽입 정렬이 일어나는 과정을 설명해 보세요.
-
리스트의 첫 번째 원소는 이미 정렬된 상태로 간주됩니다.
-
두 번째 원소부터 시작합니다. 이를 현재 원소라고 부릅니다.
현재 원소를 정렬된 부분의 적절한 위치에 삽입하기 위해, 정렬된 부분을 오른쪽으로 이동하면서 현재 원소와 비교합니다.
정렬된 부분에서 현재 원소보다 큰 원소를 만나면, 그 위치에 현재 원소를 삽입합니다. -
이제 세 번째 원소를 현재 원소로 선택하고, 정렬된 부분에 삽입해야 합니다.
현재 원소를 정렬된 부분에서 적절한 위치에 삽입합니다.
계속 진행: 이 과정을 리스트의 끝까지 반복합니다.
매 단계에서 현재 원소를 적절한 위치에 삽입합니다.
정렬 완료: 모든 원소가 정렬된 상태로 나열됩니다.
ex) [5, 2, 4, 6, 1, 3] 이라는 리스트를 삽입 정렬한다고 가정해봅시다.
초기 상태: [5] (첫 번째 원소는 이미 정렬된 상태입니다.)
두 번째 단계: [2, 5]
세 번째 단계: [2, 4, 5]
네 번째 단계: [2, 4, 5, 6]
다섯 번째 단계: [1, 2, 4, 5, 6]
여섯 번째 단계: [1, 2, 3, 4, 5, 6]
이런 식으로 원소를 하나씩 적절한 위치에 삽입하면서 리스트가 정렬됩니다.
퀵 정렬이 일어나는 과정을 설명해 보세요.
- 피벗 선택
:리스트에서 하나의 원소를 선택하여 이를 피벗(pivot)으로 지정합니다. 피
벗의 선택은 리스트의 어느 위치나 원소로 선택할 수 있지만,
보통은 리스트의 중간값을 선택하는 경우가 많습니다. - 분할 (Partitioning)
: 피벗을 기준으로 리스트를 두 개의 부분 리스트로 나눕니다.
피벗보다 작은 원소들은 피벗의 왼쪽에 위치하고, 큰 원소들은 오른쪽에 위치하게 됩니다. 이
과정을 통해 피벗은 최종적으로 자신의 위치를 찾게 됩니다. - 재귀적으로 반복
: 피벗을 기준으로 나뉜 두 개의 부분 리스트에 대해 각각 퀵 정렬을 재귀적으로 수행합니다.
각 부분 리스트에 대해 다시 피벗을 선택하고, 분할을 수행하며 정렬을 진행합니다. - 정렬 완료
: 분할이 더 이상 불가능할 때(부분 리스트의 크기가 1 이하가 될 때)까지 재귀 호출을 반복합니다. 이렇게 하면 모든 부분 리스트가 정렬됩니다.
Ex) [5, 2, 4, 6, 1, 3] 이라는 리스트를 퀵 정렬한다고 가정해봅시다.
-
초기 상태
: 리스트 중간에 위치한 4를 피벗으로 선택합니다.
[2, 1, 3] < 4 < [5, 6] -
왼쪽 부분 리스트 정렬
:피벗을 기준으로 왼쪽 부분 리스트를 나눕니다.
[2, 1, 3]
1 < 2 < 3
더 이상 분할이 불가능하므로 왼쪽 부분 리스트는 정렬됩니다. -
오른쪽 부분 리스트 정렬
:피벗을 기준으로 오른쪽 부분 리스트를 나눕니다.
[5, 6]
5 < 6
더 이상 분할이 불가능하므로 오른쪽 부분 리스트는 정렬됩니다. -
정렬 완료
:정렬된 왼쪽 부분 리스트 + 피벗 + 정렬된 오른쪽 부분 리스트를 합칩니다.
[1, 2, 3, 4, 5, 6]
이런 식으로 퀵 정렬은 피벗을 기준으로 리스트를 분할하고 재귀적으로 정렬을 수행하여 최종적으로 정렬된 리스트를 얻게 됩니다.
54321 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?
: 이미 내림차순으로 정렬되어 있기 때문에, 사용 목적에 따라 인덱스를 역순으로 접근하면 가장 시간적 효율이 높다고 생각합니다.
그럼에도 정렬을 해야 한다면, 가장 빠른 시간복잡도로 알려진 힙 정렬이나 병합 정렬을 사용할 것 같습니다.
랜덤으로 배치된 배열이 있을때, 어떤 정렬을 사용하면 좋을까요?
: 배열의 상태에 구애받지 않고 일정한 시간 복잡도를 가진 힙 정렬이나 병합 정렬을 사용할 것 같습니다.
자릿수가 모두 같은 수가 담긴 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?
: 공간 복잡도가 높아지기는 하지만, 기수 정렬을 사용하는 것이 시간적으로 효율이 가장 높다고 생각합니다.
기수 정렬은 일의 자리부터 순서대로 자릿수 별로 버킷에 담는 방식으로,
최대 자릿수 만큼만 반복하면 되기 때문에 빠르게 정렬이 가능합니다.
