[알고리즘] 버블 정렬 Bubble sort

스터디 요일이 매주 화요일이기 때문에 연휴에도 하나쯤 포스팅해 두어야할 것 같아 올리는 버블 정렬 알고리즘입니다. 
티스토리 블로그 시작 전에 문제를 풀어본 주제였지만 가볍게 내용 정리 차원에서 올려봅니다!

1. 버블 정렬이란?

 먼저 정렬이란, 어떤 데이터의 순서를 정해진 규칙대로 나열하는 것입니다. 정렬에 관한 알고리즘은 다양하고 각 알고리즘마다 작동 방식의 효율이 다르기 때문에 종류와 특징에 대해 잘 알고 있어야 효율적인 알고리즘 구현을 할 수 있습니다. 
 버블 정렬 Bubble sort이란 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 클 경우 순서를 바꿔주는 알고리즘입니다. 버블 정렬이 진행되는 동안, 숫자가 큰 순서대로 뒤에서부터 배열되는 특징이 있습니다.

출처:t.ly/zMEr

2. 시간 복잡도

 데이터의 길이가 n 이라면 데이터가 끝날 때까지 두 개씩 비교하는 과정을 $n-1$번, 모든 데이터가 순서대로 정렬될 때까지 $n$번 반복하기 때문에 최악의 경우 $ O( \tfrac{n(n-1)}{2} ) $, 완전 정렬이 되어있는 상태라면 최선의 경우에는 $O(n)$의 시간복잡도를 가지게 됩니다. 

3.구현과 문제 모음

on Github
백준 1517, 11920, 23970
프로그래머스 정렬