정렬 알고리즘 (2) (삽입, 퀵 정렬)

목차

---

• 삽입 정렬 설명 및 코드 구현
• 퀵 정렬 설명 및 코드 구현
• 삽입 정렬과 퀵 정렬의 시간 복잡도

 

 

삽입 정렬 설명 및 코드 구현

---

1) 삽입 정렬이란?

삽입 정렬이란 각각의 원소들이 자신의 위치를 찾아서 삽입되는 정렬이다.

그림으로 설명하면,

삽입 정렬 이미지화

정렬을 시작할 때, 가장자리에 있는 숫자를 기준으로 정렬을 시작한다. 위 그림에서는 4를 기준으로 정렬을 시작한다.

① 3 < 4 이므로, 3은 4보다 앞에 배치된다.

② 2 < 3 이므로. 2는 3보다 앞에 배치된다.

③ 10 > 4 이므로, 그대로 있는다.

④ 12 > 10 이므로, 그대로 있는다.

⑤ 1 < 2 이므로, 1은 2보다 앞에 배치된다.

⑥ 4 < 5 < 10 이므로, 5는 4와 10 사이에 배치된다.

⑦ 5 < 6 < 10 이므로, 6은 5와 10 사이에 배치된다. 정렬 끝.

 

2) C언어로 삽입 정렬 구현하기

- 소스 코드

/*
Insertion_Sort 함수 설명
1. arr[]은 정렬할 배열
2. len은 정렬할 배열의 길이
*/

void Insertion_Sort(int arr[], int len) {

	int i, j, temp;
	
	for(i = 0; i < len; i++) {
		temp = arr[i];
		j = i;
		
		while ((j > 0) && (arr[j - 1] > temp)) {
			arr[j] = arr[j - 1];
			j = j - 1;
		
		}
		
		arr[j] = temp;
	}


}

 

- 실행 결과

 

 

퀵 정렬 설명 및 코드 구현

---

1) 퀵 정렬 이란?

퀵 정렬이란 임의의 값(pivot)을 기준으로, 왼쪽은 pivot 보다 작은 값을 두고 오른쪽은 pivot보다 큰 값을 두는 정렬 알고리즘이다.

pivot을 기준으로 좌, 우측을 정렬하는 것을 재귀적으로 반복하며 정렬을 완성한다.

정렬 알고리즘 중에 퀵 정렬이 가장 빠르고 효율적이다.

 

그림으로 설명 하기 전에 퀵 정렬 규칙을 간단히 소개 하면,

- i > pivot : 움직이지 않는다.

- i < pivot : 오른쪽으로 한칸

- j > pivot : 왼쪽으로 한칸

- j < pivot : 움직이지 않는다.

- i > pivot 이고 j < pivot : i 와 j 의 숫자를 교환한다.

 

①  [4, 8, 2, 3, 9, 7, 1, 6, 10, 5] 배열이 있다.

 

② 4를 pivot 값으로 한다.

③ i(8) > pivot(4) 이므로 움직이지 않고, j(5) > pivot(4) 이므로 j는 왼쪽으로 움직인다.

 

④  i(8) > pivot(4) 이고 j(1) < pivot(4) 이므로 움직이지 않고, 서로 숫자를 교환한다.

 

⑤ j(3) < pivot(4), i(9) > pivot(4) 이고 더 이상 이동할 수 없으므로 i, j 이동을 멈춘다.

 

⑥ j(3) 와 pivot(4) 의 위치를 교환한다.

⑦ pivot(4) 을 기준으로, 좌측은 pivot(4) 보다 작은 값이고 우측은 pivot(4) 보다 큰 값으로 정렬되었다.

 

⑧ 새로운 pivot 값을 지정하여 재귀적으로 반복하다 보면, 정렬이 완료된다.

 

2) C언어로 퀵 정렬 코드 구현하기

- 소스 코드

/*
Quick_sort 함수 설명
1. arr[]은 정렬할 배열
2. begin은 pivot을 제외한 왼쪽 배열
3. end는 pivot을 제외한 오른쪽 배열
*/

void Quick_sort(int arr[], int begin, int end) {

	int p;

	if (begin < end) {
		p = partition(arr, begin, end);
		Quick_sort(arr, begin, p - 1);
		Quick_sort(arr, p + 1, end);

	}
}


int partition(int arr[], int begin, int end) {

	int pivot, temp, L, R, t;


	L = begin;
	R = end;
	pivot = (int)((begin + end) / 2);


	while (L < R) {
		while ((arr[L] < arr[pivot]) && (L < R)) L++;
		while ((arr[R] >= arr[pivot]) && (L < R)) R--;

		if (L < R) {
			temp = arr[L];
			arr[L] = arr[R];
			arr[R] = temp;

			if (L == pivot) {
				pivot = R;
			}
		}
	}

	temp = arr[pivot];
	arr[pivot] = arr[R];
	arr[R] = temp;

	return R;
}

 

- 실행 결과

 

 

삽입 정렬과 퀵 정렬의 시간 복잡도

---

Big-O (빅-오)

Big-O 종류	의미	예시
O(2ⁿ)	n개를 입력했을 때, 최악의 경우 2ⁿ번 실행된다.
O(n³)	n개를 입력했을 때, 최악의 경우 n³번 실행된다.
O(n²)	n개를 입력했을 때, 최악의 경우 n²번 실행된다.	버블 정렬  선택 정렬  삽입 정렬 퀵 정렬
O(n log n)	n개를 입력했을 때, 최악의 경우 n log n번 실행된다.	병합(합병) 정렬
O(n)	n개를 입력했을 때, 최악의 경우 n번 실행된다.	선형 검색
O(log n)	n개를 입력했을 때, 최악의 경우 log n번 실행된다.	이진 검색
O(1)	n개를 입력했을 때, 최악의 경우 1번 실행된다.

 

Big-Ω (빅-오메가)

Big-Ω 종류	의미	예시
Ω(2ⁿ)	n개를 입력했을 때, 최선의 경우 2ⁿ번 실행된다.
Ω(n³)	n개를 입력했을 때, 최선의 경우 n³번 실행된다.
Ω(n²)	n개를 입력했을 때, 최선의 경우 n²번 실행된다.	버블 정렬  선택 정렬
Ω(n log n)	n개를 입력했을 때, 최선의 경우 n log n번 실행된다.	병합(합병) 정렬 퀵 정렬
Ω(n)	n개를 입력했을 때, 최선의 경우 n번 실행된다.	삽입 정렬
Ω(log n)	n개를 입력했을 때, 최선의 경우 log n번 실행된다.
Ω(1)	n개를 입력했을 때, 최선의 경우 1번 실행된다.	선형 검색 이진 검색

 

 

 

---

위 글은 edwith 사이트의 <cs50> 강의 시청과

부스트 코딩 뉴비 챌린지 2020 활동 팀원들과 토론을 통해 공부한 내용을 작성한 것 입니다.

내용상 오류가 있다면 댓글로 적어주세요. 🖐

2020/07/23 - [Life/2020] - [대외활동] 부스트 코딩 뉴비 챌린지 2020

[대외활동] 부스트 코딩 뉴비 챌린지 2020