[정렬] 버블 정렬(Bubble Sort) 알고리즘

-인접한 두 원소를 비교하여 큰 값을 오른쪽으로 이동시키며 정렬하는 알고리즘

 

1. 배열의 첫번째 원소와 두번째 원소를 비교하여 첫번째 원소가 더 크면 두 원소의 위치를 교환

2. 두번 째 원소와 세번째 원소를 비교하여 큰 값을 오른쪽으로 이동시킨다

(오름차순일 경우, 내림차순이면 반대로 하면 된다)

 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

간단한 이 문제를 버블정렬로 구현했다

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
using namespace std;


int main() {

    int n;
    scanf("%d", &n);
    int a[1000] = { 0, };

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d\n", a[i]);
    }
    

  
    return 0;
}

 

바깥 for문은 배열을 전체적으로 탐색하는 역할이다

 

가장 큰 값을 배열의 마지막 원소부터 채워나간다.

1회전이 끝나면 제일 큰 원소가 배열의 맨 끝으로 이동한다

그리고 2회전때는 그 맨 끝의 원소를 비교할 필요가 없다 바깥 for문이 한 번 순회하고 나면 마지막 원소는 맨 끝에 이미 정렬이 되었으니까!!

 

첫번째 바깥문 실행때는 모든 원소를 비교하지만

두번째 바깥문 실행때는 가장 큰 원소(배열의 마지막에 있음)를 제외하고 비교하며 된다

그래서 안쪽바깥문은 n-i-1번까지 순회한다