버블정렬(Bubble sort)에 대해 설명하고 예제소스를 구현해보아라
- 오름차순으로 정렬한다.
- 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.
- 구현은 간단하지만 비효율적이다.
- 시간 복잡도 : O(n^2)
void bubble_sort(int list[], int n)
{
int temp;
for (int i = n - 1; i > 0; i--) {
// 0 ~ (i-1)까지 반복
for (int j = 0; j < i; j++) {
// j번째와 j+1번째의 요소가 크기 순이 아니면 교환
if (list[j] < list[j + 1]) {
temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
}
}선택정렬(Selection Sort)에 대해 설명하시고 예제소스를 구현해보아라
- 오름차순으로 정렬한다.
- 원소를 넣을 위치를 정해두고 어떤 원소를 넣을지 선택하는 알고리즘
- 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫번째에 놓고, 두번째 자료를 세번재 자료부터 마지막 자료까지 차례대로 비교하여 그 중 가장 작은 값을 찾아 두번재에 놓고 ... 이러한 과정을 반복하여 정렬을 수행한다.
- 구현은 간단하지만 비효율적이다.
- 시간 복잡도 : O(n^2)
void selectionSort(int arr[], int size) {
int minIndex;
int temp;
for (int i = 0; i < size - 1; i++) {
minIndex = i;
for (int j = i + 1; j < size; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}삽입정렬(Insertion Sort)에 대해 설명하시오 예제소스를 구현해보아라
- 오름차순으로 정렬한다.
- 삽입 정렬은 두번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
- 즉, 두번째 자료는 첫번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입 될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한칸 씩 뒤로 이동시킨다.
- 처음 Key값은 두 번재 자료부터 시작한다.
- 시간복잡도 : O(n^2)
void insertion_sort(int arr[], int size)
{
int i, j;
int key;
for (i = 1; i < size; i++)
{
key = arr[i];
for (j = i - 1; j >= 0; j--)
{
if (arr[j] < key) break;
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}퀵 정렬(Quick Sort)에 대해 설명하시고 예제소스를 구현해보아라
- 오름차순을 기준으로 정렬한다.
- 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot)이라고 한다. 피벗을 기준으로 피벗보다 작은 요소들은 왼쪽으로, 피벗보다 큰 요소들은 오른쪽으로 옮겨진다. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 이 과정을 더 이상 분할이 불가능할 때까지 반복한다.
- 다른 정렬 알고리즘에 비해 속도가 빠르므로 사용빈도가 높다.
- 시간복잡도 : 평균 O(nlogn) 최악 O(n^2)
void swap(int *arr,int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
void quick_sort(int *arr, int start, int end)
{
int pivot = arr[start];
int left = start+1;
int right = end;
while(left <= right)
{
while(arr[left] < pivot) { left++; } //pivot보다 작은 경우는 건너뛰고 크거나 같은경우 멈춤
while(arr[right] > pivot) { right--; } //pivot보다 큰 경우는 건너뛰고 작거나 같은경우 멈춤
if(left <= right){ swap(arr, left, right); }
}
//1개로 쪼개질때 까지
if(start < end)
{
swap(arr, start, right); //pivot값과 arr[right] 값 swap
myQuickSort(arr, start, right-1); //앞 부분
myQuickSort(arr, right+1, end); //뒷 부분
}
return;
}
[출처 및 참고 사이트]
https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html
'Study > 자료구조&알고리즘' 카테고리의 다른 글
| [알고리즘] 순차 검색(Sequential Search) 과 이분 검색(Binary Search) + (0) | 2021.07.14 |
|---|---|
| [자료구조] 단순 연결 리스트(Simple linked list) 와 이중 연결 리스트(Doubly linked list) (0) | 2021.07.14 |
| [자료구조] 스택(Stack)과 큐(Queue) (0) | 2021.07.13 |