기본 정렬 - Bubble Sort(버블 정렬)

[정렬 방법]

전체(n개의 값)에서 가장 왼쪽 이웃한 두 값부터 오른쪽 끝까지 비교하는데 왼>오이면 swap, 아닐 경우 continue한다. 이후 가장 max값을 픽스하고 나머지 값에 대해 이 과정을 진행,... 마지막으로 남은 두 값을 비교하고서 정렬하면 정렬이 완료된다.

---

[정렬 과정]

n 크기의 임의의 배열 arr에서(이때, 코드에서 key는 min과 max로 작성하였음.)

 

<1단계> - n-1번의 비교

 

arr[0]과 arr[1]을 비교 후  ( arr[0] > arr[1] )이면 arr[0]과 arr[1] swap, ( arr[0] <= arr[1] )이면 continue

arr[1]과 arr[2]을 비교 후  ( arr[1] > arr[2] )이면 arr[1]과 arr[2] swap, ( arr[1] <= arr[2] )이면 continue

.

.

.

arr[n-2]과 arr[n-1]을 비교 후  ( arr[n-2] > arr[n-1] )이면 arr[n-2]과 arr[n-1] swap, ( arr[n-2] <= arr[n-1] )이면 continue

 

<2단계> - n-2번의 비교

 

arr[0]과 arr[1]을 비교 후  ( arr[0] > arr[1] )이면 arr[0]과 arr[1] swap, ( arr[0] <= arr[1] )이면 continue

arr[1]과 arr[2]을 비교 후  ( arr[1] > arr[2] )이면 arr[1]과 arr[2] swap, ( arr[1] <= arr[2] )이면 continue

.

.

.

arr[n-3]과 arr[n-2]을 비교 후  ( arr[n-3] > arr[n-2] )이면 arr[n-3]과 arr[n-2] swap, ( arr[n-3] <= arr[n-2] )이면 continue

 

 

<n-1단계> - 1번의 비교

 

arr[0]과 arr[1]을 비교 후  ( arr[0] > arr[1] )이면 arr[0]과 arr[1] swap, ( arr[0] <= arr[1] )이면 continue

---

[pseudo code]

bubbleSort(arr[], n) {
  for last <- n downto 2 {
    for i <- 0 to last-1
      if (arr[i] > arr[i+1]) the arr[i] <-> arr[i+1]; //arr[i] > arr[i+1]이면 두 값 swap
  }
}

---

[코드 구현]

 

public class Bubble {
  public static int[] input = {22, 5, 34, 1, 32, 18, 2, 8}; //예시로 작성한 배열
  
  public static void main(String[] args) {
    bubbleSortMax(input, input.length); //혹은 bubbleSortMin(input, input.length);
    for (int i : input) {
      System.out.print(i + " ");
    }
  }
  
  public static void bubbleSortMax(int[] input, int length) { //가장 큰 값부터 버블 정렬하는 방법
    int tmp;
    for (int i = length-1; i > 0; i--) //0부터 length-1, 0부터 length-2,...,0과 1까지 비교해나감.
      for (int j = 0; j < i; j++) { //0과1, 1과2,...,i-2와 i-1을 비교 후 큰 값을 오른쪽으로 바꿔나감.
        if (input[j] > input[j+1]) {
          tmp = input[j];
          input[j] = input[j+1];
          input[j+1] = tmp;
        }
      }
  }
  
  public static void bubbleSortMin(int[] input, int length) { //가장 작은 값부터 버블 정렬하는 방법
    int tmp;
    for (int i = 0; i < length-1; i++) //0부터 length-1, 0부터 length-2,...,0과 1까지 비교해나감.
      for (int j = length-1; j > i; j--) { //i과 i+1, i+1과 i+2,...,length-2 length-1을 비교 후 큰 값을 오른쪽으로 바꿔나감.
        if (input[j] < input[j-1]) {
          tmp = input[j];
          input[j] = input[j-1];
          input[j-1] = tmp;
        }
      }
  }
}

---

[시간 복잡도]

 

처음에 n-1번의 비교, 그 다음에 n-2번의 비교,..., 1번의 비교를 진행하므로

T(n) = (n-1)+(n-2)+...+1 ) = O( n(n-1)/2 ) = O(n^2) 이 된다.

 

정렬이 잘 되어 있는 정도에 따라서

최악, 최선, 평균 모두 n(n-1)/2번의 비교연산을 수행하므로 시간복잡도는 모두 O(n^2)이다.