[자료구조] 버블정렬 with JAVA

[자료구조] 버블정렬 with JAVA

 

 

1. 버블정렬이란?

 - 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식

 - 첫 번째 원소부터 마지막 원소까지 반복하면 가장 큰 원소가 마지막 자리에 온다.

 

 [예시]

  1) 인접한 두 원소를 비교하여 자리를 교환하는 작업을 한다. 이 작업이 완료되면 가장 큰 수가 맨 마지막에 들어온다.

  2) 맨 마지막을 제외하고 첫 번째 칸부터 다시 비교를 시작한다. 이렇게 되면 뒤에서 두 번째 칸에 두 번째로 큰 수가 들어온다.

  3) 위와 같은 형태로 진행하면 n-i 칸에 i번째로 큰 수가 온다.

  4) ....

  5) 정렬 완료!

 

 - 코드를 확인하자!

 

2. 버블정렬의 시간복잡도

  - i번째 원소는 n-i번 비교하게 되므로 비교 횟수는 아래와 같다.

 - 시간복잡도는 O(n^2) 이다.

[참조] C로 배우는 쉬운 자료구조, 한빛미디어, 이지영 저

 

3. 버블정렬 코드

package Sort;
 
import java.util.Arrays;
 
public class BubbleSort {
    
    public static void bubbleSort(int[] a, int size) {
        int t, temp;
        System.out.println("정렬할 원소: "+Arrays.toString(a));
        System.out.println("--------------BubbleSort 시작-------------");
        for(int i=size-1;i>0;i--) {
            System.out.println(size-i+"단계 수행 >>");
            for(int j=1;j<=i;j++) {
                if(a[j-1]>a[j]) {
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                }
                System.out.println(Arrays.toString(a));
            }
        }
    }
    
    public static void main(String[] args) {
        int[] list = {69, 11, 30, 2, 16, 8, 31, 22};
        int size = list.length;
        bubbleSort(list, size);
        
 
    }
 
}​