Sorting
- FIFO(First In, First Out) 구조
- 삽입과 삭제 연산이 서로 다른 한 군데
- 느린 알고리즘의 경우 시간복잡도가 O(N^2), 빠른경우 O(NlogN)
- 안정성이 보장되는 경우인지 판단해야함
- 안정성 보장 : 같은 키를 가진 데이터의 순서가 안 바뀜
1. 거품정렬 (Bubble Sort)
첫번째 원소부터 인접한 원소와 비교하며 자리를 바꾸며 맨 끝부터 정렬
가장 큰 값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬
안정성 보장 O
시간 복잡도 : O(N^2) -> 비효율적
void bubble_sort(int list[], int n){
int i, j, temp;
for(i=n-1; i>0; i--){
// 0 ~ (i-1)까지 반복
for(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;
}
}
}
}
2. 선택정렬 (Selection Sort)
선택된 값과 나머지 데이터 중에 비교하여 알맞은 자리를 찾는 알고리즘
가장 작은 최솟값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬
안정성 보장 X
시간복잡도 : O(N^2) -> 비효율적
void selection_sort(int list[], int n){
int i, j, least, temp;
// 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복한다.
for(i=0; i<n-1; i++){
least = i;
// 최솟값을 탐색한다.
for(j=i+1; j<n; j++){
if(list[j]<list[least])
least = j;
}
// 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
if(i != least){
SWAP(list[i], list[least], temp);
}
}
}
3. 삽입정렬 (Insertion Sort)
버블 정렬과 달리 i번째 원소를 정렬된 상태의 i-1번째까지와 비교하여 적절한 위치에 삽입
안정성 보장 O
시간복잡도 : 평균, 최악- O(N^2) / 최선(모두 정렬 완료되어있을 경우) - O(N)
void insertion_sort(int list[], int n){
int i, j, key;
for(i=1; i<n; i++){
key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
// 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
// j 값은 음수가 아니어야 되고
// key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
for(j=i-1; j>=0 && list[j]>key; j--){
list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
}
list[j+1] = key;
}
}
4. 퀵정렬 (Quick Sort)
분할 정복 방법을 통한 정렬
하나의 pivot을 정해서 이 pivot보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 위치
안정성 보장 X
시간복잡도 : 평균, 최선- O(NlogN) / 최선(모두 정렬 완료되어있을 경우) - O(N^2)
개선 - 만약 정렬되어 있다면 배열의 가장 앞에 있는 값과 중간값을 교환하여 중간값이 pivot이 되게 하면 확률적으로나마 시간복잡도 개선 가능 (확률적이기 때문에 반드시 개선되는 것은 아님)
#include <iostream>
#include <ctime>
#define MAX_ARR 20
using namespace std;
void quickSort(int arr[], int first, int last)
{
if(first >= last) return;
int pivot = first;
int i = first + 1;
int j = last;
int tmp;
while (i <= j)
{
while (arr[i] < arr[pivot] && i <= last) i++;
while (arr[j] >= arr[pivot] && j > first) j--;
if (i >= j) break;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
tmp = arr[j];
arr[j] = arr[pivot];
arr[pivot] = tmp;
quickSort(arr, first, j - 1);
quickSort(arr, j + 1, last);
}
void print(int arr[], int N, const char* str)
{
cout << str << '\n';
for (int i = 0; i < N; i++) cout << arr[i] << " ";
cout << '\n';
}
int main(void)
{
srand(time(NULL));
int arr[MAX_ARR];
for (int i = 0; i < MAX_ARR; i++)
arr[i] = rand() % 10 + 1;
print(arr, MAX_ARR, "[PREV]");
quickSort(arr, 0, MAX_ARR - 1);
print(arr, MAX_ARR, "[NEXT]");
return 0;
}
5. 병합정렬 (Merge Sort)
배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서 전체를 정렬하는 분할 정복
안정성 보장 O
시간복잡도 : O(NlongN)
LinkedList 정렬에 사용하면 효율적
단점 : 임시 배열(추가 메모리) 필요
#include <iostream>
#include <ctime>
#define MAX_ARR 20
using namespace std;
void merge(int *arr, int first, int mid, int last)
{
int* sorted = new int[last - first + 1];
int i, j, k;
i = first; // First arr idx
j = mid + 1; // Second arr idx
k = 0; // Sorted arr idx
while (i <= mid && j <= last)
{
if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
else sorted[k++] = arr[j++];
}
if (i > mid)
while (j <= last) sorted[k++] = arr[j++];
else
while (i <= mid) sorted[k++] = arr[i++];
for (i = first, k = 0; i <= last; i++, k++) arr[i] = sorted[k];
delete[] sorted;
}
void mergeSort(int *arr, int first, int last)
{
if (first < last)
{
int mid = (first + last) / 2;
mergeSort(arr, first, mid);
mergeSort(arr, mid + 1, last);
merge(arr, first, mid, last);
}
}
void print(int* arr, int N, const char* str)
{
cout << str << '\n';
for (int i = 0; i < N; i++) cout << arr[i] << " ";
cout << "\n\n";
}
int main(void)
{
srand(time(NULL));
int arr[MAX_ARR];
for (int i = 0; i < MAX_ARR; i++)
arr[i] = (rand() % 1000) + 1;
print(arr, MAX_ARR, "[PREV]");
mergeSort(arr, 0, MAX_ARR - 1);
print(arr, MAX_ARR, "[NEXT]");
return 0;
}
6. 힙정렬 (Heap Sort)
최대 힙 트리/최소 힙 트리를 구성하여 정렬
최대/최소 값 구할 때 유용
안정성 보장 X
시간복잡도 : O(NlongN)
#include <iostream>
#include <queue>
#include <functional> // greater, less
using namespace std;
int main() {
priority_queue<int> pq; // - > priority_queue<int, vector<int>, less<int>> pq;
// 우선순위 큐에 원소를 삽입 (push) 한다
pq.push(4);
pq.push(7);
pq.push(3);
pq.push(1);
pq.push(10);
cout << "우선순위 큐 사이즈 : " << pq.size() << "\n";
// 우선순위 큐가 비어 있지 않다면 while 문을 계속 실행
while (!pq.empty()) {
cout << pq.top() << '\n';
pq.pop();
}
return 0;
}
#include <iostream>
using namespace std;
//힙정렬
int n, heap[10000001];
void heapify(int i)
{
int cur = 2 * i;
if(cur < n && heap[cur] < heap[cur+1]) cur++;
if(heap[i] < heap[cur])
{
swap(heap[i],heap[cur]);
if(cur <= n/2) heapify(cur);
}
}
void heapsort(int i)
{
swap(heap[1],heap[i]);
int root = 1;
int cur = 2;
while(cur/2<i)
{
cur = 2*root;
if(cur < i-1 && heap[cur] < heap[cur+1]) cur++;
if(cur < i && heap[root] < heap[cur])
swap(heap[root],heap[cur]);
root = cur;
}
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d",&heap[i]);
for(int i = n/2; i > 0; i--) // 최초 heap 생성
heapify(i);
for(int i = n; i > 0; i--) // heap 정렬
heapsort(i);
for(int j = 1; j <= n; j++) // 출력
printf("%d ",heap[j]);
}
7. 계수정렬 (Counting Sort)
각 항목을 세어 저장해두고, 이를 앞 순서대로 정렬
- 예를 들어, [3,4,1,2,4,6,1] 배열을 정렬한다고 했을 때,
- 해당 배열에서 각 숫자가 몇 개 나오는 지 세어보면 아래와 같습니다.
1 : 2개
2 : 1개
3 : 1개
4 : 2개
6 : 1개
- 그리고 1부터 6까지 갯수대로 나열 → [1,1,2,3,4,4,6]
안정성 보장 O
시간복잡도 : O(N)
메모리 낭비 심할 수 있음 (k가 크면)
int main(void){
int count[5] = {0,0,0,0,0};
int data[20] = {
1,4,2,5,3,
2,3,4,5,2,
2,2,3,4,1,
4,2,5,5,1
};
// 반복문 한번으로 정렬 완료
for(int i=0; i<20; i++){
count[data[i]-1]++;
}
// 결과 출력
for(int i=0; i<5; i++){
if(count[i] != 0){
// 0일때는 출력 안해도 되니깐
for(int j=0; j<count[i]; j++) {
printf("%d ", i+1);
}
}
}
return 0;
}
'algorithm > 정리' 카테고리의 다른 글
| 이분탐색 (0) | 2024.04.05 |
|---|---|
| 99클럽 코테 스터디 5일차 TIL - 자바 map 관련 함수 (getOrDefault, equals) (1) | 2024.04.05 |
| Backtracking (0) | 2024.04.03 |
| 99클럽 코테 스터디 3일차 TIL - java String / java 약수 구하기 최적화 알고리즘 (0) | 2024.04.03 |
| 기본 자료구조 - 해시, 트리, 힙 (0) | 2024.03.31 |