Java) 버블 정렬(Bubble Sort) 알고리즘

여러 정렬(Sort) 알고리즘 중에 '버블 정렬'에 대해 알아보자.

 

버블 정렬은 정렬 알고리즘 중에서 가장 기본적인 알고리즘이다.

인접한 두 요소를 검사하여 정렬하는 방법이다.

 

시간 복잡도는 O(n^2)으로 상당히 느리다. 하지만, 코드는 짜기 매우 단순하다.

 

코드는 다음과 같다.

 

public class SortAlgorithm {
	public int[] bubbleSort(int[] arr) {

	// 외부 for문은 배열의 길이만큼 반복문을 돌려야 함
    for (int i = 0; i < arr.length; i++) {

      boolean swapped = false;
	  
      // 내부 for문은 끝을 제외한 나머지 길이(n-1)만큼 반복문을 돌려야 함
      for (int j = 0; j < arr.length - i - 1; j++) {

        if (arr[j] > arr[j + 1]) {
          swap(arr, j, j + 1);
          swapped = true;
        }
      }

      if (swapped == false) break;
    }
    return arr;
  }

  // 실질적으로 요소의 교체가 이뤄지는 메서드
  void swap(int[] a, int i, int j) {
    
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
}

 

코드에서 boolean 타입의 코드들은 선택적이다.
이미 요소가 교체되어서, 교체가 필요 없는 과정은 이 코드를 통해 생략할 수 있다.
그러므로, 코드의 실행 시간을 단축시킬 수 있는 부가적인 코드라고 생각하면 된다.

대개는 이 코드를 작성하는 걸 권장한다.

 

 

버블 정렬에 대해 간단하게 학습하고 작성한 글이다.

추후에, 문제를 접하거나 깊이 공부하게 되는 상황이 생기면, 덧붙여 작성할 예정이다.