[알고리즘] 정렬 2 - 선택 정렬, 버블 정렬, 퀵 정렬

알고리즘

[알고리즘] 정렬 2 - 선택 정렬, 버블 정렬, 퀵 정렬

sundori 2023. 12. 9. 00:42

정렬

선택 정렬 Selection Sort

선택 정렬 Selection Sort은 전체 원소 중에서 기준 위치에 맞는 원소를 선택해 자리를 교환하는 방식을 사용한다.

전체 원소 중에서 가장 작은 원소를 찾은 다음 첫째 원소와 자리를 교환하고 둘째로 작은 원소를 찾고 둘째 원소와 자리를 교환한다. 그다음 셋째로 작은 원소를 찾고 셋째 작은 원소와 자리를 교환한다.

위의 사진처럼 각 단계에서 배열의 인덱스를 1씩 증가하면서 배열에어 가장 작은 값을 가진 원소와 교환을 하는 것이다.

#include <stdio.h>

void SelectionSort(int a[], int size) {
	int i, j, t, min, temp;

	for (i = 0; i < size - 1; i++) {
		min = i;
		for (j = i + 1; j < size; j++) {
			if (a[j] < a[min]) min = j;
		}
		temp = a[i];
		a[i] = a[min];
		a[min] = temp;
		printf("\n%d단계 : ", i + 1);
		for (t = 0; t < size; t++)  printf("%3d ", a[t]);
	}
}

int main(void) {
	int i,  list[8] = { 69, 10, 30, 2, 16, 8, 31, 22 };	// 정렬할 원소
	int size = sizeof(list) / sizeof(list[0]);
	printf("\n정렬할 원소 : ");
	for (i = 0; i < size; i++) 	printf("%d ", list[i]);	// 정렬 전의 원소 출력
	printf("\n\n<<<<<<<<<< 선택 정렬 수행 >>>>>>>>>>\n");
	SelectionSort(list, size);		// 선택 정렬 함수 호출

	getchar(); return 0;
}
----------------------------------------------------
정렬할 원소 : 69 10 30 2 16 8 31 22 

<<<<<<<<<< 선택 정렬 수행 >>>>>>>>>>

1단계 :   2  10  30  69  16   8  31  22 
2단계 :   2   8  30  69  16  10  31  22 
3단계 :   2   8  10  69  16  30  31  22 
4단계 :   2   8  10  16  69  30  31  22 
5단계 :   2   8  10  16  22  30  31  69 
6단계 :   2   8  10  16  22  30  31  69 
7단계 :   2   8  10  16  22  30  31  69

이러한 선택 정렬의 시간 복잡도는 시간 복잡도: O(n^2)로 정렬되어야 하는 자료의 개수가 늘어나면 늘어날수록 시간이 제곱으로 증가하는데 예를 들자면

n = 1일 때: 1^2 = 1
n = 2일 때: 2^2 = 4
n = 3일 때: 3^2 = 9
n = 4일 때: 4^2 = 16
n = 5일 때: 5^2 = 25
n = 6일 때: 6^2 = 36

이런 식으로 시간이 증가한다.

import time
import matplotlib.pyplot as plt

def selection_sort(arr):
    comparisons = 0  # 비교 횟수 초기화
    swaps = 0        # 교환 횟수 초기화
    size = len(arr)

    for i in range(size - 1):
        min_index = i
        for j in range(i + 1, size):
            comparisons += 1
            if arr[j] < arr[min_index]:
                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]
        swaps += 1

    return comparisons, swaps

def measure_time_complexity(input_sizes):
    times = []

    for size in input_sizes:
        input_data = list(range(size, 0, -1))  # 최악의 경우를 고려해 역순으로 정렬된 데이터 생성
        start_time = time.time()
        selection_sort(input_data)
        end_time = time.time()
        elapsed_time = end_time - start_time
        times.append(elapsed_time)

    return times

def plot_time_complexity(input_sizes, times):
    plt.plot(input_sizes, times, marker='o')
    plt.title('Selection Sort Time Complexity')
    plt.xlabel('Input Size')
    plt.ylabel('Time (seconds)')
    plt.show()

if __name__ == "__main__":
    input_sizes = [10, 50, 100, 200, 300, 400]  # Add more sizes as needed
    execution_times = measure_time_complexity(input_sizes)
    plot_time_complexity(input_sizes, execution_times)

버블 정렬 Bubble Sort

버블 정렬은 인접한 두 원소를 비교하여 자리를 교환하는 방식을 반복하면서 정렬을 하는 방식인데, 버블 정렬을 수행하면 인접한 처음 두 개 원소부터 인접한 마지막 원소까지 비교하는 작업과 자리를 교환하는 작업을 반복하면서 가장 큰 원소가 마지막 자리에 정렬된다.

이때 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막으로 이동하는 과정이 물 위로 뽀글뽀글하는 것 같다고 버블 정렬이라고 한다;;;..

2단계에서 중간에 자리 교환을 하지 않는 이유는 왼쪽의 기준 값이 오른쪽 인접한 원소의 값보다 작기 때문이다.

사실상 이렇게 4단계까지 온뒤 그 이후의 단계는 인접한 원소끼리 값을 비교하여 자리를 교환하는 함수에서의 반복문에 들어가도 바뀌는 것이 없다. 왜냐하면 배열을 보면 이미 정렬이 되어 있기 때문이다.

#include <stdio.h>

void bubbleSort(int a[], int size) {
	int i, j, t, temp;

	for (i = size - 1; i > 0; i--) {
		printf("\n %d단계>>", size - i);
		for (j = 0; j < i; j++) {
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
			printf("\n\t");
			for (t = 0; t < size; t++) printf("%3d ", a[t]);
		}
	}
}

int main(void) {
	int i, list[8] = { 69, 10, 30, 2, 16, 8, 31, 22 };   // 정렬할 원소 
	int size = sizeof(list) / sizeof(list[0]);
	printf("\n정렬할 원소 : ");
	for (i = 0; i < size; i++)  printf("%d ", list[i]); // 정렬 전의 원소 출력
	printf("\n\n<<<<<<<<<< 버블 정렬 수행 >>>>>>>>>>\n");
	bubbleSort(list, size);      // 버블 정렬 함수 호출

	getchar();  return 0;
}
------------------------------------
정렬할 원소 : 69 10 30 2 16 8 31 22 

<<<<<<<<<< 버블 정렬 수행 >>>>>>>>>>

 1단계>>
         10  69  30   2  16   8  31  22 
         10  30  69   2  16   8  31  22 
         10  30   2  69  16   8  31  22 
         10  30   2  16  69   8  31  22 
         10  30   2  16   8  69  31  22 
         10  30   2  16   8  31  69  22 
         10  30   2  16   8  31  22  69 
 2단계>>
         10  30   2  16   8  31  22  69 
         10   2  30  16   8  31  22  69 
         10   2  16  30   8  31  22  69 
         10   2  16   8  30  31  22  69 
         10   2  16   8  30  31  22  69 
         10   2  16   8  30  22  31  69 
 3단계>>
          2  10  16   8  30  22  31  69 
          2  10  16   8  30  22  31  69 
          2  10   8  16  30  22  31  69 
          2  10   8  16  30  22  31  69 
          2  10   8  16  22  30  31  69 
 4단계>>
          2  10   8  16  22  30  31  69 
          2   8  10  16  22  30  31  69 
          2   8  10  16  22  30  31  69 
          2   8  10  16  22  30  31  69 
 5단계>>
          2   8  10  16  22  30  31  69 
          2   8  10  16  22  30  31  69 
          2   8  10  16  22  30  31  69 
 6단계>>
          2   8  10  16  22  30  31  69 
          2   8  10  16  22  30  31  69 
 7단계>>
          2   8  10  16  22  30  31  69

버블 정렬의 시간 복잡도 또한 기존의 선택 정렬과 같은 결과가 나온다. 왜냐 시간 복잡도가 O(n^2)으로 같기 때문!

퀵 정렬 Quick Sort

퀵 정렬은 정렬할 전체 원소에 대해 정렬을 수행하지 않고 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분 집합으로 분할 Divide 한다.

왼쪽 부분 집합에는 기준값보다 작은 원소를 이동시키고, 오른쪽 부분집합에는 기준값보다 큰 원소들을 이동시킨다.

이때 사용하는 기준값을 피봇 Pivot이라고 하며 피봇은 전체 원소 중 가운데 위치한 원소를 사용하거나 첫째 원소 또는 마지막 원소 등 별도의 수식을 사용하여 정하기도 한다.

이러한 퀵 정렬은 두 가지의 기본 작업을 반복하는데...

분할 Divide : 정렬할 자료들을 기준값을 중심으로 두 개로 나누어 부분집합으로 만든다.
정복 Conquer : 부분집합 안에서 기준값의 정렬 위치를 정한다.

분할 작업을 순환적으로 반복하여 피복의 왼쪽 부분집합과 오른쪽 부분집합의 크기를 줄여가면서, 부분 집합 내에서의 정렬을 반복하는 방식으로 전체 원소를 정렬한다. 퀵 정렬은 마치 큰 일을 여러 단계로 나누어 해결하는 것처럼 동작하는 정렬 방법 같기도 하다...

피벗 선택:
- 배열에서 하나의 숫자를 선택합니다. 이 숫자는 특별한 기준으로 삼을 피벗이다.. 일반적으로 배열 중간 값을 피벗으로 고르거나 무작위로 선택한다.
파티션:
- 선택한 피벗을 기준으로, 피벗보다 작은 숫자들은 왼쪽으로, 큰 숫자들은 오른쪽으로 옮긴다. 이렇게 하면 피벗 자리는 확정되어 그 자리에는 정렬된 숫자가 들어가게 된다..
재귀적인 정렬:
- 이제 피벗을 중심으로 왼쪽과 오른쪽 부분에 대해 같은 과정을 반복한다. 즉, 왼쪽 부분에서도 피벗을 정하고 정렬하고, 오른쪽 부분에서도 마찬가지로 피벗을 정하고 정렬한다.
합병:
- 모든 부분이 정렬되면 이제 그 부분들을 합쳐 전체 배열이 정렬된 상태가 된다.

이해를 돕기 위해 예를 들어보자면. 예를 들어, [4, 2, 7, 1, 9, 5]라는 배열이 있다고 가정한다.

피벗을 중간 값 7로 선택한다.
피벗보다 작은 숫자는 왼쪽으로, 큰 숫자는 오른쪽으로 옮겨 [4, 2, 1, 5] | 7 | [9]와 같이 배열이 나뉜다.
나뉜 부분에 대해 재귀적으로 퀵 정렬을 적용한다.
- 왼쪽 부분: [4, 2, 1, 5] → 피벗 2 선택 → [1] | 2 | [4, 5]
- 오른쪽 부분: [9] (이미 정렬된 상태)
최종적으로 합쳐지면 [1, 2, 4, 5, 7, 9]가 정렬된 배열이 된다.

또 하나의 예를 들자면 주어진 배열 {69, 10, 30, 2, 16, 8, 31, 22}에 대해 퀵 정렬을 해보자.

피벗을 2로 선택하고, 주어진 데이터는 {69, 10, 30, 2, 16, 8, 31, 22} 일 때....

처음 배열:
- {69, 10, 30, 2, 16, 8, 31, 22}
피벗 선택:
- 피벗을 2로 선택한다.
파티션 과정:
- 피벗을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동한다.
- 파티션 결과: {2, 10, 8, 16, 30, 31, 22, 69}
분할 정복:
- 왼쪽 그룹에 대한 퀵 정렬: {2, 10, 8, 16} (재귀적으로 동일한 과정을 반복)
- 오른쪽 그룹에 대한 퀵 정렬: {30, 31, 22, 69} (재귀적으로 동일한 과정을 반복)
재귀적인 퀵 정렬:
- 왼쪽 그룹 {2, 10, 8, 16}에 대한 퀵 정렬:
  - 피벗을 8로 선택하고 파티션: {2, 8, 10, 16}
- 오른쪽 그룹 {30, 31, 22, 69}에 대한 퀵 정렬:
  - 피벗을 31로 선택하고 파티션: {22, 30, 31, 69}
정렬 완료:
- 최종적으로 왼쪽 그룹, 피벗, 오른쪽 그룹을 합치면 정렬 완료.
  - {2, 8, 10, 16, 22, 30, 31, 69}

#include <stdio.h>

int i = 0;  //쿽정렬 단계 출력용 변수

// 주어진 부분집합 안에서 피봇의 위치를 확정하여 분할 위치를 정하는 연산
int partition(int a[], int begin, int end, int size) {
	int  pivot, L, R, t, temp;
	L = begin;
	R = end;
	pivot = (begin + end) / 2;	// 중간에 위치한 원소를 피봇 원소로 선택
	printf("\n [%d단계 : pivot = %d ] \n", ++i, a[pivot]);
	while (L < R) {
		while ((a[L] < a[pivot]) && (L < R)) L++;
		while ((a[R] >= a[pivot]) && (L < R)) R--;
		if (L < R) {					// L과 R 원소의 자리 교환
			temp = a[L];
			a[L] = a[R];
			a[R] = temp;
			// L이 피봇인 경우, 변경된 피봇의 위치(R)를 다시 저장!
			if (L == pivot)	pivot = R;
		} // if(L<R)
	} // while(L<R)
	// (L=R)이 된 경우, 
	// 더 이상 진행할 수 없으므로 R 원소와 피봇 원소의 자리를 교환하여 마무리
	temp = a[pivot];
	a[pivot] = a[R];
	a[R] = temp;
	for (t = 0; t < size; t++)  printf("%4d", a[t]);	// 현재의 정렬 상태 출력
	printf("\n");
	return R;	// 정렬되어 확정된 피봇의 위치 반환
}

void quickSort(int a[], int begin, int end, int size) {
	int p;
	if (begin < end) {
		p = partition(a, begin, end, size);	// 피봇의 위치에 의해 분할 위치 결정
		quickSort(a, begin, p - 1, size);		// 피봇의 왼쪽 부분집합에 대해 퀵 정렬을 재귀호출
		quickSort(a, p + 1, end, size);		// 피봇의 오른쪽 부분집합에 대해 퀵 정렬을 재귀호출
	}
}

int main(void) {
	int list[8] = { 69, 10, 30, 2, 16, 8, 31, 22 }, i = 0;
	int size = sizeof(list) / sizeof(list[0]); 	// list 배열의 원소 개수
	printf("\n정렬할 원소 : ");
	for (i = 0; i <= size - 1; i++) printf(" %d", list[i]);
	printf("\n\n<<<<<<<<<< 퀵 정렬 수행 >>>>>>>>>>\n");
	quickSort(list, 0, size - 1, size);  // 퀵 정렬 함수 호출

	getchar();  return 0;
}
--------------------------
정렬할 원소 :  69 10 30 2 16 8 31 22

<<<<<<<<<< 퀵 정렬 수행 >>>>>>>>>>

 [1단계 : pivot = 2 ] 
   2  10  30  69  16   8  31  22

 [2단계 : pivot = 16 ] 
   2  10   8  16  69  30  31  22

 [3단계 : pivot = 10 ] 
   2   8  10  16  69  30  31  22

 [4단계 : pivot = 30 ] 
   2   8  10  16  22  30  31  69

 [5단계 : pivot = 31 ] 
   2   8  10  16  22  30  31  69

이 퀵 정렬의 평균 시간 복잡도: O(n log n), 최악의 경우: O(n^2)인데

평균 시간 복잡도(O(n log n)):
- 퀵 정렬의 평균 시간 복잡도인 O(n log n)은 입력 크기 n이 증가함에 따라 로그 성장하므로 상대적으로 빠른 속도로 정렬이 가능.
- 입력이 2배로 증가할 때마다 시간은 약 2배 증가.
최악의 경우(O(n^2)):
- 최악의 경우인 O(n^2)는 피벗을 항상 최소 또는 최댓값으로 선택했을 때입니다. 이 경우에는 입력 배열이 거의 정렬된 상태와 유사한 상황에서 최악의 성능을 나타낸다.
- 입력 크기 n이 증가할 때마다 시간은 n의 제곱에 비례하여 증가하므로 큰 입력에 대해 매우 느려질 수 있다.

'알고리즘' 카테고리의 다른 글

[알고리즘] 정렬 4 - 병합 정렬(2-way, n-way) (0)	2023.12.09
[알고리즘] 정렬 3 - 삽입정렬, 셸 정렬 (0)	2023.12.09
[알고리즘] 정렬 1 (1)	2023.12.08
[알고리즘] 그래프 8 - 최단 경로(플로이드) (1)	2023.12.08
[알고리즘] 그래프 7 - 최단 경로(다익스트라) (1)	2023.12.07

현재글[알고리즘] 정렬 2 - 선택 정렬, 버블 정렬, 퀵 정렬

낭만을 찾아서 개발자의 길에 오르기 시작하다.

프로그래머스, 임베디드시스템, opengl을 이용한 태양계, 알고리즘, Lv.0, CodeVisionAVR, java, C/C++, 태양계, 극동대학교, Atmega128보드, 코딩 기초 트레이닝, 극동대학교 AI컴퓨터, 스위치를 이용한 LED 컨트롤, LV0, IntStream, 자바, 추상 클래스, 트리, 자료구조,

Today :
Yesterday :

일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

sundori DevStory