정렬

버블 정렬

버블정렬 : 버블 정렬은 정렬이 진행되는 모양이 비누거품과 같다고 하여 붙여진 이름이다. 나란히 있는 두개의 데이터를 계속하여 바꾸어 나간다.

• 전체 비교 횟수 : T(n)=n(n-1)/2
• 시간 복잡도 : O(n²)

알고리즘

list에 대한 기본 버블정렬 알고리즘

void bubble_sort(element list[], int n){
	int i, j;
	element next;
	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]}}}}

개선된 버블정렬

• 버블정렬 각 단계에서 데이터의 이동이 일어나지 않으면 다음 단계로 진행할 필요가 없다. 즉 중간과정에서 정렬이 끝나면 더 이상 비교와 교환이 필요없다.

void bubble_sort(element list[], int n){
	int i, j;
	element next;
	for (i=n-1;flag>0;i--){
		flag=0;
		for(j=0;j<i;j++){
			if (list[j]>list[j+1]{
				swap(list[j],list[j+1]
				flag=1;}}}}

• 버블 정렬 : 진행 할 수록 뒤에 정렬되어버림 → 완전 끝까지 할 필요는 없는데 그만 할 수 있으면 그만하자! → 교환하면 깃발 들어! 진행 계속!!
  • 교환 x → flag 진행 그만!

삽입 정렬

• 각 단계에서 list[j]를 앞 방향으로 비교해가면서 교환해 나간다. 더 작은 값이 나오면 멈춘다. j번째 진행될 때는 앞선 데이터는 정렬이 끝난 상태이다.
• 전체 비교횟수 : T(n)=n(n-1)/2
• 시간 복잡도 : O(n²)

알고리즘

void insertion_sort(element list[], int n){
	int i, j;
	element next;
	for(i=1;i<n;i++){
		next=list[i];
		for(j=i-1;j>=0;j-- && next.key <list[j].key;j--)
			{list[j+1]=list[j];};
		list[j+1]=next;
}
}

퀵 정렬

• 정렬 속도가 빠르다.
  • 과정
    1. 리스트에서 기준 데이터 1개를 지정한 다음 리스트의 데이터들을 앞과 뒤 양쪽에서 가운데쪽으로 1개씩 비교하여양쪽에서 비교하여 오기 때문에 이동할 데이터를 찾으면 서로 맞바꾼다.
    2. 기준 데이터보다 큰 값을 리스트 앞에서 찾아서 리스트의 뒤쪽으로 기준데이터보다 작은 값은 리스트의 뒤쪽에서 찾아서 리스트의 앞 쪽으로 둔다.
    3. 첫 번째 과정이 끝나면 두 개의 리스트에 대해서 각각 같은 방법으로 첫번째 과정과 같은 방법으로 분리한다.
• 전체 비교횟수 : T(n)=n
• 시간 복잡도 : O(nlog2n) → 최악시간은 O(n²){이미 정리되어진 상황}

알고리즘

void quicksort(element list[], int left, int right)
{
	int pivot, i, j; element temp;
	if(left<right){
		i=left; j=right+1;
		pivot=list[left].key;
		do{
			do i++;
			while(list[i].key<pivot &&i<=right);
			do j--;
			while(list[j].key>pivot);
				if(i<j)
					SWAP(list[i], list[j], temp);
		}while(i<j);
		SWAP(list[left], list[j], temp);
		quicksort(list, left, j-1);
		quicksort(list,, j+1, right);
}
}

Q 10.3

힙 정렬

• 힙은 트리중에서 부모 노드의 원소 값이 자식 노드의 원소 값보다 큰 완전 이진트리 이다.
  • 힙 구조에서 가잔 큰 값의 위치는 루트에 있으며 가장 작은 값은 리프 노드 중에 있게 된다. 힙은 완전 이진트리이므로 트리 구조이지만 배열에 저장하는 것이 더 효율적이다.

  #define MAX_ELEMENTS 200
  #define HEAP_FULL(n) (n == MAX_ELEMENTS
  #define HEAP_EMPTY(n) (!n)
  
  typedef struct {
  
  int key:
  } element:
  
  element heap[MAX_ELEMENTS];
  int n = 0;
  

  1. 리스트를 배열에 저장하여 힙을 만든다.
     • Adjust 알고리즘(다시 흔들기) 0.5n번 적용하여 완전 이진트리 힙 구성
  2. 힙에서 n개의 데이터를 삭제하고 힙을 재구성하는 과정을 반복한다.
     • Adjust 알고리즘 n-1번 수행
• 시간 복잡도 : O(nlog2n)
  • 재구성 : O(h) : h=트리의 깊이.

알고리즘

재구성 알고리즘

void adjust(element list[], int root, int n) {
int child, rootkey; element temp;
temp = list[root];
rootkey = list[root].key;
child = 2 * root; /* left child */
while(child <= n) {
	if((child < n) &&
		(list[child].key < list[child+1].key))
		child++;
	if(rootkey > list[child].key) break;
	else {
		list[child/2] = list[child];
	child *= 2;}
	}
list[child/2] = temp;
}

알고리즘

void quicksort(element list[], int left, int right)
{
	int pivot, i, j; element temp;
	if(left<right){
		i=left; j=right+1;
		pivot=list[left].key;
		do{
			do i++;
			while(list[i].key<pivot &&i<=right);
			do j--;
			while(list[j].key>pivot);
				if(i<j)
					SWAP(list[i], list[j], temp);
		}while(i<j);
		SWAP(list[left], list[j], temp);
		quicksort(list, left, j-1);
		quicksort(list,, j+1, right);
}
}

Q 10.3

힙 정렬

• 힙은 트리중에서 부모 노드의 원소 값이 자식 노드의 원소 값보다 큰 완전 이진트리 이다.
  • 힙 구조에서 가잔 큰 값의 위치는 루트에 있으며 가장 작은 값은 리프 노드 중에 있게 된다. 힙은 완전 이진트리이므로 트리 구조이지만 배열에 저장하는 것이 더 효율적이다.

  #define MAX_ELEMENTS 200
  #define HEAP_FULL(n) (n == MAX_ELEMENTS
  #define HEAP_EMPTY(n) (!n)
  
  typedef struct {
  
  int key:
  } element:
  
  element heap[MAX_ELEMENTS];
  int n = 0;
  

  1. 리스트를 배열에 저장하여 힙을 만든다.
     • Adjust 알고리즘(다시 흔들기) 0.5n번 적용하여 완전 이진트리 힙 구성
  2. 힙에서 n개의 데이터를 삭제하고 힙을 재구성하는 과정을 반복한다.
     • Adjust 알고리즘 n-1번 수행
• 시간 복잡도 : O(nlog2n)
  • 재구성 : O(h) : h=트리의 깊이.

알고리즘

재구성 알고리즘

void adjust(element list[], int root, int n) {
int child, rootkey; element temp;
temp = list[root];
rootkey = list[root].key;
child = 2 * root; /* left child */
while(child <= n) {
	if((child < n) &&
		(list[child].key < list[child+1].key))
		child++;
	if(rootkey > list[child].key) break;
	else {
		list[child/2] = list[child];
	child *= 2;}
	}
list[child/2] = temp;
}

힙정렬

void heapsort(element list[], int n) {
int i, j;
element temp;
for(i = n / 2; i > 0; i--) /*1*/
adjust (list, i, n);
for(i = n - 1; i > 0; i--) { /*2*/
	SWAP(list[1], list[i + 1], temp);
	adjust (list, 1, i);
	}
}