정렬
- 데이터를 특정한 기준에 따라 순서대로 나열한 것
선택정렬
- 시간복잡도 - $O(N^2)$
- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복
- 가장 작은 것을 선택
#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;
int main (){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int num[] = { 7,5,9,0,3,1,6,2,4,8 };
// 선택 정렬
for (int i = 0; i <10; i++) {
int idx = i; // 가장 작은 원소 인덱스
for (int j = i; j < 10; j++) {
if (num[j] < num[idx]) {
idx = j;
}
}
swap(num[idx], num[i]);
}
for (int i = 0; i < 10; i++) {
cout << num[i] << " ";
}
삽입 정렬
알고리즘 문제 풀이에 사용하기엔 느림
But 정렬이되어 있는 상태로 입력이 주어지는 문제라면 다른 알고리즘을 사용하는 것보다 효율적
- 시간 복잡도 - 최선 $O(N)$ , 최악 $O(N^2)$
- 필요할 때만 위치를 바꿔서 '데이터가 거의 정렬 되어 있을 때' 효율적
- 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다
#include <iostream>
#include <stdlib.h>
#include<algorithm>
using namespace std;
int main (){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int num[] = { 7,5,9,0,3,1,6,2,4,8 };
// 삽입 정렬
for (int i = 1; i < 10; i++) {
for (int j = i; j>0; j--) {
if (num[j] < num[j - 1]) {
swap(num[j], num[j - 1]);
}
else {
break;
}
}
}
for (int i = 0; i < 10; i++) {
cout << num[i] << " ";
}
}
퀵 정렬
c++ STL의 algorithm 헤더에 있는 sort() 함수 ⇒ 퀵정렬
- 시간 복잡도 - $O(NlongN)$
- 기준을 설정한 다음 큰 수와 작은 숫자를 교환한 후 리스트를 반으로 나누는 방식
- 피봇 : 큰 수와 작은 수를 교환 할 때, 교환하기 위한 기준을 명칭
#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;
void quickSort(int* arr, int start, int end) {
if (start >= end) return; // 원소가 1개인 경우 종료
int pivot = start; // 피벗은 첫 번째 원소
int left = start + 1;
int right = end;
while (left <= right) {
// 피벗보다 큰 데이터를 찾을 때까지 반복
while (left <= end && arr[left] <= arr[pivot]) left++;
// 피벗보다 작은 데이터를 찾을 때까지 반복
while (right > start && arr[right] >= arr[pivot]) right--;
// 엇갈렸다면 작은 데이터와 피벗을 교체
if (left > right) swap(arr[pivot], arr[right]);
// 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
else swap(arr[left], arr[right]);
}
// 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
}
int main (){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int num[] = { 7,5,9,0,3,1,6,2,4,8 };
// 퀵 정렬
// 라이브러리 이용
// sort(num, num + 10);
// 일반 구현
quickSort(num, 0, 9);
for (int i = 0; i < 10; i++) {
cout << num[i] << " ";
}
}
계수 정렬
- 시간복잡도 - $O(N+K)$
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
- 데이터의 크기 범위가 제한되어 정수로 표현할 수있을 때만 사용 가능
- 가장 큰 데이터와 작은 데이터 크기가 작아야함
#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;
int main (){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int num[] = { 7,5,9,0,3,1,6,2,4,8,0,5,2};
int ans[13] = {0,};
// 계수 정렬
for (int i = 0; i < 13; i++) {
ans[num[i]]++;
}
for (int i = 0; i < 10; i++) {
if (ans[i] > 0) {
while (ans[i]--) {
cout << i << " ";
}
}
}
}
C++ sort STL
오름차순 (default)
- sort()는 algorithm 헤더 파일에 속함
- 퀵 정렬이용
- 평균 시간복잡도 - $O(NlongN)$
사용법
sort(arr, arr+1);
sort(v.begin(), v.end());
sort(v.begin(), v.end(), compare); // compare : 사용자 정의 함수
sort(v.begin(), v.end(), greater<자료형>()); // 내림차순
sort(v.begin(), v.end(), less<자료형>()); // default - 오름차순
'Algorithm > C++' 카테고리의 다른 글
[개념] 최단 경로 구하기 (0) | 2020.10.13 |
---|---|
[개념] 다이나믹 프로그래밍(동적계획법) (0) | 2020.10.11 |
[개념] DFS/BFS (0) | 2020.10.09 |
[개념] 이진탐색 (0) | 2020.10.09 |