Basic sorting algorithm ( Selection, Bubble, Insertion)
아래 알고리즘들은 오름차순을 기준으로 함
선택 정렬 (Selection Sort)
- 시간 복잡도 =
O(n^2) In-place(제 자리)정렬 알고리즘으로 새로운 메모리 공간을 요구하지 않아 메모리 공간이 제약적인 상황에서 사용할 수 있음선택 정렬은버블 정렬(Bubble sort) 보다 항상 우수함 (버블 정렬이 최적화 안되어 있을 경우)
선택 정렬 알고리즘
최소값 탐색 후 가장 앞 자리로 옮기며 정렬하는 알고리즘
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
선택 정렬 C++ 코드
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int> &list, int n) {
int temp;
for (int i = 0; i < n - 1; i++) {
int indexMin = i;
for (int j = i + 1; j < n; j++) {
if (list[j] < list[indexMin])
indexMin = j;
}
//swap
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}
int main() {
int n;
cin >> n;
vector<int> list(n);
for (int i = 0; i < n; i++)
cin >> list[i];
selectionSort(list, n);
for (int i = 0; i < n; i++)
cout << list[i]<<" ";
return 0;
}버블 정렬 (Bubble Sort)
- 시간 복잡도 =
O(n^2) In-place정렬 알고리즘- 정렬 알고리즘 중에서 매우 느린 속도
- 최적화시 최상의 경우 시간 복잡도는 O(n)으로 선택 정렬보다 빠를 수 있음
버블 정렬 알고리즘
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
- i 번째 요소와 i + 1 번째 요소와 비교
- i 번째 요소가 i + 1 번째 요소보다 크면 둘이 swap
- 1~2 과정을 i + 1 = n 이 될 때까지 반복
- n을 1감소하고 1~3 과정 반복
- n = 1 되면 끝
버블 정렬 c++ 코드
#include <iostream>
#include <vector>
using namespace std;
void BubbleSort(vector<int> &list, int n) {
int temp;
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (list[j] > list[j + 1]) {
//swap
temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
swapped = true;
}
}
//버블 정렬 최적화 코드
if (swapped == false)break;
}
}
int main() {
int n;
cin >> n;
vector<int> list(n);
for (int i = 0; i < n; i++)
cin >> list[i];
BubbleSort(list, n);
for (int i = 0; i < n; i++)
cout << list[i]<<" ";
return 0;
}삽입 정렬 (Insertion Sort)
사람이 손안의 카드를 정렬하는 방법과 유사
- 시간 복잡도 =
O(n^2) - 선택 정렬과 버블 정렬 중에서 비교적 빠른 알고리즘
- 배열이 길어질수록 효율이 떨어짐
- 어느 정도 정렬이 된 리스트일수록 뛰어난 성능을 보여줌
삽입 정렬 알고리즘
자신의 위치를 찾아 삽입하면서 완성하는 알고리즘
- 두 번째 요소 부터 시작
- 자신의 앞에 있는 요소들은 정렬이 되어 있음
- 앞에 요소와 하나씩 비교하면서 자신의 위치를 찾아서 삽입
- i++
삽입 정렬 c++ 코드
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<int> &list, int n) {
int key;
for (int i = 1; i < n; i++) {
key = list[i];
int j = i - 1;
while (j >= 0 && list[j] > key) {
list[j + 1] = list[j];
j--;
}
list[j + 1] = key;
}
}
int main() {
int n;
cin >> n;
vector<int> list(n);
for (int i = 0; i < n; i++)
cin >> list[i];
insertionSort(list, n);
for (int i = 0; i < n; i++)
cout << list[i]<<" ";
return 0;
}시간 복잡도 비교
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html