버블정렬 (Bubble Sort)

정렬을 배우면 처음으로 접하는 정렬 방법이 

바로 이 버블 정렬입니다 알고리즘, 자료구조 책을 참고해보면

일일이 하나씩 비교해서 정렬을 한다 라고 설명이 되어있는데

다른 정렬을 보다보면 조금 다른 방향으로 해석이 가능해집니다

루프가 두번 들어 가는 형태로 비교대상이 하나씩 줄어들며 계속해서 처음부터 비교해 나갑니다

아래 그림을 보겠습니다

이 예제는 5개의 배열이므로

첫번째 루프를 i, 두번쨰 루프를 j라고 하겠습니다

1. i=0, j=0

2. i=0, j=1

3. i=0, j=2

4. i=0, j=3 여기서 오른쪽 맨끝이 확정된 정렬이 되어집니다

5. i=1, j=0

6. i=1, j=1

7. i=1, j=2 여기서 오른쪽 두번쨰 끝이 확정된 정렬이 되어집니다

8. i=2, j=0

9. i=2, j=1 여기서 오른쪽 3번째 끝이 확정된 정렬이 되어집니다

10. i=2, j=1 여기서 오른쪽 4번째 끝이 확정된 정렬이 되어지게됩니다.

이렇게 비교하고 나면 정렬이 완료됩니다.

#include <iostream> using namespace std; void printArr(int *arr,int size){ for(int i = 0;i<size;i++){ cout << arr[i]<<" "; } cout<<endl; } void swapArr(int *arr,int a,int b){ int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } void bubbleSort(int *arr,int size){ for(int i = 0; i<(size-1) ;i++){ for(int j = 0 ;j<(size-1-i);j++){ if(arr[j]>arr[j+1]) swapArr(arr, j, j+1); } } } int main(int argc, const char * argv[]) { int inputSize; int *arr; cin >> inputSize; arr = (int*)malloc(sizeof(int)*(inputSize)); for(int i = 0; i<inputSize ;i++){ cin >> arr[i]; } bubbleSort(arr,inputSize); printArr(arr,inputSize); return 0; }