자바의 버블 정렬

1. 소개

이 빠른 기사에서는 Java 구현에 중점을두고 버블 정렬 알고리즘을 자세히 살펴 보겠습니다.

이것은 가장 간단한 정렬 알고리즘 중 하나입니다. 핵심 아이디어는 컬렉션이 정렬 될 때까지 배열의 인접한 요소 가 잘못된 순서로되어있는 경우 계속 교체 하는 것입니다.

데이터 구조를 반복하면서 작은 항목이 목록의 맨 위에 "거품"이됩니다. 따라서이 기술을 버블 정렬이라고합니다.

정렬은 스왑에 의해 수행되기 때문에 내부 정렬을 수행한다고 말할 수 있습니다.

또한 두 요소의 값이 동일한 경우 결과 데이터의 순서가 유지 되므로 안정적인 정렬이 가능합니다.

2. 방법론

앞서 언급했듯이 배열을 정렬하기 위해 인접한 요소를 비교하고 필요한 경우 교체하면서 배열을 반복합니다. 크기가 n 인 배열에 대해 n-1 번의 반복을 수행합니다.

방법론을 이해하기 위해 예를 들어 보겠습니다. 오름차순으로 배열을 정렬하고 싶습니다.

4 2 1 6 3 5

4와 2를 비교하여 첫 번째 반복을 시작합니다. 그들은 확실히 올바른 순서가 아닙니다. 스와핑 결과 :

[2 4] 1 6 3 5

이제 4와 1에 대해 동일하게 반복합니다.

2 [1 4] 6 3 5

우리는 끝까지 계속합니다.

2 1 [ 4 6] 3 5

2 1 4 [3 6] 5

2 1 4 3 [5 6]

보시다시피, 첫 번째 반복이 끝날 때 올바른 위치에 마지막 요소가 있습니다. 이제 우리가해야 할 일은 다음 반복에서 동일한 절차를 반복하는 것입니다. 단, 이미 정렬 된 요소는 제외됩니다.

두 번째 반복에서는 마지막 요소를 제외한 전체 배열을 반복합니다. 마찬가지로 세 번째 반복의 경우 마지막 2 개 요소를 생략합니다. 일반적으로 k 번째 반복의 경우 인덱스 nk (제외) 까지 반복 합니다. n-1 반복 이 끝나면 정렬 된 배열을 얻습니다.

이제 기술을 이해 했으므로 구현에 대해 살펴 보겠습니다.

3. 구현

Java 8 접근 방식을 사용하여 논의한 예제 배열에 대한 정렬을 구현해 보겠습니다.

void bubbleSort(Integer[] arr) { int n = arr.length; IntStream.range(0, n - 1) .flatMap(i -> IntStream.range(1, n - i)) .forEach(j -> { if (arr[j - 1] > arr[j]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } }); }

그리고 알고리즘에 대한 빠른 JUnit 테스트 :

@Test public void whenSortedWithBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(array); assertArrayEquals(array, sortedArray); }

4. 복잡성과 최적화

우리가 알 수 있듯이, 평균 및 최악의 경우에 , 시간 복잡도는 (N은 2 ^) O .

또한, 버블 정렬 알고리즘은 추가 메모리를 필요로하지 않고 정렬이 원래 배열 에서 발생하므로 최악의 시나리오에서도 공간 복잡성 은 O (1) 입니다.

솔루션을주의 깊게 분석하면 반복에서 스왑이 발견되지 않으면 더 이상 반복 할 필요가 없음을 알 수 있습니다.

앞에서 설명한 예제의 경우 두 번째 반복 후 다음을 얻습니다.

12 34 5 6

세 번째 반복에서는 인접한 요소 쌍을 바꿀 필요가 없습니다. 따라서 나머지 모든 반복을 건너 뛸 수 있습니다.

정렬 된 배열의 경우 첫 번째 반복 자체에서 교체가 필요하지 않습니다. 즉, 실행을 중지 할 수 있습니다. 이것은 최상의 시나리오이며 알고리즘시간 복잡도는 O (n) 입니다.

이제 최적화 된 솔루션을 구현해 보겠습니다.

public void optimizedBubbleSort(Integer[] arr) { int i = 0, n = arr.length; boolean swapNeeded = true; while (i < n - 1 && swapNeeded) { swapNeeded = false; for (int j = 1; j  arr[j]) { int temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; swapNeeded = true; } } if(!swapNeeded) { break; } i++; } }

최적화 된 알고리즘의 출력을 확인해 보겠습니다.

@Test public void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.optimizedBubbleSort(array); assertArrayEquals(array, sortedArray); }

5. 결론

이 튜토리얼에서 우리는 버블 정렬이 어떻게 작동하는지, 자바로 구현하는 것을 보았습니다. 또한 어떻게 최적화 할 수 있는지 살펴 보았습니다. 요약하면 시간이 복잡하고 안정적인 내부 알고리즘입니다.

  • 최악 및 평균 사례 : O (n * n), 배열이 역순 일 때
  • 최상의 경우 : O (n), 배열이 이미 정렬 된 경우

이 알고리즘은 정렬시 작은 오류를 감지 할 수있는 기능으로 인해 컴퓨터 그래픽에서 널리 사용됩니다. 예를 들어, 거의 정렬 된 배열에서 완전히 정렬 된 배열을 얻으려면 두 개의 요소 만 교체하면됩니다. 버블 정렬은 선형 시간에서 이러한 오류를 수정할 수 있습니다 (예 :이 배열 정렬).

항상 그렇듯이이 알고리즘의 구현을위한 코드는 GitHub에서 찾을 수 있습니다.