[#136][알고리즘][면접] 코딩면접 준비하기 - 정렬
[면접] 코딩면접 준비하기 - 정렬
1. 버블 정렬(Bubble Sort)1) 방법 : 인접한 두 원소를 비교하며 정렬
2) 시간복잡도 : O(n²)
바깥 for loop = n-1
안쪽 for loop = n-1, n-2, n-3, ..., 2, 1
원소 교환 = 상수
T(n) = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n²)
3) 코드
#include <iostream>
using namespace std;
int arr[] = { 3,5,2,1,4};
void printArr( int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void bubbleSort(int size) {
for (int k = 0; k < size - 1; k++) {
for (int i = 0, j = i + 1; i < size - 1; i++, j++) {
if (arr[i] > arr[j]) {
swap(arr[i], arr[j]);
cout << i << " " << j << endl;
printArr(size);
}
}
}
}
int main() {
int size = sizeof(arr) / sizeof(int);
bubbleSort(size);
printArr(size);
}
| cs |
2. 퀵정렬 (Quick Sort) - top down식 정렬
1) 방법 : pivot보다 작은 값은 앞으로, 큰 값은 뒤로 정렬
2) 시간복잡도 : O(nlogn) / 최악 O(n²)
최악인 경우 = 이미 정렬된 배열, pivot이 항상 최소/최대가 될 때
=> pivot을 중간값으로 설정하여 개선 가능
3) 분할 정복(divide and conquer)
분할 = pivot을 중심으로 2개의 부분집합으로 분할
정복 = 부분집합의 원소 중 pivot보다 작은 원소는 왼쪽 부분집합으로, 큰 원소는 오른쪽 부분집합으로 정렬.
3) 코드
#include <iostream>
using namespace std;
int arr_size;
void printArr(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void partition(int arr[], int left, int right, int &pivot) {
int i, j, pivotitem;
pivotitem = arr[left];
j = left;
for (i = left + 1; i <= right; i++) {
if (arr[i] < pivotitem) {
j++;
swap(arr[i], arr[j]);
}
}
pivot = j;
swap(arr[left], arr[pivot]);
}
void QuickSort(int arr[], int left, int right) {
int pivotpoint;
if (right > left) {
partition(arr, left, right, pivotpoint);
QuickSort(arr, left, pivotpoint - 1);
QuickSort(arr, pivotpoint + 1, right);
}
}
int main() {
int arr[] = { 14,3,1,63,46,77,23 };
arr_size = sizeof(arr) / sizeof(int);
QuickSort(arr, 0, arr_size - 1);
printArr(arr, arr_size);
}
| cs |
3. 합병정렬 (Merge Sort) - bottom up정렬
1) 방법 : 데이터를 계속 나눈 후, 더이상 분할이 불가능 할 때 합병하면서 정렬
2) 시간복잡도 : O(nlogn)
3) 특징 : 퀵 정렬과 달리 추가적인 메모리 필요 (n만큼). stable sort라는 장점이 있음.
4) 코드
#include <iostream>
using namespace std;
int arr_size;
void printArr(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void Merge(int arr[],int left, int mid, int right) {
int i, j, k;
int *tmparr;
tmparr = new int[arr_size];
i = left;
j = mid + 1;
k = left;
//left~mid까지 비교, mid+1~right까지 비교
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
tmparr[k] = arr[i];
i++;
}
else {
tmparr[k] = arr[j];
j++;
}
k++;
}
if (i > mid) {
//arr[j]~arr[right]를 tmparr[k]~tmparr[right]로 옮김
for (int a = j; a <= right; a++) {
tmparr[k] = arr[a];
k++;
}
}
else {
//arr[i]~arr[mid]를 tmparr[k]~tmparr[right]로 옮김
for (int a = i; a <= mid; a++) {
tmparr[k] = arr[a];
k++;
}
}
//tmparr[left]~tmparr[high]를 arr[left]~arr[high]로 옮김
for (int a = left; a <= right; a++) {
arr[a] = tmparr[a];
}
}
void MergeSort(int arr[], int left, int right) {
int mid;
if (left < right) {
mid = (left + right) / 2;
MergeSort(arr,left, mid);
MergeSort(arr,mid + 1, right);
Merge(arr,left, mid, right);
}
}
int main() {
int arr[] = { 14,3,1,63,46,77,23 };
arr_size = sizeof(arr) / sizeof(int);
MergeSort(arr, 0, arr_size - 1);
printArr(arr, arr_size);
}
| cs |
4. 삽입정렬 (Insertion Sort)
1) 방법 : 앞에서부터 최소값으로 채우는 정렬
2) 시간복잡도 : O(n²)
3) 코드
#include <iostream>
using namespace std;
int arr_size;
void printArr(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void InsertionSort(int arr[]) {
int i, j;
int key;
for (i = 1; i < arr_size; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = { 14,3,1,63,46,77,23 };
arr_size = sizeof(arr) / sizeof(int);
InsertionSort(arr);
printArr(arr, arr_size);
}
| cs |
5. 선택정렬 (Selection Sort)
1) 방법 : 가장 작은 원소를 맨 앞으로 보내기
2) 시간복잡도 : O(n²)
3) 코드
#include <iostream>
using namespace std;
int arr_size;
void printArr(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void SelectionSort(int arr[], int size) {
int i, j;
int min;
for (i = 0; i < size - 1; i++) {
min = i;
for (j = i + 1; j < size; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
swap(arr[i], arr[min]);
}
}
int main() {
int arr[] = { 14,3,1,63,46,77,23 };
arr_size = sizeof(arr) / sizeof(int);
SelectionSort(arr, arr_size);
printArr(arr, arr_size);
}
| cs |
6. 힙정렬 (Heap Sort)
1) 방법
- 배열로 힙을 만든다
- 힙에서 최대값을 마지막 값과 바꾼다. 이를 삭제한다.
- 루트노드에 대하여 heapfiy한다
- 이를 반복한다
2) 시간복잡도 : O(nlogn)
3) 힙 : 한 노드가 최대 두개의 자식노드를 가지며, 마지막 레벨을 제외한 모든 레벨에서 노드가 꽉 차있는 완전이진트리. 각 노드의 값은 자식 노드에 저장된 값 보다 크거나 같다.
댓글
댓글 쓰기