정렬 알고리즘 (1) (버블, 선택, 병합(합병) 정렬)

목차

---

• 정렬 알고리즘 이란?
• 버블 정렬 설명 및 코드 구현
• 선택 정렬 설명 및 코드 구현
• 병합(합병) 정렬 설명 및 코드 구현
• 버블, 선택, 병합(합병) 정렬의 시간 복잡도

 

 

정렬 알고리즘 이란?

---

정렬 알고리즘 이란 원소들을 번호순이나 사전순서와 같이 일정한 순서대로 정렬하는 알고리즘이다.

정렬 알고리즘이 존재하는 이유는 탐색의 효율성 때문이다.

수많은 데이터들을 탐색할 때, 무작위로 섞여 있는 데이터를 탐색하는 것보다 정렬되어 있는 데이터를 탐색하는 것이 훨씬 효율적이고 활용성에 있어서도 용이하다.

정렬 알고리즘은 매루 많지만, 그 중에서 버블, 선택, 병합(합병) 정렬에 대해 다룰 것이다.

 

 

버블 정렬 설명 및 코드 구현

---

1) 버블 정렬 이란?

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식의 정렬 알고리즘이다.

즉 두 개씩 비교하며, (오른차순으로 정렬한다면) 더 작은 값을 왼쪽에 배치하는 정렬이다.

 

그림으로 설명하자면,

버블 정렬 이미지화

[1차 교환]

첫 번째, 5381 에서 53 비교 → 5 > 3 이므로 3581로 교환한다.

두 번째, 3581에서 58 비교 → 5 < 8 이므로 교환하지 않는다.

세 번째, 3581에서 81 비교 → 8 > 1 이므로 3518로 교환한다.

[2차 교환]

첫 번째, 3518에서 35 비교 → 3 < 5 이므로 교환하지 않는다.

두 번째, 3518에서 51 비교 → 5 > 1 이므로 3158로 교환한다.

[3차 교환]

첫 번째, 3158에서 31 비교 → 3 > 1 이므로 1358로 교환한다.

[4차 교환]

정렬이 모두 완료되어 알고리즘 종료.

 

 

2) C언어로 버블 정렬 구현하기

소스 코드

/*
Bubble_Sort 함수 설명
1. arr[]은 정렬할 배열
2. len은 정렬할 배열의 길이
*/
void Bubble_Sort(int arr[], int len) {

	int temp = 0;
	int n = len;


	while (n != 0) {
		for (int i = 0; i < len - 1; i++) {
			if (arr[i] > arr[i + 1]) {
				temp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = temp;
			}
		}
		n = n - 1;
	}

}

 

실행 결과

 

 

선택 정렬 설명 및 코드 구현

---

1) 선택 정렬이란?

선택 정렬이란 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.

즉 배열을 오른차순으로 정렬한다고 할 때, 전체 배열에서 가장 작은 수를 첫 번째 위치와 교환하는 것이다. 그 다음 두 번째로 작은 수를 두 번째 위치와 교환하는 것이다. 이 방식을 반복하며 배열을 정렬한다.

 

그림으로 설명하면,

선택 정렬 이미지화

첫 번째, 배열 중 1이 가장 작으므로 첫 번째 숫자와 위치 교환한다.

두 번째, (1을 제외한) 배열 중 2가 가장 작으므로 두 번째 숫자와 위치 교환한다.

세 번째, (1, 2를 제외한) 배열 중 3이 가장 작으므로 세 번째 숫자와 위치 교환한다.

네 번째, (1, 2, 3을 제외한) 배열 중 5가 가장 작으므로 네 번째 숫자와 위치 교환한다.

다섯 번째, (1, 2, 3, 5를 제외한) 배열 중 7이 가장 작으므로 다섯 번째 숫자와 위치 교환한다.

여섯 번째, 배열 정렬 완료

 

2) C언어로 선택 정렬 코드 구현

소스 코드

/*
Selection_sort 함수 설명
1. arr[]은 정렬할 배열
2. len은 정렬할 배열의 길이
*/
void Selection_sort(int ar[], int len) {

	int min;
	int temp = 0;

	for (int j = 0; j < len; j++) {
		min = j;
		for (int i = j; i < len; i++) {
			if (ar[i] < ar[min]) {
				min = i;
			}
		}

		temp = ar[min];
		ar[min] = ar[j];
		ar[j] = temp;

	}


}

 

실행 결과

 

 

병합(합병) 정렬 설명 및 코드 구현

---

1) 병합(합병) 정렬 이란?

병합(합병) 정렬은 이진 검색과 같이 반으로 나누어 간다는 것에서 공통점이 있다.

병합(합병) 정렬이란 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합치면서 정렬하는 방식이다.

 

그림으로 설명 하자면, 

병합(합병) 정렬 이미지화

첫 번째, [21, 10, 12, 20, 25, 13, 15, 22] 배열을 [21], [10], [12], [20], [25], [13], [15], [22] 와 같이 원소 한개로 분할한다.

두 번째, [10, 21] / [12, 20] / [13, 25] / [15, 22] 와 같이 인접한 2개의 부분 리스트끼리 정렬한다.

세 번째, [10, 12, 20, 21] / [13, 15, 22, 25] 와 같이 인접한 2개의 부분 리스트끼리 정렬한다.

네 번째, [10, 12, 13, 15, 20, 21, 22, 25] 와 같이 인접한 2개의 부분 리스트끼리 정렬한다. 정렬 끝.

 

2) C언어로 병합(합볍) 정렬 코드 구현

소스 코드

void mergeSort(int low, int high) {
    int mid;
    if(low < high) {
        mid = (low + high)/2;
        mergeSort(low, mid);
        mergeSort(mid+1, high);
        merge(low, mid, high);
	}
}

void merge(int low, int mid, int high) {

    int i = low;
    int j = mid+1;
    int k = low;

    while (i<=mid && j<=high) {
        if(mergeArr2[i] < mergeArr2[j]) {
           mergeArr1[k++] = mergeArr2[i++];
        } else if(mergeArr2[i] >= mergeArr2[j]) {
           mergeArr1[k++] = mergeArr2[j++];
        }
    }

 

    // 남은 영역 조사후 mergedArr으로 복사

    if(i>=mid) {
        while(j<=high) {
           mergeArr1[k++] = mergeArr2[j++];
        }
    }

    if(j>=high) {
        while(i<=mid) {
           mergeArr1[k++] = mergeArr2[i++];
        }
    }
    copyArray(low, high);
}

 

// 배열 출력 함수 

void printArr(int a[], int n) {
     int i;
     for (i=0; i<n; i++) {
        printf("%d ", a[i]);
     }
     printf("\n");
}

 

void copyArray(int start, int end) {
    int i;
    for (i=start; i<=end; i++) {
        mergeArr2[i] = mergeArr1[i];
    }
}

(위 병합 정렬 코드는 https://coding-factory.tistory.com/136를 참고했습니다.)

 

 

버블, 선택, 병합(합병) 정렬의 시간 복잡도

---

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