3. 버블정렬 bubble sort (Java)

Goal

 - 버블정렬 이해

 - 버블정렬 알고리즘 C언어 및 Java언어로 구현 

 - 버블정렬의 특징 및 시간복잡도 

1. 버블정렬 (bubble sort)

 - 각 회전마다 첫 번째 값을 시작으로 양옆 값을 비교후 교환 하여 자료내 가장 큰 값을 맨 뒤로 밀어냄.

 - 회전의 수행으로 가장 큰 값이 뒤에서부터 채워지기 때문에, 각 회전에서의 교환 작업은 이전 회전의 교환 작업수 -1.

 - 총 자료의 수(n) - 1번 회전 수행.

 

 사진 1) 버블정렬 실행 방식

 

 

 

1) C로 구현

void bubbleSort(int data[], int n){
  for (int i = n-1; i > 0; i--){
    for (int j = 0; j < i; j++ ){
      if (data[j] > data[j + 1]){
        int tmp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = tmp;
      }
    }
  }
}

 

2) Java 구현

 - 각 회전마다 첫 번째 값을 시작으로 양옆 값을 비교후 교환 하여 자료내 가장 큰 값을 맨 뒤로 밀어냄.

 - 회전의 수행으로 가장 큰 값이 뒤에서부터 채워지기 때문에, 각 회전에서의 비교 작업은 이전 회전의 비교 작업수 -1.

 - 총 자료의 수(n) - 1번 회전 수행.

package inflearn.chapter1.algorithm;

import java.util.Arrays;

public class BubbleSortImplement {

	public static void main(String[] args) {
		
	  int[] numArr = {8, 5, 3, 2, 9};
	  bubbleSort(numArr, numArr.length);
	  System.out.println(Arrays.toString(numArr));

	}
	
	static void bubbleSort(int data[], int n) {
	  for (int i = n-1; i > 0; i--) { // 총 자료수(n) - 1번의 회전 실행 
	    for (int j = 0; j < i; j++) { // 각 회전마다 비교 작업은 이전 비교 작업 - 1
	      if (data[j] > data[j + 1]) { // 이전 값이 다음 값보다 크면 SWAP (값이동) 실행하고 큰 값을 뒤로 밀어냄
	        int tmp = data[j];
	        data[j] = data[j + 1];
	        data[j + 1] = tmp;
	      }
	    }
	  }
		
	}

}

 

1-1 버블 정렬(bubble sort) 알고리즘의 특징

- 장점
  ->구현이 매우 간단.
 - 단점
  -> 순서에 맞지 않은 요소를 인접한 요소와 교환함. 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 함. 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어남. 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않음.

 

1-2 버블 정렬(bubble sort)의 시간복잡도

 - 비교 횟수 : 최상, 평균, 최악 모두 일정 -> n-1, n-2, … , 2, 1 번 = n(n-1)/2
 - 교환 횟수 : 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2. 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
 - T(n) = O(n^2)

 

- 참고 자료 

*정렬 알고리즘 내용참고

참고: https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html