정렬

ㅅㅇㄱ·2024년 9월 28일

CS

목록 보기

19/19

레코드들을 주어진 키 값에 따라 순서화되도록 재배치하는 것

안정성
- 입력 데이터에 동일한 키 값을 갖는 레코드가 여러 개 존재할 경우, 이들의 상대적인 위치가 정렬후에도 바뀌지 않음을 의미함

	최선	평균	최악	안정성
선택정렬	O( $n^2$ )	O( $n^2$ )	O( $n^2$ )	X
삽입정렬	O(n)	O( $n^2$ )	O( $n^2$ )	O
버블정렬	O( $n^2$ )	O( $n^2$ )	O( $n^2$ )	O
퀵정렬	O( $nlog2n$ )	O( $nlog2n$ )	O( $n^2$ )	X
합병정렬	O( $nlog2n$ )	O( $nlog2n$ )	O( $nlog2n$ )	O
힙정렬	O( $nlog2n$ )	O( $nlog2n$ )	O( $nlog2n$ )	X
기수정렬	O(dn)	O(dn)	O(dn)	O
쉘정렬	O(n)	O(n^1.5)	O(n^1.5)	X

선택정렬

최선 : O(n2) 평균 : O(n2) 최악 : O(n2)
안정성여부 : 만족하지 않음

#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++) //	최솟값	탐색
			if(list[j] < list[least])	least = j;
		SWAP(list[i], list[least], temp);
	}
}

삽입정렬

최선 : O(n) 평균 : O(n^2) 최악 : O(n^2)
안정성여부 : 만족

void insertion_sort(int	list[],	int	n)	{			
	int	i, j, key;
	for(i = 1; i < n; i++) {
	  key = list[i];
	  for(j	= i-1; j >= 0 && list[j] > key; j--)
		list[j+1] = list[j]; //	레코드의 오른쪽 이동
	  list[j+1] = key;
	}
}

레코드마다 올바른 자리까지 한칸씩당겨오는 방식

버블정렬

최선 : O(n^2) 평균 : O(n^2) 최악 : O(n^2)
안정성여부 : 만족

#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--){
      for(j = 0; j < i; j++) //앞뒤의 레코드 비교 후 교체
          if(list[j] > list[j+1])
             SWAP(list[j], list[j+1], temp);
   }
}

앞뒤 레코드를 비교해 레코드를 한칸씩 교환하며 올바른 자리를 찾는 방식

퀵정렬 : 분할-정복기법

최선 : O(nlog2n) 평균 : O(nlog2n) 최악 : O(n2)
안정성여부 : 만족하지 않음

int quick_sort(int list[], int left, int right) {
   int pivot, temp, i, j;
   if(left < right) {
      i = left;
      j = right + 1;
      pivot = list[left];
      do {
         while(list[++i] < pivot);
         while(list[--j] > pivot);
         if(i < j) SWAP(list[i], list[j], temp);
      } while(i < j);
      SWAP(list[left], list[j], temp); 
      quick_sort(list, left, j-1);
      quick_sort(list, j+1, right);
   }
}

피벗을 정한후 그 피벗보다 큰부분, 작은부분으로 나눈다
피벗을 제외한 두 부분에 똑같이 반복한다
나누어진 리스트가 더 이상 나눌수 없을때까지 반복한다
다 이어붙이면 정렬되있다

합병 정렬 : 분할-정복 기법

최선 : O(nlog2n) 평균 : O(nlog2n) 최악 : O(nlog2n)
안정성여부 : 만족

int sort[MAX]; //추가공간 필요
void merge(int list[], int left, int mid, int right) {
   int i, j, k, l;
   i = left; j = mid+1; k = left;
   /* 분할 정렬된 list의 합병*/
   while(i <= mid && j <= right) { 
      if(list[i] <= list[j]) sort[k++] = list[i++];
      else sort[k++] = list[j++];
   }
  /* 남아있는 레코드의 일괄복사 */
   if(i > mid) for(l = j; l <= right; l++)
                  sort[k++] = list[l];
   else for(l = i; l <= mid; l++)
         sort[k++] = list[l];
   /* sort[]의 리스트를 list[]로 재복사 */
   for(l = left; l <= right; l++)
      list[l] = sort[l];
}
void merge_sort(int list[], int left, int right) {
   int mid;
   if (left < right) {
      mid = (left + right) / 2;
      merge_sort(list, left, mid); //분할
      merge_sort(list, mid+1, right); //분할
      merge(list, left, mid, right); //합병
   }
}

입력된 배열을 같은크기의 2개의 배열로 나눈다
계~~~속 하나씩 떨어질때 까지
두개의 배열을 비교해 합친다
- 각 배열의 첫 원소끼리 비교
다 합치면 정렬되있음

힙 정렬

최선 : O(nlog2n) 평균 : O(nlog2n) 최악 : O(nlog2n)
안정성여부 : 만족하지 않음

힙트리를 이용해 정렬
트리 의 힙 참조

    #define SIZE 8
    void insert_max_heap(int h[], int item, int heap_index) {
       int i = heap_index;
       while((i != 1) && (item > h[i/2])) {
          h[i] = h[i/2]; //부모값을 자식으로 옮김
          i /= 2;
       }
       h[i] = item;
    }
    int delete_max_heap(int h[], int heap_index) {
       int parent, child, item, temp;
       item = h[1]; //가장 큰 값(삭제할 원소)
       temp = h[heap_index]; //마지막 원소값 저장
       parent = 1;  child = 2;
       while(child <= heap_index) {
         if((child < heap_index) && (h[child]) < h[child+1]))
            child++; //자식 중 더 큰값 선택
         if(temp >= h[child]) break;
         h[parent] = h[child]; //자식값을 부모로
         parent = child; //아래단계로 이동
         child *= 2;     //아래단계로 이동
       }
       h[parent] = temp;
       return item;
    }
    void heap_sort(int list[], int n) {
      int i, heap_index = 0;
      int h[SIZE] = {0};
      for(i = 0; i < n; i++) { //최대힙 만들기
        heap_index++;
        insert_max_heap(h, list[i], heap_index);
      }
      for(i = n-1; i >= 0; i--) {
        list[i] = delete_max_heap(h, heap_index);
        heap_index--;
      }
    }
    int main(void) {
      int list[SIZE] = {23, 56, 11, 9, 56, 99, 27, 34};
      heap_sort(list, SIZE); //힙정렬
      for(int i = 0; i < SIZE; i++)
        printf("%d ", list[i]); //정렬 완료 후 출력
    }