버블정렬

버블 정렬

버블 정렬은 구현하기 쉽습니다.

쉽게 말하면 버블 정렬은 인접한 두개 데이터를 계속 비교해서 크기에 따라 서로 바꿔주면서 정렬을 해주는 알고리즘입니다.

그림을 통해서 우선 이해를 해봅시다.

1.

 

이런식으로 비교를 해가면서 진행해 나갑니다. 3과 2중에 2가더 작기때문에 2와 3을 바꿔 줍니다.

또 3과 4를 비교합니다. 3이 더 작기때문에 이때는 교체하지 않습니다.

 

다음 인덱스로 넘어가면서 4와 1을 비교합니다. 이때 1이 더 작기 때문에 1과 4를 교체합니다.  큰 숫자가 마지막에 가있습니다. 건드릴 필요 없겠죠.

자 끝난 것 같죠??

아닙니다. 아직 2 3 1 4 로 정렬이 되지 않았습니다. 다시 처음 인덱스0인 값 2로 이동을 해서 위의 과정을 정렬이 끝날 때 까지 반복합니다.

2와 3을 비교하지만 2가 작기때문에 그대로 둡니다. 3과 1을 비교했을 때 1이 작기때문에 3과 1을 교체합니다. 마지막은 비교할 필요가 없겠죠

2.

위의 과정을 한번 더 했을 경우에는 3과 4는 제자리를 찾았습니다. 건드릴 필요 업겠죠.

이런 식으로 나오게 됩니다. 자 점점 정렬의 형태로 되가지 않나요 ?

마지막으로 한번 더 진행하게 됩니다.

2와 1을 비교하여 1이 더 작기 때문에 2와 1을 교체합니다.

그럼 1 2 3 4 순서대로 정렬이 됩니다.

어때요 버블 정렬은 쉽죠? 교환 과정이 거품 처럼 버블버블 일어난다 해서 버블정렬이랍니다.

 

그럼 이 과정들을 코드로 살펴보시죠

 

#include <stdio.h>
/*
버블 정렬
*/
#define N 4
void bubble_sort(int arr[], int n) {
	int i, j;
	int temp;
	//n번 돌아감 
	for (i = 0; i < n - 1; i += 1) {
		//마지막은 한번 돌때마다 큰 값이 뒤로 정해지기 때문에 n-i -1 
		for (j = 0; j < (n - i) - 1; j += 1) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}


int main() {
	int i;
	int arr[N] = { 1,5,2,4 };

	bubble_sort(arr, N);

	for (i = 0; i < N; i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}

 쉽게 설명드릴게요

Bub_sort는 버블정렬 함수입니다. 매개인자로 배열과 배열의 크기를 넣습니다.

copyArray는 복사할 때 필요한 변수입니다.

 

위의 예를 보면서 설명하겠습니다.

중첩 for문중에 첫 for문은 전달한 배열의 크기만큼 돌려야합니다. 위의 예에서는 4가 되겠죠.

n은 4입니다. 그렇다면 i는 0~3까지 배열의 크기만큼 총 4사이클을 돌게 되는겁니다.

 

1. 첫 사이클 for문에서 i가 0이라고 합시다.

그 다음 for문에서는 i가 0일때 j는 0~2까지 돌게됩니다. 이때 비교를 하게되는거죠.

j=0일 때

arr[0]>arr[1]을 비교해서 바꿔줘야 한다면 바꿔줍니다.

j=1일 때

arr[1]>arr[2]을 비교해서 바꿔 줍니다.

j=2일 때

arr[2]>arr[3]을 비교해서 바꿔 줍니다. 첫 사이클의 결과에서는 마지막 인덱스에 무조건 큰 숫자가 들어가게 되어있어서 마지막 인덱스는 건드릴 필요가 없습니다. 따라서 j<(n-i)-1의 형태가 나온거구요!!

 

2. 두번째 사이클 for문에서 i가 1이라고 합시다.

그 다음 for문에서 i가 1이기 때문에 j는 0~1까지 돕니다. 즉 마지막 인덱스는 건드리지 않는거죠!!

j=0일때

arr[0]>arr[1] 비교

j=1일때

arr[1]>arr[2] 비교 과정 끝 여기서도 마찬가지로 arr[2]에는 큰 숫자가 들어가기때문에 arr[2]와 arr[3]은 고정입니다. 건드릴 필요가 없습니다.

그렇디면 arr[2],arr[3]은 안건드리게 됩니다.

 

3. 세 번째 사이클 for문에서 i가 2입니다.

j는 그럼 다음 for문에서 0만 적용이 되겠죠

따라서 j=0일때 arr[0]>arr[1] 비교 완료

이렇게 되면 위의 예처럼 1, 2, 3, 4가 됩니다. 예를 들면서 설명을 했습니다. 그렇게 해야 이해가 빨리 될 것 같네요

 

다음으로 선택정렬을 설명하도록 하겠습니다.