먼저 4와 2를 비교해 4가 2보다 크므로2와 4의 위치를 바꿔 줍니다.이후 4와 3을 비교하여 4가 3보다 크므로4와 3의 위치를 바꿔 줍니다.전과 동일하게 4와 1을 비교하여위치를 바꾸어 줍니다.처음 정한 원소인 4 다음 원소가 없으면 다시 첫 번째 원소인 2를 선택해 다음 원소인 3과 비교합니다. 2와 3은 위치를 바꿀 필요가 없으므로 그대로 놔둡니다.다음 원소인 3에 대해 오른쪽 원소인 1과 비교합니다. 3이 더 크므로 1과 3의 위치를 바꾸어 줍니다.4는 이미 정렬되어 있으므로 3과 4를 비교하지 않고 다음 정렬 순서로 넘어갑니다.다시 첫 번째 원소인 2를 오른쪽 원소인 1과 비교하여 2가 1보다 크므로1과 2의 위치를 바꿔 줍니다. 이후 3이 정렬 되어 있으므로 2를 정렬하고 1을 정렬하려 버블 정렬을 마무리합니다.
버블 정렬을 쉽게 도식화 한 그림과 설명을 보면 한번 위치 교환을 통해 가장 큰 원소가 마지막으로 가는 것을 확인할 수 있습니다. 이를 통해 마지막 원소가 정렬되었다고 볼 수 있고, 이를 N-1번 반복한다면 버블 정렬이 끝납니다. N개의 원소가 있다면, N-1번의 교환을 통해 정렬할 수 있습니다. 이를 시간 복잡도로 나타내면 (정렬해야 할 원소의 개수 - 1) *(최대 교환 수) 이므로 O(N²)이 됩니다. 힙 정렬, 퀵 정렬과 같은 정렬보다 비효율적이므로 자주 쓰지 않습니다.
#include <iostream>
#include <algorithm>
#define MAX 5005
using namespace std;
int d[MAX];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> d[i];
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (d[j] > d[j + 1]) {
swap(d[j], d[j + 1]);
}
}
}
for (int i = 0; i < n; i++) {
cout << d[i] << " ";
}
return 0;
}
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] d = new int[5005];
for (int i = 0; i < n; i++)
d[i] = scanner.nextInt();
for (int i = 0; i < n; i++)
for (int j = 0; j < n - i - 1; j++)
if (d[j] > d[j + 1]) {
int temp = d[j];
d[j] = d[j + 1];
d[j + 1] = temp;
}
for (int i = 0; i < n; i++)
System.out.print(d[i] + " ");
}
}
