자바로 구현하는 버블소트 (Bubble sort) 알고리즘

거품 정렬(Bubble sort)이란 ?

  - 두 인접한 원소를 검사하여 정렬하는 방법 시간 복합도가 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

출처: http://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

 

 

여기서 잠깐!

자바에선 편리하게도 배열, 리스트 형태의 데이터를 정렬해주는 클래스가 존재한다.

Arrays 클래스의 Sort 메서드를 통해 byte, int, short 배열 등 각 타입배열에 따른 정렬을 제공해주고,

Collections 클래스의 sort, reverse 메서드를 통해 List 타입의 자료를 정렬해준다.

두 방식 모두 순차방식 으로 작동한다.

자바 1.8 부터 Arrays 클래스에는 좀더 향상된 병렬처리로 parallelSort 메서드를 제공한다. 

(순차 보단 빠름 단, 1.8 부터 사용가능)

버블소트는 쉽게 풀이해서 두개의 원소를 비교하여 자리를 교환한다.

if (items[n] > items [n+1]) 즉, 앞 뒤 수를 비교하여 앞 수가 크다면 조건이 성립되면 데이터를 서로 교체한다.

69, 10, 30, 2, 16 임의의 숫자를 버블소트 한다면,

1단계. 

  첫번째 수와 두 번째 수를 비교하여 교체한다. ( 69 > 10 성립 자리 교체)

  10 69 30 2 16

  두번째 수와 세 번째 수를 비교하여 교체한다. (69 > 30 성립 자리 교체)

  10 30 69 2 16

  세번째 수와 네 번째 수를 비교하여 교체한다. (69 > 2 성립 자리 교체)

  10 30 2 69 16

  네번째 수와 다섯 번째 수를 비교하여 교체한다. (69 > 16 성립 자리 교체)

  10 30 2 16 69

 

 

2단계.

  첫번째 수와 두 번째 수를 비교하여 교체한다. (10 > 30 성립X 그대로)

  10 30 2 16 69

  두번째 수와 세 번째 수를 비교하여 교체한다. (30 > 2 성립 자리 교체)

  10 2 30 16 69

  세번째 수와 네 번째 수를 비교하여 교체한다. (30 > 16 성립 자리 교체)

  10 2 16 30 69

  네번째 수와 다섯 번째 수를 비교하여 교체한다. (30 > 69 성립 X 그대로)

  10 2 16 30 69

3단계.

  첫번째 수와 두 번째 수를 비교하여 교체한다. (10 > 2 성립 자리 교체)

  2 10 16 30 69

  

이렇게, 오름차순(ASC)이 완료 되었다.

반대로 내림차순(DESC) 를 하고싶다면? 

간단히 if (items[n] < items [n+1]) 뒤에 있는 원소가 크면 자리를 교체하면 된다.

아래 코드는 배열, 리스트 형태의 버블소트 (오름차순, 내림차순) 을 제공한다.

 - Sort Class

1. import java.util.Collections;
2. import java.util.List;
3.  
4.  
5. public class Sort {
6.    
7.     public static int[] BubbleSortAsc(int [] items) {
8.         for(int i=0;i<items.length-1;i++) {
9.             for(int j=0; j<items.length-1; j++) {
10.                 if (items[j] > items[j+1]) { //원소를 비교하여 앞 원소가 크다면..
11.                     int temp = items[j]; //앞 원소를 임시 저
12.                     items[j] = items[j+1]; //앞 원소의 자리에 다음 원소 값 저장
13.                     items[j+1] = temp; //다음 원소의 자리에 임시로 저장했던 원소값 저
14.                 }
15.             }
16.         }
17.         return items;
18.     }
19.    
20.     public static List<Integer> BubbleSortAsc(List<Integer> items) {
21.         Collections.sort(items);
22.         return items;
23.     }
24.  
25.     public static int[] BubbleSortDesc(int [] items) {
26.         for(int i=0;i<items.length-1;i++) {
27.             for(int j=0; j<items.length-1; j++) {
28.                 if (items[j] < items[j+1]) {
29.                     int temp = items[j];
30.                     items[j] = items[j+1];
31.                     items[j+1] = temp;
32.                 }
33.             }
34.         }
35.         return items;
36.     }
37.  
38.     public static List<Integer> BubbleSortDesc(List<Integer> items) {
39.         Collections.reverse(items);
40.         return items;
41.     }
42.    
43. }

 - Main Class

1. import java.util.ArrayList;
2.  
3. public class Main {
4.  
5.     public static void main(String[] args) {
6.        
7.         int temp[] = {3,5,7,9,1,8};
8.         temp = Sort.BubbleSortAsc(temp);
9.         System.out.print("Array Asc : ");
10.         for(int z : temp) {
11.             System.out.print(z + " ");         
12.         }
13.        
14.         ArrayList<Integer> tempList = new ArrayList<Integer>();
15.         tempList.add(3);
16.         tempList.add(5);
17.         tempList.add(7);
18.         tempList.add(9);
19.         tempList.add(1);
20.         tempList.add(8);
21.  
22.         System.out.println("");
23.         System.out.print("List Asc : ");
24.         Sort.BubbleSortAsc(tempList);
25.         for(int z : tempList) {
26.             System.out.print(z + " ");     
27.         }
28.                
29.  
30.         System.out.println("\n");
31.         temp = Sort.BubbleSortDesc(temp);
32.         System.out.print("Array Desc : ");
33.         for(int z : temp) {
34.             System.out.print(z + " ");         
35.         }
36.  
37.         System.out.println("");
38.         System.out.print("List Desc : ");
39.         Sort.BubbleSortDesc(tempList);
40.         for(int z : tempList) {
41.             System.out.print(z + " ");     
42.         }
43.     }
44. }

실행결과

Sort.java

※ 퍼갈땐 반드시 출처를 남겨주세요.