Java에서 버블 정렬 구현

상당히 많은 수의 정렬 알고리즘이 있으며 그 중 다수는 매우 구체적이며 좁은 범위의 문제를 해결하고 특정 유형의 데이터를 사용하기 위해 개발되었습니다. 그러나 이 모든 다양성 중에서 가장 간단한 알고리즘은 당연히 모든 프로그래밍 언어로 구현될 수 있는 버블 정렬입니다. 단순함에도 불구하고 이는 다소 복잡한 알고리즘의 기초가 됩니다. 똑같이 중요한 또 다른 장점은 단순성이므로 추가 문헌 없이도 즉시 기억하고 구현할 수 있다는 것입니다.

소개

전체 현대 인터넷은 데이터베이스에 수집된 수많은 다양한 유형의 데이터 구조로 구성됩니다. 여기에는 사용자의 개인 데이터부터 고도로 지능적인 자동화 시스템의 의미론적 핵심까지 모든 종류의 정보가 저장됩니다. 말할 필요도 없이, 데이터 정렬은 이 엄청난 양의 구조화된 정보에서 매우 중요한 역할을 합니다. 정렬은 데이터베이스의 정보를 검색하기 전 필수 단계일 수 있으며 정렬 알고리즘에 대한 지식은 프로그래밍에서 매우 중요한 역할을 합니다.

기계의 눈과 사람의 눈을 통한 분류

높이가 다른 5개의 열을 오름차순으로 정렬해야 한다고 가정해 보겠습니다. 이러한 열은 모든 종류의 정보(주가, 통신 채널 대역폭 등)를 의미할 수 있으며, 이를 더욱 명확하게 하기 위해 이 작업에 대한 자신만의 버전을 제시할 수 있습니다. 예를 들어, 어벤저스를 키별로 정렬하겠습니다. 컴퓨터 프로그램과 달리 정렬은 어렵지 않습니다. 전체 그림을 볼 수 있고 높이별 정렬이 성공적으로 완료되기 위해 어떤 영웅을 어디로 이동해야 하는지 즉시 파악할 수 있기 때문입니다. 이 데이터 구조를 오름차순으로 정렬하려면 헐크와 아이언맨의 위치를 ​​바꾸면 된다는 것을 이미 짐작하셨을 것입니다.

완료!

그러면 정렬이 성공적으로 완료됩니다. 그러나 컴퓨터는 당신과 달리 다소 어리석고 전체 데이터 구조를 전체적으로 보지 못합니다. 제어 프로그램은 한 번에 두 값만 비교할 수 있습니다. 이 문제를 해결하려면 그녀는 두 개의 숫자를 메모리에 저장하고 비교 작업을 수행한 다음 모든 데이터가 분석될 때까지 다른 숫자 쌍으로 이동하는 등의 작업을 수행해야 합니다. 따라서 모든 정렬 알고리즘은 다음 세 단계의 형태로 매우 단순화될 수 있습니다.

• 두 요소를 비교하십시오.
• 그 중 하나를 교환하거나 복사하십시오.
• 다음 요소로 이동합니다.

다양한 알고리즘은 이러한 작업을 다양한 방식으로 수행할 수 있지만 계속해서 버블 정렬의 작동 방식을 고려하겠습니다.

버블 정렬 알고리즘

버블 정렬은 가장 간단한 것으로 간주되지만 이 알고리즘을 설명하기 전에 기계처럼 일정 기간 동안 두 영웅만 서로 비교할 수 있다면 어벤저스를 높이별로 정렬하는 방법을 상상해 보겠습니다. 아마도 다음과 같은 방법으로 (가장 최적의) 작업을 수행할 것입니다.

• 배열의 요소 0(Black Widow)으로 이동합니다.
• 0 요소(Black Widow)와 첫 번째 요소(Hulk)를 비교합니다.
• 위치 0의 요소가 더 높으면 이를 교체합니다.
• 그렇지 않고 위치 0의 요소가 더 작으면 해당 위치에 그대로 둡니다.
• 오른쪽 위치로 이동하여 비교를 반복합니다. (헐크와 캡틴 비교)

이러한 알고리즘을 사용하여 한 번에 전체 목록을 살펴본 후에는 정렬이 완전히 완료되지 않습니다. 그러나 반면에 목록에서 가장 큰 요소는 가장 오른쪽 위치로 이동됩니다. 가장 큰 요소를 찾으면 해당 요소를 맨 끝까지 이동할 때까지 끊임없이 장소를 변경하기 때문에 이런 일이 항상 발생합니다. 즉, 프로그램이 배열에서 헐크를 "발견"하자마자 헐크를 목록의 맨 끝으로 이동시킵니다. 이것이 바로 이 알고리즘을 버블 정렬이라고 부르는 이유입니다. 그 이유는 해당 연산의 결과로 목록에서 가장 큰 요소가 배열의 맨 위에 있게 되고 모든 작은 요소는 한 위치 왼쪽으로 이동되기 때문입니다. 정렬을 완료하려면 배열의 시작 부분으로 돌아가 위에서 설명한 5단계를 다시 반복하고 다시 왼쪽에서 오른쪽으로 이동하면서 필요에 따라 요소를 비교하고 이동해야 합니다. 하지만 이번에는 배열이 끝나기 한 요소 전에 알고리즘을 중지해야 합니다. 왜냐하면 가장 큰 요소(Hulk)가 절대적으로 가장 오른쪽 위치에 있다는 것을 이미 알고 있기 때문입니다. 따라서 프로그램에는 두 개의 루프가 있어야 합니다. 더 명확하게 하기 위해 프로그램 코드를 검토하기 전에 다음 링크에서 버블 정렬 작동 방식에 대한 시각화를 볼 수 있습니다. 버블 정렬 작동 방식 시각화

Java에서 버블 정렬 구현

Java에서 정렬이 작동하는 방식을 보여주기 위한 프로그램 코드는 다음과 같습니다.

• 5개 요소의 배열을 생성합니다.
• 복수 자의 부상을 업로드합니다.
• 배열의 내용을 표시합니다.
• 버블 정렬을 구현합니다.
• 정렬된 배열을 다시 표시합니다.

아래 코드를 볼 수 있고 즐겨 사용하는 IntelliJ IDE에 다운로드할 수도 있습니다. 아래에서 분석됩니다.

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

코드의 자세한 설명에도 불구하고 프로그램에 제시된 일부 메서드에 대한 설명을 제공합니다. 프로그램의 주요 작업을 수행하는 주요 메서드는 ArrayBubble 클래스에 작성됩니다. 클래스에는 생성자와 여러 메서드가 포함되어 있습니다.

• into– 배열에 요소를 삽입하는 방법;
• printer– 배열의 내용을 한 줄씩 표시합니다.

• toSwap– 필요한 경우 요소를 재배열합니다. 이를 위해 dummy첫 번째 숫자의 값이 기록되는 임시 변수가 사용되며 첫 번째 숫자 대신 두 번째 숫자의 값이 기록됩니다. 그런 다음 임시 변수의 내용이 두 번째 숫자에 기록됩니다. 이는 두 요소를 교환하는 표준 기술입니다.

  마지막으로 주요 방법은 다음과 같습니다.

• bubbleSorter– 주요 작업을 수행하고 배열에 저장된 데이터를 정렬하므로 별도로 다시 표시하겠습니다.

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

out여기서는 두 개의 카운터, 즉 external 및 Internal 에 주의해야 합니다 in. 외부 카운터는out 배열의 끝에서부터 값을 열거하기 시작하고 새로운 패스가 있을 때마다 점차적으로 1씩 감소합니다. out각각의 새로운 패스에서 변수는 이미 배열의 오른쪽에 정렬된 값에 영향을 주지 않도록 왼쪽으로 더 이동됩니다. 내부 카운터는in 배열의 시작 부분부터 값을 열거하기 시작하고 새로운 패스마다 점차적으로 1씩 증가합니다. (현재 패스에서 마지막으로 분석된 요소)에 in도달할 때까지 증가가 발생합니다. out내부 루프는 in인접한 두 셀 in과 를 비교합니다 in+1. in보다 큰 숫자가 에 저장되면 메소드 in+1가 호출되어 toSwap이 두 숫자의 위치를 ​​바꿉니다.

결론

버블 정렬 알고리즘은 가장 느린 알고리즘 중 하나입니다. 배열이 N개의 요소로 구성된 경우 첫 번째 패스에서는 N-1 비교가 수행되고, 두 번째 패스에서는 N-2, 그 다음에는 N-3 비교가 수행됩니다. 즉, 총 패스 수는 다음과 같습니다: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 따라서 정렬할 때 알고리즘은 약 0.5x(N ^2) 비교를 수행합니다. N = 5인 경우 비교 횟수는 대략 10회이고, N = 10인 경우 비교 횟수는 45회로 늘어납니다. 따라서 요소 수가 증가하면 정렬의 복잡성도 크게 늘어납니다. 알고리즘의 속도는 패스 수뿐만 아니라 수행해야 하는 순열 수의 영향을 받습니다. 무작위 데이터의 경우 순열 수는 평균 (N^2) / 4이며 이는 패스 수의 약 절반입니다. 그러나 최악의 경우 순열 수는 N^2 / 2일 수도 있습니다. 이는 데이터가 처음에 역순으로 정렬된 경우입니다. 이것이 다소 느린 정렬 알고리즘이라는 사실에도 불구하고 이것이 어떻게 작동하는지 알고 이해하는 것이 매우 중요하며, 앞서 언급했듯이 더 복잡한 알고리즘의 기초가 됩니다. 쯧쯧!