선택 정렬
· 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
· 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야함
· 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 N + (N-1) + (N-2) + ... + 2
#include<iostream>
using namespace std;
int n = 10;
int target[10] = { 7,5,9,0,3,1,6,2,4,8 };
int main()
{
//선택정렬
for (int i = 0; i < n; i++)
{
int min_index = i;
for (int j = i + 1; j < n; j++)
{
if (target[min_index] > target[j])
{
min_index = j;
}
}
swap(target[i], target[min_index]);
}
//출력
for (int i = 0; i < n; i++)
{
cout << target[i] << ' ';
}
}삽입 정렬
· 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
· 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작함
· 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
#include<iostream>
using namespace std;
int n = 10;
int target[10] = { 7,5,9,0,3,1,6,2,4,8 };
int main()
{
//삽입 정렬
for (int i = 1; i < n; i++)
{
for (int j = i; j > 0; j--)
{
if (target[j] < target[j - 1])
{
swap(target[j], target[j - 1]);
}
else break;
}
}
//출력
for (int i = 0; i < n; i++)
{
cout << target[i] << ' ';
}
}퀵 정렬
· 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
· 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
· 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
· 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)으로 설정함
#include<iostream>
using namespace std;
int n = 10;
int target[10] = { 7,5,9,0,3,1,6,2,4,8 };
void quickSort(int* target, int start, int end)
{
if (start >= end) return;
int pivot = start;
int left = start + 1;
int right = end;
while (left <= right)
{
while (left <= end && target[left] <= target[pivot]) left++;
while (right > start && target[right] >= target[pivot]) right--;
if (left > right) swap(target[pivot], target[right]);
else swap(target[left], target[right]);
}
quickSort(target, start, right - 1);
quickSort(target, right + 1, end);
}
int main()
{
quickSort(target, 0, n - 1);
//출력
for (int i = 0; i < n; i++)
{
cout << target[i] << ' ';
}
}개수 정렬
· 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
- 개수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
· 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장합니다.
#include<iostream>
#define MAX_VALUE 9
using namespace std;
int n = 15;
int arr[15] = { 7,5,9,0,3,1,6,2,9,1,4,8,0,5,2 };
int cnt[MAX_VALUE + 1];
int main()
{
for (int i = 0; i < n; i++)
{
cnt[arr[i]] += 1;
}
for (int i = 0; i <= MAX_VALUE; i++)
{
for (int j = 0; j < cnt[i]; j++)
{
cout << i << ' ';
}
}
}
참고한 동빈나님 유튜브
https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4