Bubble Sort

Loading...April 9, 2022

Concept

성능이 그리 좋지 않지만, 로직이 간단하여 인간이 하듯이 정렬한다.

insertion sort 보다 더 느리다. 그래서 List가 크다면 적절하진 않다.

List가 sorted 되어있다면 굉장히 빠르다. O(n)

How to work

  1. 두 숫자를 비교 후 큰 숫자를 오른쪽으로 이동
  2. Outer 루프가 한번 돌 때 마다 element 하나의 최종위치가 확정
  3. 탐색범위

    3-1. Outer: 0 -> n-1 (마지막 element는 이미 비교 되었음)

    3-2. Inner: 0 -> n-i-1 (이미 정렬 되어있는 부분 제외)

Performance

Worst: O(n^2)

Average: O(n^2)

Best: O(n)

Source

public class BubbleSort {

   public void work(int[] numbers) {
      boolean numberSwitched;
      do {
         numberSwitched = false;
         for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i + 1] < numbers[i]) {
               int tmp = numbers[i + 1];
               numbers[i + 1] = numbers[i];
               numbers[i] = tmp;
               numberSwitched = true;
            }
         }
      } while (numberSwitched);
   }

   public void work2(int[] numbers) {
      for (int i = 0; i < numbers.length - 1 ; i ++) {
         for (int j = 0; j < numbers.length -1 - i ; j ++) {
            if (numbers[j + 1] < numbers[j]) {
               int tmp = numbers[j + 1];
               numbers[j + 1] = numbers[j];
               numbers[j] = tmp;
            }
         }
      }
   }