버블 정렬

버블 정렬 --> 옆에 사람끼리 비교한다,

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이라고 한다...

제일 큰 원소가 가장 오른쪽으로 이동한다. (빠르게)

비교적으로 작은 원소들이 정렬되는 속도가 크기가 큰 원소들이 정렬되는 속도보다 느리다.

 

#include <iostream>
using namespace std;

void swap(int* a, int* b)
{
 int tmp = *a;
 *a = *b;
 *b = tmp;
}

int main() {
    int arr_len;
    cin >> arr_len;
    int arr[arr_len];

    for(int i=0; i<arr_len; i++) {
        cin >> arr[i];
    }

    for(int i=1; i<arr_len; i++) {
        for(int j=0; j<arr_len - i; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
    for(int i=0; i<arr_len; i++) {
        cout << arr[i] <<" ";
    }

}

i 횟수

배열 크기 -1 만큼 반복함

why? 배열 크기 -1 번만 하면 나머지 1개 원소는 알아서 배정된다.

 

j 횟수

배열 크기 - i번 반복

why? i개의 오른쪽 원소들은 이미 정렬이 되있기 때문이다.

         크기가 큰 원소들이 빠르게 오른쪽으로 이동한다!