버블 정렬

버블 정렬 (bubble sort)

알고리즘 연습 방법

1. 연습장과 펜을 준비하기.
2. 알고리즘 문제를 읽고 분석한다.
3. 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우까지 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각한다.
4. 가능한 알고리즘이 보인다면 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.
5. 코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리하고
6. 각 문장을 코드 레벨로 적는다.
7. 변수가 코드에 따라 어덯게 변하는지 손으로 적으면서, 임의 데이터로 코드가 정상 동작하는지를 연습장과 펜으로 검증한다.

쉬운 것부터 연습해보기!

1. 데이터가 두 개일 때 버블 정렬 알고리즘 방식을 정렬해보세요.

import java.util.ArrayList;
import java.util.Collections;

public class BubbleSort {
    public static void main(String args[]) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        list.add(4);
        list.add(2);
        
        // 1번 2번 비교 => 자리바꿈
        if(list.get(0) > list.get(1)) {
          Collections.swap(list, 0, 1);
        }
        
        System.out.println(list); //[2, 4]
    }
}

2. 데이터가 세 개일 때 버블 정렬 알고리즘 방식을 정렬해보세요.

import java.util.ArrayList;
import java.util.Collections;

public class BubbleSort {
    public static void main(String args[]) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        list.add(9);
        list.add(2);
        list.add(4);
        
        // list = [9, 2, 4]
        
        // [2, 9, 4] - 1번 2번 비교 => 자리바꿈
        // [2, 4, 9] - 2번 3번 비교 => 자리바꿈
        
        // [2, 4, 9] - 1번 2번 비교 => 자리바꿈 없음 - 종료
        // [참고] 3번은 9로 고정되었기 때문에 비교하지 않아도 된다.
        
        for(int i = 0; i < list.size() - 1; i++) {
            boolean flag = false;
            
            for(int j = 0; j < (list.size() - 1) - i; j++) {
                if(list.get(j) > list.get(j+1)) {
                    Collections.swap(list, j, j+1);
                    flag = true;
                }
            }
            
            if(flag == false) {
                break;
            }
        }
        
        System.out.println(list); //[2, 4, 9]
    }
}

3. 데이터가 네 개일 때 버블 정렬 알고리즘 방식을 정렬해보세요.

import java.util.ArrayList;
import java.util.Collections;

public class BubbleSort {
    public static void main(String args[]) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        list.add(1);
        list.add(9);
        list.add(3);
        list.add(2);
        
        // list = [1, 9, 3, 2]
        
        // [1, 9, 3, 2] - 1번 2번 비교 - 자리바꿈 없음
        // [1, 3, 9, 2] - 2번 3번 비교 - 자리바꿈
        // [1, 3, 2, 9] - 3번 4번 비교 - 자리바꿈
        
        // [1, 3, 2, 9] - 1번 2번 비교 - 자리바꿈 없음
        // [1, 2, 3, 9] - 2번 3번 비교 - 자리바꿈
        // [참고] 4번은 9로 고정되었기 때문에 비교하지 않아도 된다.
        
        // [1, 2, 3, 9] - 1번 2번 비교 - 자리바꿈 없음 - 종료
        // [참고] 3번과 4번은 고정되었기 때문에 비교하지 않아도 된다.
        
        for(int i = 0; i < list.size() - 1; i++) {
            boolean flag = false;
            
            for(int j = 0; j < (list.size() - 1) - i; j++) {
                if(list.get(j) > list.get(j+1)) {
                    Collections.swap(list, j, j+1);
                    flag = true;
                }
            }
            
            if(flag == false) {
                break;
            }
        }
        
        System.out.println(list); //[1, 2, 3, 9]
    }
}

4. 테스트해보기!

import java.util.ArrayList;
import java.util.Collections;
import java.lang.Math;

public class BubbleSort {
    public static void main(String args[]) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        // Math.random() : 0이상 1미만의 부동소숫점 값을 가져올 수 있다.
        for(int index = 0; index < 100; index++){
            list.add((int)(Math.random() * 100));
        }
        
        for(int i = 0; i < list.size() - 1; i++) {
            boolean flag = false;
            
            for(int j = 0; j < (list.size() - 1) - i; j++) {
                if(list.get(j) > list.get(j+1)) {
                    Collections.swap(list, j, j+1);
                    flag = true;
                }
            }
            
            if(flag == false) {
                break;
            }
        }
        
        System.out.println(list);
    }
}

5. 알고리즘 분석

• 반복문이 두 개 O(n^2)
  - 최악의 경우, n(n-1)/2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)

6. 참고사이트

• 직접 눈으로 확인
• Online Java Compiler