버블정렬 (bubble sort)

버블정렬은 인접한 두 데이터의 크기를 비교해 두 데이터를 서로 바꿔가며 정렬하는 방법이다.
간단히 구현할 순 있지만, 시간복잡도는 O(n^2)로 다른 정렬 알고리즘보다 속도가 느린 편이다.

핵심 이론

정렬되지 않은 정렬의 첫번째 인덱스부터 그 다음 인덱스와 비교하며, 정렬 조건에 따라 자리를 바꿔준다.
1. 루프 범위 설정
2. 인접한 데이터 값을 비교한다.
3. swap조건에 부합하면 swap연산을 수행하고, 부합하지 않으면 그냥 넘어간다.
4. 2번~3번을 반복한다.
5. 전 범위를 반복하면 정렬된다.
( 만약 전 범위를 반복하지 않았지만, 만약 하나의 루프에서 swap연산이 한번도 일어나지 않는다면 끝내도된다.)

Code

n : 배열의 크기
정렬되지 않은 배열 arr이 주어질때

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

(참고)Do it! 알고리즘 코딩테스트 자바편
http://www.yes24.com/Product/Goods/108571508