[자료구조] 7. Sorting

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; //합병된 리스트의 시작인덱스 리턴
}