Sorting의 응용 분야
- 이진 검색(binary search)
- 두 리스트의 동일성/합집합/차집합/교집합 계산
Stable Sorting
리스트에서 같은 키 값이 여러 개 존재하는 경우, 해당 값의 순서가 sorting 전의 순서로 유지되는 경우
Sort 알고리즘의 종류
- Internal sorting(내부 정렬): 메모리 상에서 정렬
- External sorting(외부 정렬): 리스트 내용이 커서 메모리에 저장될 수 없는 경우 사용
삽입 정렬(Insertion Sort)
void insertion_sort(int list[],int n)
{
int next;
for(int i=1;i<n;i++)
{
next=list[i];
for(int j=i-1;j>=0 && next<list[j];j--)
{
list[j+1]=list[j]; //next값이 들어갈 자리를 찾아 한칸씩 뒤로 밈
}
list[j+1]=next; //next값 삽입
}
}
앞에서부터 정렬된 부분리스트를 만드는 형식이다.
값을 하나씩 잡아서 앞쪽에 정렬된 곳에 알맞은 자리를 찾아 넣는다.
시간복잡도: O(n^2)
Stable 함
데이터의 위치 변경이 빈번하게 일어난다.
모든 데이터가 sorting되어있는 경우라면 O(n)만에 실행이 가능하지만
역순으로 정렬되어 있는경우 효율이 최악이다.
퀵 정렬(Quick Sort)
pivot을 설정하고, 이 pivot값을 기준으로 왼쪽에는 pivot보다 작은 값, 오른쪽에는 pivot보다 큰 값으로 모은다.
나뉘어진 왼쪽과 오른쪽에 관하여 또다시 pivot을 설정하고 반복한다.
void quicksort(int list[],int left,int right)
{
int pivot,i,j;
int temp;
if(left<right)
{
i=left;
j=right+1;
pivot=list[left];
do{
do{
i++;
}while(list[i]<pivot);
do{
j--;
}while(list[j]>pivot);
if(i<j)
SWAP(list[i],list[j],temp);
}while(i<j);
SWAP(list[left],list[j],temp); //pivot을 중간에 놓음
quicksort(list,left,j-1);//왼쪽을 다시 정렬
quicksort(list,j+1,right);//오른쪽을 다시 정렬
}
}
평균적인 경우 시간복잡도: O(nlog2 n)
최악의 경우 O(n^2) ==> 선택한 pivot(위 코드에서는 맨 앞 값)이 리스트의 중간값에서 멀어질수록 비효율적
Non Stable sotring이다
병합 정렬(Merge Sort)
정렬되어있는 두 개의 리스트를 합병하여 하나의 리스트로 만드는 방식이다.
각각의 리스트에서 값을 하나씩 꺼낸다.
비교해서 더 작은것을 sorted[]에 넣는다.
새로운 값을 꺼내 비교한다.
기존 list는 인덱스 i~m / m+1~n 두개로 나뉘어져 있고
이 두 개로 나누어진 리스트를 sorted리스트에 정렬해서 넣는 것이다.
void merge(int list[], int sorted[], int i, int m, int n)
{
int j=m+1;
int k=i;
while(i<=m && j<=n)
{
if(list[i] <= list[j])
sorted[k++]=list[i++]; //list[i]가 더 작은경우
else
sorted[k++]=list[j++];//list[j]가 더 작은경우
}
if(i>m)//j가 남은 경우
for(;j<=n;j++)
sorted[k++]=list[j];
else//i가 남은 경우
for(;i<=m;i++)
sorted[k++]=list[i];
}
위 코드는 병합하는 과정이다
void merge_pass(int list[],int sorted[],int n,int length)
{
int i,j;
for(i=0;i+2*length-1<n;i+=2*length)
merge(list,sorted,i,i+length-1,i+2*length-1);//끝3개 인자는 순서대로 i,m,n
//length길이인 배열을 한 쌍 잡아서 merge함
if(i+length <n) //마지막 한 쌍이 length길이 1개+length보다 적은 양 1개인 경우
merge(list,sorted,i,i+length-1,n-1);
else //남은 쌍이 없거나/한 쌍만 남은경우
for(j=i;j<n;j++)
sorted[j]=list[j]; //그대로 옮김
}
위 코드는 length길이만큼의 배열을 한 쌍씩 묶어 병합한다.
쌍이 딱 맞게 떨어지지 않는 경우가 있을 수 있는데,
length길이의 온전한 배열 1개+ length길이가 되지 않는 작은 배열이 남은 경우,
length길이거나 length보다 작은길이의 배열1개만 남은 경우가 있다.
이 경우는 if-else문을 이용해 처리한다.
void merge_sort(int list[],int n)
{
int length=1;
int extra[MAX_SIZE];
while(length<n){
merge_pass(list,extra,n,length);
length*=2;
merge_pass(extra,list,n,length);
length*=2;
}
}
반복문 안에서 length의 증가가 두번이나 이루어져서 문제가 생기지 않을까 생각할 수 있지만
length가 n보다 커져도 merge_pass에서는 문제없이 수행할것이다.
처음에는 list의 값을 extra에 정렬하고
두번째는 extra의 값을 list에 정렬한다.
최종적으로 정렬된 결과는 list배열에 남을 수 있게 된다.
이 방법은 extra[MAX_SIZE]배열을 만들어 사용하므로 메모리 사용이 크다는 단점이 있다
하지만 퀵정렬과 달리 stable하다는 장점이 있다
Recursive merge sort
int rmerge(element list[],int lower, int upper)
{
int middle;
if(lower>=upper)
return lower;
else{
middle=(lower+upper)/2;
return listmerge(list,rmerge(list,lower,middle),rmerge(list,middle+1,upper));
}
}
int listmerge(element list[],int first,int second)
{
int start=n; //연결리스트의 시작
while(first!=-1 &&second!=-1)
{
if(list[first].key<=list[second].key)
{
list[start].link=first;
start=first;
first=list[first].link;
}
else
{
list[start].link=second;
start=second;
second=list[second].link;
}
}
if(first==-1)//first리스트의 값은 모두 썼고 second리스트만 남은 경우
list[start].link=second;
else
list[start].link=first;
return list[n].link; //합병된 리스트의 시작인덱스 리턴
}
'2022-2 > 자료구조' 카테고리의 다른 글
[자료구조] 7.Sorting: Heap Sort (0) | 2022.12.13 |
---|---|
[자료구조] 그래프 - 작업 네트워크 (1) | 2022.11.29 |
그래프 - 최단거리 (0) | 2022.11.24 |
Biconnected Components/최소 비용 신장트리 (0) | 2022.11.22 |
6장 - 기초적인 그래프 연산들 (1) | 2022.11.18 |
댓글