[정렬] 버블정렬 (Bubble Sort)

 

버블정렬 O(n^2)

마지막 인덱스에 최대 값을 놓음

 

첫번째 for 조건 0 < n-1   - 이유: 버블 정렬은 인접한 혹은 자기자신의 +1 인덱스와 비교를 반복함.  4321의 경우 4-3, 3-2, 2-1 와 같이 비교해야 하는 수가 정해짐.

두번째 0 < (n-i)-1 - 이유: 자기 다음의 인덱스와의 크기여부를 비교함. 첫번째 for에서의 마지막 인덱스전까지를 기준으로 다음 인덱스와의 비교연산을 하기 때문.

기준이 되는 인덱스가 자신의 다음 인덱스보다 큰 경우 if(a[i] > a[i+1]) SWAP

temp = a[i]
a[i+1] = a[i]
a[i] = temp

n을 오름차순으로 정렬하라.
ex) n = [4,3,2,1] 
첫번째 4-3, 3-2, 2-1와 같이 비교 해야하는 갯수가 정해짐
4,3,2,1 -> 3,4,2,1 -> 3,2,4,1 -> 3,2,1,4

두번째 맨 마지막 숫자를 제외하고 3-2, 2-1와 같이 비교 해야하는 갯수가 정해짐
3,2,1,4 -> 2,3,1,4 -> 2,1,3,4

세번째 맨 마지막 숫자를 제외하고 2-1와 같이 비교 해야하는 갯수가 정해짐
2,1,3,4 -> 1,2,3,4

 

#include<iostream>
using namespace std;
 
void BubbleSort(int arr[], int n){
    int temp;
    
    for (int i = 0; i < n - 1; i++){
        for (int j = 0; j < (n - i) - 1; j++){
 
            if (arr[j] > arr[j + 1]){
            
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            
            }
        }
    }
}
 
 
int main(){
 
    int arr[4] = {4, 3, 2, 1};
 
    BubbleSort(arr, sizeof(arr) / sizeof(arr[0]));
 
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        cout << i+1 << ": "<< arr[i] << '\n';
    
    return 0;
}