자료구조 병합정렬 , 셸정렬

---

참고자료

https://jung-story.tistory.com/5?category=826491 

자료구조 (Linked list) - 알고리즘 & 자료구조 C언어

https://jung-story.tistory.com/6?category=826491 

자료구조 선택정렬, 버블정렬, 삽입정렬

 

---

정렬 알고리즘 시간복잡도

• 저번에는 삽입 정렬, 버블 정렬, 선택 정렬에 대해서 알아보았습니다.
• 오늘은 병합정렬,셸정렬에 대해서 알아보기 전에 각각 정렬들에 대해서 시간 복잡도를 알아보겠습니다.

 

Name	Best	Avg	Worst	Run-time (단위:sec)
삽입정렬	n	n^2	n^2	7438
선택정렬	n^2	n^2	n^2	10842
버블정렬	n^2	n^2	n^2	22894
셸 정렬	n	n^1.5	n^2	0.056
퀵 정렬			n^2	0.014
힙 정렬				0.034
병합정렬				0.026

 

• 삽입 정렬, 선택 정렬, 버블 정렬은 단순(구현 간단)하지만 비효율적인 방법입니다.
• 반면에 퀵 정렬, 힙 정렬, 병합 정렬은 복잡하지만 효율적인 방법입니다.
  
  

 

---

셸 정렬

 

#include <stdio.h>
void shellSort(int arr[], int);
void intervalSort(int arr[], int, int, int);

void shellSort(int arr[], int size) {
	int interval;
	interval = size / 2;
	while (interval >= 1) {

		for (int i = 0; i < interval; i++) {
			intervalSort(arr, i, size - 1, interval);
		}
		printf("\n interval = %d \n", interval);
		for (int t = 0; t < size; t++) {
			printf("%2d,", arr[t]);
		}
		printf("\n");
		interval = interval / 2;
	}
}

void intervalSort(int arr[], int begin, int end, int interval) {
	int item, j, i;
	for (i = begin + interval; i <= end; i += interval) {
		item = arr[i];
		for (j = i - interval; j >= begin && item < arr[j]; j -= interval) {
			arr[j + interval] = arr[j];
		}
		arr[j + interval] = item;
	}
}
int main() {
	int size = 8;
	int arr[] = { 88,45,71,10,46,77,100,19 };
	shellSort(arr, 8);

}

 

---

셸 정렬 결과

 

셸 정렬후

 

 

---

병합정렬

 

#include<stdio.h>


int A[10000];

int MergeSort(int A[], int p, int q);

int Merge(int A[], int p, int q, int r);

int main()

{

	int number;

	printf("배열 크기 입력 :");

	scanf_s("%d", &number);

	for (int i = 1; i <= number; i++)

	{

		printf("%d번째 배열값 입력 :", i);

		scanf_s("%d", &A[i]);

	}

	MergeSort(A, 1, number);

	for (int j = 1; j <= number; j++)

	{

		printf("[%d],", A[j]);

	}

}

int MergeSort(int A[], int p, int r)

{

	int q;

	if (p<r)

	{

		q = (p + r) / 2;

		MergeSort(A, p, q);

		MergeSort(A, q + 1, r);

		Merge(A, p, q, r);

	}

}

int Merge(int A[], int p, int q, int r)

{

	int temp[10000];

	int i = p;

	int j = q + 1;

	int t = 1;

	while (i <= q && j <= r)

	{

		if (A[i] <= A[j])

		{

			temp[t++] = A[i++];

		}

		else

		{

			temp[t++] = A[j++];

		}

	}

	while (i <= q)

	{

		temp[t++] = A[i++];

	}

	while (j <= r)

	{

		temp[t++] = A[j++];

	}

	i = p;

	t = 1;

	while (i <= r)

	{

		A[i++] = temp[t++];

	}

}

 

---

병합 정렬 결과

 

병합정렬 출력

 

---