CS(Computer Science)/알고리즘

JAVA 버블정렬이란(Bubble Sort)

galid1 2018. 10. 28. 18:21
728x90


버블정렬이란.

- 두 인접한 원소를 검사하여 정렬하는 방법

- 정렬 속도는 느리지만 코드가 단순하여 자주 사용된다.

- 원소의 이동이 거품이 수면위로 올라오는 듯한 모습을 보여 지어진 이름이다.


과정

1. 첫 원소와 바로 다음의 원소를 비교하여 뒤바꾼다 한 원소씩 이동하며 반복한다.

2. 이렇게 한 사이클을 돌면 제일 큰값(오름차순의 경우)이 맨마지막에 위치 하게 된다.

3. 다시 맨첫 원소부터 정렬이 확정된 마지막 원소 전까지 1번 과정을 반복한다.


시간 복잡도 

- Θ(n2) 


코드


1) BubbleSort Class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class BubbleSort {
 
    public void bubbleSort(int[] unsortedList) {
        for(int i = 1; i < unsortedList.length; i++) {
            for(int j = 0; j < unsortedList.length - i; j++) {
                if(unsortedList[j] > unsortedList[j+1])
                    SortUtil.swap(unsortedList, j, j+1);
            }
        }
        
        SortUtil.printList(unsortedList);
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] list = new int[]{3,1,4,5,2};
        BubbleSort bubble = new BubbleSort();
        bubble.bubbleSort(list);
    }
 
}
cs

2) SortUtil Class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class SortUtil {
    
    public static void printList(int[] list) {
        for(int num : list)            
            System.out.println(num + " ");
    }
    
    public static void swap(int[] list, int num1, int num2) {
        int temp = list[num1];
        list[num1] = list[num2];
        list[num2] = temp;
    }
    
}
cs


코드해석

1. i에 대한 for문은 j에 대한 for문의 끝지점을 1씩 줄이는 목적

2. j에 대한 for문은 i에 대한 for문의 1사이클이 돌때마다 끝지점이 3 , 2 , 1 , 0 까지 줄어든다

3. j에 대한 for문에서 j가 1씩 증가할 때마다 j와 j의 바로 다음 원소의 크기를 비교하여 뒤 바꾼다.