정렬알고리즘_버블정렬 [2/8]

[ 버블 정렬이란? ]

• 기준값과 다음값을 비교해서 작은 값을 앞으로 가져옴
• 이 과정을 계속 반복해서 마지막까지 가면 정렬 완료
• 코드는 간단하지만 O(n^2)의 시간 복잡도를 가지는만큼 매우 비효율적인 정렬 방식
• 수행횟수 : 9 + 8 + 7 + ... + 1 = 9(9+1)/2 = n(n+1)/2
• 선택정렬보다 값을 교체(Swap)하는 수행 횟수가 많으므로 더 비효율적이고 느림

---

 

1. arr[0] > arr[1] 이면 두 값을 바꿔줌
2. arr[1] > arr[2] 이면 두 값을 바꿔줌
3. ...반복...
4. arr[8] > arr[9] 이면 두 값을 바꿔줌 (한 사이클 완료)
5. arr[0] > arr[1] 이면 두 값을 바꿔줌
6. ...반복...
7. arr[7] > arr[8] 이면 두 값을 바꿔줌 (한 사이클 완료)
8. ...반복...

 

#include <stdio.h>
#define SIZE 10

void main()
{
	int arr[SIZE] = { 5,4,9,3,6,7,8,1,2,10 };

	for (int i = SIZE - 2; i >= 0; --i)  // 마지막 비교값은 arr[8], arr[9]
		for (int j = 0; j <= i; ++j)  // arr[0], arr[1]을 비교하고 끝내야함
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}	

	for (int i = 0; i < SIZE; ++i)
		printf("%d ", arr[i]);
}