버블정렬(Bubble Sort)

버블정렬

인접한 데이터를 비교하여 정렬시킨다. 시간복잡도는 O(N^2) 이다.

처음 N개 데이터를 인접한 데이터끼리 N-1번 비교하여 인덱스 끝에 정렬시킨 데이터를 넣는다.

이후 N-1개 데이터로 인접한 데이터 비교를 N-2번 ... 이 과정을 반복한다. 

(N-1) + (N-2) + .... + 2 + 1 = (N-1)*(N-2) / 2 = O(N^2) 

코드는 단순하다.

가장 마지막 위치부터 정렬시킨다.

참고 : https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

#include<iostream>
#include<vector>
using namespace std;
 
int main() {
   int n;
   cin >> n;
   vector<int> v = vector<int>(n, 0);
   for (int i = 0; i < n; i++) {
      cin >> v[i];
   } // input
 
   for (int ith = 0; ith < n-1; ith++) {
      for (int here = 0; here < n - 1 - ith; here++) {
         int there = here + 1;
         if (v[here] > v[there]) {
            int temp = v[here];
            v[here] = v[there];
            v[there] = temp;
         }
      }
      cout << "["<<ith << "th] ";
      for (auto it : v) {
         cout << it << " ";
      }
      puts("");
   } // bubble sort
 
   for (auto it : v) {
      cout << it << " ";
   }
 
   return 0;
}
/*
input format
N
A[0] A[1] .... A[N-1]
*/