😎 시간복잡도를 빅오표기법으로 나타내시오.
😎 거품 정렬, 버블정렬 (Bubble Sort)
서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘입니다. 가장 쉬운 정렬 알고리즘이지만 시간복잡도가 좋은 퍼포먼스를 내지 못해서 실제로는 잘 사용되지 않습니다.
시간복잡도는 O(n²)이며 공간복잡도는 하나의 배열만 사용하여 정렬을 진행하기 때문에 O(n)입니다.
정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가
O(n²)으로 동일하다.
과정(오름차순)
- 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
- 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
자바 코드 구현
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length; i++) { // 1.
for(int j= 1 ; j < arr.length-i; j++) { // 2.
if(arr[j-1] > arr[j]) { // 3.
// swap(arr[j-1], arr[j])
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}장점
- 구현이 매우 간단하고, 소스코드가 직관적이다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. ➡ 제자리 정렬(in-place sorting)
- 안정 정렬(Stable Sort) 이다.
단점
- 시간복잡도가 최악, 최선, 평균 모두 O(n²)으로, 굉장히 비효율적이다.
- 정렬 돼있지 않은 원소가 정렬 됐을 때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.
시간 복잡도
| Name | Best | Avg | Worst |
| 거품 정렬 | O(n²) | O(n²) | O(n²) |
😎 선택 정렬(Selection Sort)
원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘으로
배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 편합니다.
시간복잡도는 O(n²)입니다.
과정(오름차순)
- 주어진 배열 중에 최솟값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 계속해서 교체한다.
자바 코드로 구현
void selectionSort(int[] arr) {
int indexMin, temp;
for (int i = 0; i < arr.length-1; i++) { // 1.
indexMin = i;
for (int j = i + 1; j < arr.length; j++) { // 2.
if (arr[j] < arr[indexMin]) { // 3.
indexMin = j;
}
}
// 4. swap(arr[indexMin], arr[i])
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
System.out.println(Arrays.toString(arr));
}
장점
- Bubble sort와 마찬가지로 알고리즘이 단순하다.
- 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
- Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. ➡ 제자리 정렬(in-place sorting)
단점
- 시간복잡도가 O(n²)으로, 비효율적이다.
- 불안정 정렬(Unstable Sort)이다.
시간 복잡도
| Name | Best | Avg | Worst |
| 선택 정렬 | O(n²) | O(n²) | O(n²) |
😎 삽입 정렬(Insertion Sort)
선택정렬과 유사하지만, 좀 더 효율적인 정렬 알고리즘입니다.
선택 정렬과 삽입 정렬의 차이점
둘은 k번째 반복 이후, 첫 번째 k 요소가 정렬된 순서로 온다는 점에서 유사합니다. 하지만, 선택정렬은 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 삽입정렬은 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있습니다.
삽입정렬은 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교해 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.
최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다. 평균 시간복잡도는 O(n²)입니다.
과정(오름차순)
- 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
- temp와 이전에 있는 원소들과 비교하며 삽입해 나간다.
- '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다
자바 코드 구현
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){ // 1.
int temp = arr[index];
int prev = index - 1;
while( (prev >= 0) && (arr[prev] > temp) ) { // 2.
arr[prev+1] = arr[prev];
prev--;
}
arr[prev + 1] = temp; // 3.
}
System.out.println(Arrays.toString(arr));
}- 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치(index)부터 탐색을 시작한다. temp에 임시로 해당 위치(index) 값을 저장하고, prev에는 해당 위치(index)의 이전 위치(index)를 저장한다.
- 이전 위치(index)를 가리키는 prev가 음수가 되지 않고, 이전 위치(index)의 값이 '1'번에서 선택한 값보다 크다면, 서로 값을 교환해 주고 prev를 더 이전 위치(index)를 가리키도록 한다.
- '2'번에서 반복문이 끝나고 난 뒤, prev에는 현재 temp 값보다 작은 값들 중 제일 큰 값의 위치(index)를 가리키게 된다. 따라서, (prev+1)에 temp 값을 삽입해 준다.
장점
- 알고리즘이 단순하다.
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. ➡ 제자리 정렬(in-place sorting)
- 안정 정렬(Stable Sort)이다.
- Selection Sort나 Bubble Sort과 같은 O(n²) 알고리즘에 비교하여 상대적으로 빠르다.
단점
- 평균과 최악의 시간복잡도가 O(n²)으로 비효율적이다.
- Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.
시간복잡도
| Name | Best | Avg | Worst |
| 삽입 정렬 | O(n) | O(n²) | O(n²) |
최악의 경우(역으로 정렬되어 있을 경우) 선택정렬과 마찬가지로 O(n²) 이다.
하지만, 모두 정렬이 되어있는 경우, 한 번씩 밖에 비교를 안 하므로 시간복잡도 O(n)을 가지게 된다.
😎 퀵 정렬(Quick Sort)
매우 빠른 정렬 속도를 자랑하는 분할 정복 알고리즘* 중 하나로 합병정렬과 달리 리스트를 비균등하게 분할합니다. 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬을 합니다.
* 분할 정복(divide and conquer) 방법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후 결과를 모아서 원래의 문제를 해결하는 전략이다.
평균적으로 가장 빠른 정렬 알고리즘으로 가장 많이 쓰는 정렬알고리즘입니다. JAVA에서 Arrays.sort() 내부적으로도 Dual Pivot Quick Sort로 구현되어 있을 정도로 효율적인 알고리즘으로 기술면접에서 빈번하게 출제됩니다.
최악의 경우에는 O(n²)의 비교를 수행하지만 일반적으로 O(nlogn)의 시간복잡도를 가집니다.
과정(오름차순)
- 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다.
자바 코드로 구현
퀵 정렬은 다음의 단계들로 이루어진다.
1. 정복 (Conquer)
부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
public void quickSort(int[] array, int left, int right) {
if(left >= right) return;
// 분할
int pivot = partition();
// 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
quickSort(array, left, pivot-1); // 정복(Conquer)
quickSort(array, pivot+1, right); // 정복(Conquer)
}
2. 분할 (Divide)
입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열 (피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들)로 분할한다.
public int partition(int[] array, int left, int right) {
int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
int i = left, j = right;
while(i < j) {
while(pivot < array[j]) {
j--;
}
while(i < j && pivot >= array[i]){
i++;
}
swap(array, i, j);
}
array[left] = array[i];
array[i] = pivot;
return i;
}
장점
- 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
단점
- 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
시간복잡도
| Name | Best | Avg | Worst |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n²) |
최악: O(n²)
피벗 값이 최소나 최댓값으로 지정되어 파티션이 나누어지지 않았을 때, O(n²)에 대한 시간복잡도를 가지는 데 이는 정렬하고자 하는 배열이 오름차순 정렬되어 있거나 내림차순 정렬되어 있으면 생기는 경우입니다.
😎 병합 정렬, 합병 정렬(Merge Sort)
정렬할 리스트를 반으로 쪼개나가며 좌측과 우측 리스트를 계속하여 분할해 나간 후 각 리스트 내에서 정렬 후 분할 정복 방법을 통해 구현하는 알고리즘이다.
* 분할 정복 방법은, 큰 문제를 작은 문제 단위로 쪼개면서 해결해 나가는 방식
병합정렬은 가장 많이 쓰이는 정렬 알고리즘 중 하나이며 시간복잡도는 O(nlogn)을 보장한다.
퀵소트와의 차이점
퀵정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)
합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)
합병정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적입니다.
시간 복잡도
| Name | Best | Avg | Worst |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
😎 힙 정렬(Heap Sort)
완전 이진트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식으로 시간 복잡도 O(nlogn)입니다.
최대 힙트리나 최소 힙트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 됩니다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.
과정
- n개의 노드에 대한 완전 이진트리를 구성하고 최대 힙을 구성한다.
- 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
- 1과 2를 반복한다.
힙 소트가 유용할 때
- 가장 크거나 가장 작은 값을 구할 때
- 최소 힙 or 최대 힙의 루트 값이기 때문에 한 번의 힙 구성을 통해 구하는 것이 가능
- 최대 k 만큼 떨어진 요소들을 정렬할 때
- 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있음
시간 복잡도
| Name | Best | Avg | Worst |
| 힙 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
😎 6개 정렬 알고리즘 시간복잡도 비교
| Name | Best | Avg | Worst |
| 거품 정렬 | O(n²) | O(n²) | O(n²) |
| 선택 정렬 | O(n²) | O(n²) | O(n²) |
| 삽입 정렬 | O(n) | O(n²) | O(n²) |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n²) |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
| 힙 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
나머지 알고리즘 문제는 2편에서 이어서 작성하도록 하겠습니다.
출처:
https://mangkyu.tistory.com/90
'기술 면접 준비' 카테고리의 다른 글
| [CS 모의면접 스터디] 자바 편 (0) | 2023.11.16 |
|---|---|
| [기술면접] 알고리즘 - 2/2 (0) | 2023.05.22 |
| [기술면접] 자료구조 - 2/2 (1) | 2023.05.16 |
| [기술면접] 자료구조 - 1/2 (2) | 2023.05.16 |
| [기술면접] 운영체제 - 2/2 (0) | 2023.04.04 |