정렬 - 삽입, 선택, 버블, 쉘, 합병

오른차순 / 내리차순

 

정렬 알고리즘 평가 

--> 비교 횟수

--> 이동 횟수

 

단순 & easy, but 비효율적 : 삽입 정렬, 버블 정렬, 선택 정렬

복잡 & difficult, but 효율적 : 퀵 정렬, 힙 정렬, 합병 정렬

---

삽입 정렬

 

정렬된 부분에 새로운 데이터 삽입

정렬 안된 부분에서 작은 수 가져오기

 

삽입 정렬

// 삽입정렬
void insertion_sort(int list[], int n)       	
{   
   int i, j, key;
   for(i=1; i<n; i++){
   	key = list[i];//비교 대상 (current)
	for(j=i-1; j>=0 && list[j]>key; j--) //key 값이 previous(j)보다 작으면
		list[j+1] = list[j]; 		// 레코드의 오른쪽 이동
    	list[j+1] = key;
   }
}

 

복잡도 : O(n^2)

 

최선의 경우 O(n) : 이미 정렬되어 있는 경우

– 비교 : n-1 번

– 이동 : 없음

 

최악의 경우 O(n^2) : 역순으로 정렬되어 있는 경우

–모든 단계에서 앞에 놓인 자료 전부를 이동

비교)

이동)

단점

– 많은 이동이 필요하므로 레코드가 클 경우 불리

---

선택 정렬

 

정렬 안 된 부분(오른쪽)에서 최솟값 --> 정렬된 부분(왼쪽)으로 (자리 교체) --> 오른쪽 부분 데이터 없을 때까지 반복

 

 

선택 정렬

#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) //자리 교체 
void selection_sort(int list[], int n)
{
   int i, j, least, temp;

   for(i=0; i<n-1; i++) {
   
      least = i; //최솟값 (처음은 맨 앞)
      for(j=i+1; j<n; j++) 		// 최솟값 탐색(정렬 부분 그 뒤 레코드부터~n)
         if(list[j]<list[least]) least = j; //최솟값 갱신

      SWAP(list[i], list[least], temp); // 가장 작은 수를 왼쪽에 넣기
   }
}

 

복잡도 : O(n^2)

 

비교 횟수

– (n - 1) + (n - 2) + … + 1 = ∑_(i=1)^(n-1)▒i=  (n(n-1))/2=O(n^2)

 

이동 횟수

– 3(n - 1)

 

특징

– 입력에 민감하지 않다.

– 효율성이 떨어진다.

---

버블 정렬

인접한 2개 비교 -> 작은 수를 앞으로 (1cycle-> 가장 큰 수가 뒤로 -> 반복)

버블 정렬

#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) //자리 교체 메크로

void bubble_sort(int list[], int n)
{
   int i, j, temp;

   for(i=n-1; i>0; i--){      // 데이터가 n개일 때 n-1 회 반복
		for(j=0; j<i; j++) 	// 앞뒤의 레코드를 비교한 후 교체
	      if(list[j]>list[j+1])   //앞 레코드가 더 크면
     		    SWAP(list[j], list[j+1], temp); //자리 교체
   }
}

 

복잡도 :  O(n^2)

 

비교 횟수(최상, 평균, 최악의 경우 모두 일정)

– O(n^2)

 

이동 횟수

– 이동 횟수 = 3 * 비교 횟수

– 이미 정렬된 경우(최선의 경우) :  이동 횟수 = 0

 

단점

– 데이터의 이동이 많다.

– 컴퓨터에게 이동은 비교보다 많은 시간이 소요된다.

---

쉘 정렬

삽입 정렬이 어느 정도 정렬된 리스트에서 대단히 빠른 것에 착안

 

절차

 

– 전체 리스트를 일정 간격(gap)의 부분 리스트로 나눈다. --> 각각의 부분 리스트를 삽입 정렬

– 간격을 줄임

• 부분 리스트의 수는 작아지고 각 부분 리스트의 크기는 더 커진다

– 간격이 1이 될 때까지 반복

 

쉘 정렬

// gap 만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last

inc_insertion_sort(int list[], int first, int last, int gap) //각 부분 리스트 삽입 정렬
{
	int i, j, key;
	for(i=first+gap; i<=last; i=i+gap){
		key = list[i];
		for(j=i-gap; j>=first && key<list[j];j=j-gap)
			list[j+gap]=list[j];
		list[j+gap]=key;
	}
}
void shell_sort( int list[], int n )
{
	int i, gap;
	for( gap=n/2; gap>0; gap = gap/2 ) { //간격: 5->3->1
		if( (gap%2) == 0 ) gap++;
		for(i=0;i<gap;i++)		// 부분 리스트의 개수는 gap (i=0~5/0~3/0~1)
			inc_insertion_sort(list, i, n-1, gap); //0,9,5
	}
}

 

복잡도 : O(n^1.5) , 최악은 O(n^2)

---

합병 정렬

 

리스트 -> 2개로 균등 분할 & 정렬하면서 합병

분할 정복 (divide and conquer)방법

 

 

합병 정렬

merge_sort(list, left, right){
   if (left < right)
      mid = (left+right)/2; //반으로 나누고
      merge_sort(list, left, mid); //앞 부분 또 나누기 (재귀)
      merge_sort(list, mid+1, right); //뒷 부분 나누기
      merge(list, left, mid, right); //합병
   }

merge(list, left, mid, right){
   i←left; j←mid+1; k←left;
   while i≤left and j≤right do
      if(list[i]<list[j]) 
         sorted[k]←list[i];
         k++; i++;
      else
         sorted[k]←list[j];
         k++; j++;
   요소가 남아있는 부분배열을 sorted로 복사;
   sorted를 list로 복사;
   }

 

복잡도 : O(n log n⁡)

 

비교) log n 으로 분할 (높이) & n번 비교

 

이동) 각 패스 2n번 이동 --> 전체 2n * logn

---