Burble sort

1. Problem

- n개의 정수를 담은 배열을 오름차순으로 정렬해보자.

- 버블 정렬은 바로 옆에 있는 두 요소 중 더 작은 요소를 앞으로 보내면서 정렬한다.

- 맨 끝까지의 비교가 1번씩 일어날 때마다 가장 큰 요소가 맨 뒤로 간다.

 

2. Input

1) int[] arr

 

3. Output

1) 정렬된 배열을 반환

 

4. Example

// 예시: {2 3 6 1 5 4}
// 2는 바꾸지 않는다. -> {2 3 6 1 5 4}
// 3은 바꾸지 않는다. -> {2 3 6 1 5 4}
// 1과 6을 바꾼다. -> {2 3 (1 6) 5 4}
// 6과 5를 바꾼다. -> {2 3 1 (5 6) 4}
// 6과 4를 바꾼다. -> {2 3 1 5 (4 6)} -> {2 3 1 5 4} 6
// 다시 맨 앞부터 비교한다.
// {2 3 1 4} 5 6
// {2 3 1} 4 5 6
// {2 3 1} 4 5 6
// {2 1} 3 4 5 6
// 1 2 3 4 5 6

 

5. Code

int[] arr = {6, 3, 5, 9, 1, 10, 7, 2, 4, 8}; // 10개의 요소
int temp = 0;
for(int i=0 ; i<arr.length ; i++) {       // 처음 비교 범위는 0~9까지인데
    for(int j=0 ; j<arr.length-1-i ; j++) // 그 다음 비교 범위는 0~8, 0~7로 1개씩 줄어든다.
        if(arr[j] > arr[j+1]) {           // 정렬이 1번 일어날 때마다 비교 범위의 수 중에서
            temp = arr[j];                // 가장 큰 요소가 비교 범위의 뒤쪽으로 이동하기 때문이다.
            arr[j] = arr[j+1];
            arr[j+1] = temp;    // j번째 요소가 그 다음 요소보다 크다면 둘의 자리를 바꾼다.
        }
}
// 정렬 확인
for(int i : arr)
System.out.print(i+","); // 1,2,3,4,5,6,7,8,9,10,

- 10개의 요소를 정렬할 때 살펴봐야 하는 총 횟수는 9 + 8 + ... + 1 = 45번의 비교 연산을 해야 한다.
- n개의 요소라면 비교 연산의 총 횟수는 n*(n-1)/2번이다.
- 그러므로 시간 복잡도는 O(n^2)를 따른다.
- 버블 정렬은 비교 연산이 true일 때마다 둘의 자리를 바꿔주는 연산을 해야하기 때문에 선택 정렬과 시간 복잡도는 같지만 실제 수행 시간이 훨씬 길다.