버블 정렬

버블 정렬

인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

 

버블 정렬 알고리즘

 

데이터가 두 개일 때 버블 정렬

import java.util*;

ArrayList<Integer> list = new ArrayList<>();
list.add(5);
list.add(3);

if(list.get(0) > list.get(1)) {
    Collections.swap(list, 0, 1);
}

System.out.println(list);    // [3, 5]

 

데이터가 세 개일 때 버블 정렬

import java.util.*;

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(3);
list.add(5);

for(int i = 0; i < list.size() - 1; i++) {
    if(list.get(i) > list.get(i + 1)) {
        Collections.swap(list, i, i + 1);
    }
}

System.out.println(list);    // [3, 5, 10]

 

버블 정렬 구현

• n개의 리스트가 있는 경우 최대 n - 1번 적용
• 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정됨
• 한 번도 교환된 적이 없다면 이미 정렬된 상태, 반복 적용할 필요 없음

import java.util.*;

public class BubbleSort {
    public ArrayList<Integer> sort(ArrayList<Integer> list) {
        for(int i = 0; i < list.size() - 1; i++) {
            boolean isSwap = 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);
                    isSwap = true;
                }
            }
            
            if(isSwap == false) {
                break;
            }
        }
        
        return list;
    }
}

 

 

시간 복잡도

• 반복문이 두개 O(n^2), 최악일 경우 𝑛∗(𝑛−1) / 2
• 완전 정렬일 경우 O(n)

 

 

 

 

 

 

 

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스