정렬(Sort)
정렬이란 : 데이터들을 일정한 순서대로 열거하는 알고리즘을 말한다.
정렬의 종류 : 대표적으로 거품정렬(Bubble Sort) , 선택정렬(Selection Sort) , 삽입정렬(Insertion Sort), 퀵정렬(Quick Sort), 합병정렬(Merge Sort) , 힙정렬(Heap Sort) 등이있다.
거품정렬 (Bubble Sort)
- 인접하는 두 항을 축차교환한다
- 원리는 간단하지만 교환 횟수가 많다.
- 최악일때 O(n^2)으로 swap 발생한다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include<bits/stdc++.h>
using namespace std;
void bubbleSort(vector<int> &arr) {
for (int i = arr.size()-1; i >=0; i--) {
for (int j = 0; j< i; j++) {
if (arr[j] > arr[j +1])
swap(arr[j], arr[j + 1]);
}
}
}
int main() {
vector<int> arr = { 41,34,6,16,38,36,28,19,45,43,49 };
bubbleSort(arr);
for (int i : arr)
cout << i << " ";
cout<<endl;
}
|
cs |
이미지 출처 : https://riverblue.tistory.com/39
선택정렬 (Selection Sort)
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
- swap O(n)번 발생
- 거품정렬보다 항상 우수하다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include<bits/stdc++.h>
using namespace std;
void selectionSort(vector<int> &arr)
{
int len = arr.size();
for (int i = 0; i < len - 1; i++)
{
int indexMin = i;
for (int j = i + 1; j < len; j++)
{
if (arr[j] < arr[indexMin])
{
indexMin = j;
}
}
swap(arr[i], arr[indexMin]);
}
}
int main() {
vector<int> arr = { 41,34,6,16,38,36,28,19,45,43,49 };
selectionSort(arr);
for (int i : arr)
cout << i << " ";
cout<<endl;
}
|
cs |
출처 : https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC
삽입정렬 :
- 안정한 정렬 방법(바로 옆의 데이터와 비교하기 때문)
- 자료의 수가 적을 경우 알고리즘 구현이 매우 간단
- 이미 정렬되어 있는 경우나 자료의 수가 적은 정렬에 매우 효율적
- 비교적 많은 레코드들의 이동을 포함
- 자료의 수가 많고 자료의 크기가 클 경우 적합하지 않음
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<bits/stdc++.h>
using namespace std;
void insertion_sort(vector<int> &arr)
{
int len = arr.size();
for (int i = 1; i < len; i++)
{
int j = i;
int temp = arr[i];
while (--j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
int main() {
vector<int> arr = { 5,3,8,1,2,7 };
insertion_sort(arr);
for (int i : arr)
cout << i << " ";
cout<<endl;
}
|
cs |
| 정렬 종류 | Worst Case | Average Case | Best Case |
| Bubble Sort | O(n^2) | O(n^2) | O(n^2) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) |
| Insertion Sort | O(n^2) | O(n^2) | O(n) |
퀵정렬(Quick Sort)
'Computer Science > 자료구조' 카테고리의 다른 글
| 자료구조 hash (0) | 2022.04.22 |
|---|---|
| [CS 자료구조] 그래프와 트리의 차이 (0) | 2022.03.07 |
| [자료구조] CS 공부 스택 vs 큐 (스택으로 큐구현 , 큐로 스택구현) (0) | 2022.02.24 |
| [자료구조] List → ArrayList vs LinkedList (0) | 2022.01.20 |
| [자료구조] Queue 구현하기 (0) | 2020.08.08 |
