버블 정렬 자바

프로그래밍에서 정렬 방법에 대해 들어본 적이 있다면 대부분 버블 정렬 알고리즘일 것입니다. 그것은 유명한 것입니다. 모든 프로그래머는 버블 정렬이 세계 최고의 정렬 알고리즘이기 때문이 아니라 가장 쉽기 때문에 버블 정렬을 알고 있습니다. 이 알고리즘은 일반적으로 학습 목적으로 사용되거나 Java Junior 인터뷰에서 작업으로 얻을 수 있습니다. Java 버블 정렬 알고리즘은 이해하기 매우 쉽지만 효율적이지 않습니다. 어쨌든 알아 봅시다.

정렬이란

우선 일반적으로 정렬이 무엇인지, Java 프로그램에서 무엇을 정렬할 수 있는지 이해해야 합니다. 두 개 이상의 요소나 객체를 속성으로 비교할 수 있다면 이 속성으로 정렬할 수 있음을 의미합니다. 예를 들어 오름차순 또는 내림차순의 숫자 또는 사전순 단어. 따라서 요소는 서로 비교 가능해야 합니다. 그건 그렇고, 무엇의 요소? Java에서는 Collections의 요소를 비교할 수 있습니다. 예를 들어 정수, 문자열 등의 Array 또는 ArrayList를 정렬할 수 있습니다.

버블 정렬은 어떻게 작동합니까?

정수 배열을 오름차순, 즉 가장 작은 수에서 가장 큰 수로 정렬해야 한다고 가정해 보겠습니다. 먼저 전체 배열을 따라 이동하고 인접한 2개의 요소를 모두 비교합니다. 순서가 잘못된 경우(왼쪽 이웃이 오른쪽 이웃보다 큼) 교환합니다. 끝에 있는 첫 번째 패스에서 가장 큰 요소로 나타납니다(오름차순으로 정렬하는 경우). 가장 큰 요소는 "팝업"이라고 말할 수 있습니다. 그것이 버블 정렬 알고리즘 이름의 이유입니다. 첫 번째 요소부터 마지막 요소까지 첫 번째 단계를 반복합니다. 마지막에서 두 번째로 큰 요소가 있습니다. 등등. 이전 단계에서 적어도 하나의 교환이 이루어졌는지 확인하여 알고리즘을 약간 개선할 수 있습니다. 그렇지 않은 경우 어레이를 따라 실행을 중지합니다.

버블 정렬 예제

아래 그림에서 볼 수 있는 정수 배열을 정렬해 봅시다. 버블 정렬 - 2

1단계: 어레이를 통과합니다. 알고리즘은 처음 두 요소(인덱스 0과 1 포함), 8과 7로 시작하여 순서가 올바른지 확인합니다. 분명히 8 > 7이므로 서로 바꿉니다. 다음으로 두 번째와 세 번째 요소(인덱스 1과 2)를 살펴봅니다. 이제 이들은 8과 1입니다. 같은 이유로 서로 바꿉니다. 세 번째로 우리는 8과 2, 적어도 8과 5를 비교합니다. 우리는 총 4개의 교환을 했습니다: (8, 7), (8, 1), (8, 2), (8, 5). 이 배열에서 가장 큰 값인 8이 목록 끝에 올바른 위치로 나타납니다. 버블 정렬 - 3

버블 정렬 알고리즘 작업의 첫 번째 단계 결과는 다음 배열입니다. 버블 정렬 - 4

2단계. (7,1), (7,2) 및 (7,5)와 동일한 작업을 수행합니다. 7은 이제 끝에서 두 번째 위치에 있으며 목록의 "꼬리"와 비교할 필요가 없으며 이미 정렬되어 있습니다. 버블 정렬 - 5

버블 정렬 알고리즘 작동의 두 번째 단계의 결과는 다음 배열입니다. 버블 정렬 - 6

보시다시피 이 배열은 이미 정렬되어 있습니다. 어쨌든 버블 정렬 알고리즘은 적어도 한 번은 더 진행되어야 합니다. 3단계. 우리는 배열을 한 번 더 살펴보고 있습니다. 여기서 교체할 항목이 없으므로 "개선된" 버블 정렬 알고리즘을 사용하는 경우(이전 단계에서 적어도 하나의 교환이 이루어졌는지 확인 포함) 이 단계가 마지막 단계입니다.

버블 정렬 자바 코드

버블소트 자바 구현

버블 정렬을 위한 두 가지 방법을 만들어 봅시다. 첫 번째는 bubbleSort(int[] myArray) 평면 1입니다. 매번 어레이를 통해 실행됩니다. 두 번째 최적화된 BubbleSort(int myArray[])는 내부 루프로 인해 스왑이 발생하지 않은 경우 알고리즘을 중지하여 최적화됩니다. 카운터는 정렬하는 동안 몇 단계를 수행했는지 보여줍니다. 여기에 버블 정렬 Java 구현이 있습니다.

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

버블 정렬 Java 알고리즘 작업의 결과:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

버블 정렬은 얼마나 효율적입니까?

버블 정렬은 구현하기 가장 쉬운 알고리즘 중 하나이지만 효율적이지 않습니다. 한 쌍의 중첩 루프가 필요합니다. 최악의 경우 알고리즘의 최적화된 버전에서도(데이터 세트의 각 요소가 원하는 요소의 역순임) 외부 루프는 데이터 세트의 n개 요소 각각에 대해 한 번씩 반복됩니다. 내부 루프는 처음에는 n 번, 두 번째에는 ( n-1 ) 등을 반복합니다. 따라서 모든 n 요소를 정렬하려면 루프를 n*(n-1)/2 번 실행해야 합니다. O(n ² ) 를 호출합니다.시간 복잡도는 알고리즘이 배열의 1000개 요소에 대해 약 500,000번의 비교를 수행함을 의미합니다. 그러나 버블 정렬 알고리즘은 메모리 사용에 매우 효과적이며(메모리 복잡성은 O(n) ) 거의 정렬된 작은 데이터 세트에 정말 좋습니다.

더 읽어보기:
이론 및 실제 정렬 알고리즘 Java 컬렉션 및 정렬 방법