반응형
//삽입정렬, 선택 정렬, 버블 정렬, 병합정렬, 퀵정렬,힙정렬,기수정렬,위상정렬
#include<iostream>
using namespace std;
//선택정렬 -하나를 기준으로두고, 그외 나머지에서 우선순위 있는 것을 고른다.
//시간복잡도 O(n^2)
void selectSort(int *arr, int size)
{
for (int i = 0; i < size - 1; i++)
{
int temp = i;
for (int j = i + 1; j < size; j++)
{
if (arr[temp] > arr[j])temp = j;
}
swap(arr[i], arr[temp]);
}
}
//버블정렬-서로 이웃한 데이터들을 비교하며 큰데이터를 가장 뒤로 보내 정렬하는방식(오름차순기준)
//시간복잡도 O(n^2)
void bubbleSort(int *arr, int size)
{
for (int i = 0; i < size - 1; i++)
{
for (int j = 0; j < size - 1 - i; j++)
{
if (arr[j] >arr[j + 1])
{
swap(arr[j], arr[j + 1]);
}
}
}
}
//삽입정렬-삽입정렬은 key값을 갖는다. key값을 기준으로 이전데이터를 살펴보면서 정렬하는방식
//이미정렬된 데이터라면 시간복잡도는 O(n),최악(n^2)
////선택정렬과 버블정렬의 다른점- 모든것을 비교하지 않고 자기기준에 맞는 부분까지만 비교 정렬 그렇기때문에 최선은 O(N)
void insertSort(int *arr, int size)
{
for (int i = 1; i < size; i++)
{
int key = arr[i];
int j;
for (j = i - 1; j >= 0; j--)
{
if (key < arr[j])arr[j + 1] = arr[j];
else break;
}
arr[j + 1] = key;
}
}
//퀵정렬-분할정복에 근거하여 만들어진 방법
//피벗을 기준으로 작거나 같은은 값을 가진 데이터는 앞으로
//큰값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰값을 갖는 데이터로 분리해가며 정렬하는 방법
//pivot 설정이 가장 왼쪽인것보다 pivot설정을 데이터기준의 중간값으로
//설정하는것이 좋다.
//예 >왼쪽을 pivot으로 계속 설정한다면 최악의 경우 1 2 3 4 5 6 7 8 9
//시간복잡도 O(nΛ2)이가 된다.ㅜㅜ
//pivot을 mid로 하여 결정할때 : 분할횟수, 이동연산 포함하면
//분할정복처럼 O(N*log2n)
//*분할정복- 똑같은 문제를 여러개의 부분문제로 나누어 해결하여 원래 문제의 해를 구하는 방식
void Qsort(int *arr, int l, int r, int size)
{
int pivot = (l + r) / 2;
int Left = l;
int Right = r;
while (Left <= Right)
{
while (arr[Left] < arr[pivot] && Left < size)Left++;
while (arr[pivot]<arr[Right] && Right>-1)Right--;
if (Left <= Right)
{
swap(arr[Left], arr[Right]);
Left++;
Right--;
}
}
if (Left < r)Qsort(arr, Left, r, size);
if (l < Right)Qsort(arr, l, Right, size);
}
//병합정렬- 데이터가 1개 남을때까지 분할 하고 ,실제 정렬은 나눈것을 병합하는 과정에서
//데이터수가 8개일때 병합의 과정은 3회 진행되었다.
//마찬가지로 데이터수가 16개일때 병합의 과정은 4회 진행된다.
//즉 데이터 수 n과 그에 따른 병합과정의 횟수 K에는 다음식이 성립된다.
//빅오 연산은 O(N*log2n)이 된다 ,최악의경우에도 같다.
void MergeTwoArea(int arr[], int left, int mid, int right)
{
int fidx = left;
int ridx = mid + 1;
int sidx = left;
int temp[100] = { 0, };// 원래는..동적으로만들기
//temp에 왼쪽오른쪽 인덱스비교해가면서 작은거 넣기
while (fidx <= mid &&ridx <= right)
{
if (arr[fidx] < arr[ridx])
{
temp[sidx++] = arr[fidx++];
}
else
temp[sidx++] = arr[ridx++];
}
//한쪽에 몰려있어서 탐색이끝난경우 나머지 값들 넣어주기
if (fidx > mid)
{
for (int i = ridx; i <= right; i++, sidx++)
{
temp[sidx] = arr[i];
}
}
else
{
for (int i = fidx; i <= mid; i++, sidx++)
{
temp[sidx] = arr[i];
}
}
for (int i = left; i <= right; i++)
{
arr[i] = temp[i];
}
//위에서 만든 temp 동적으로 만들엇다면 아래서 free 써서 해제해야딤
}
void MergeSort(int arr[], int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);//분할
MergeTwoArea(arr, left, mid, right); //병합
}
}
//기수정렬
//기수 정렬도 대단히 빠릅니다.자리수를 비교해서 정렬하는 방식인데요.그래서 단점이라면 자리수가 없는 것들은 정렬할 수 없습니다.예를 들면 부동소수점같은 경우가 있겠네요.하지만 문자열과 정수는 거의 다 정렬할 수 있습니다.
//복잡도는 O(dn)인데요.d는 가장 큰 데이터의 자리수입니다.예를 들면 가장 큰 수가 10000이면 자리수는 5니까 O(5n)이 됩니다.
//< 기수정렬 ( 큐 사용버젼 )
#include<queue>
#define BUCKET 10
void radixSort_Queue(int* arr, int size)
{
//< 큐를 사용 ( 버킷수 만큼 )
queue<int> qu[BUCKET];
//< 인수
int factor = 1;
//< 최대값
int max = 0;
//< 정렬 단계
int count = 1;
//< 버킷 인덱스
int index = 0;
//< 최대값을구한다.
for (int i = 0; i<size; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
//< 최대값자리수만큼반복
while ((max / factor) > 0)
{
//< 자릿수에 따른 배열 데이터를 버킷에 분배
for (int i = 0; i<size; i++)
{
index = (arr[i] / factor) % 10;
qu[index].push(arr[i]);
}
//< 버킷에 있는 순서대로 배열에 넣기
index = 0;
for (int i = 0; i<BUCKET; i++)
{
//< 버킷에 데이터가 존재하면
while (qu[i].empty() == false)
{
//< 버킷에 데이터를 꺼내어 배열에 저장한후 버킷 데이터 삭제
arr[index++] = qu[i].front();
qu[i].pop();
}
}
//< 다음자리수
factor *= 10;
}
}
int main()
{
}반응형
