자바 버블 정렬을 작성하는 방법
프로그래머가 버블 정렬에 대해 이야기할 때 그들은 아마도 여러분이 인생의 어느 시점에서 날려본 물방울에 대해 이야기하는 것이 아닙니다. 그들은 항목 목록을 정렬하는 데 사용되는 정렬 알고리즘에 대해 이야기하고 있습니다.
이 가이드에서는 버블 정렬과 작동 방식에 대해 이야기할 것입니다. 이 알고리즘이 코드로 변환되는 방식을 이해할 수 있도록 Java를 사용하여 버블 정렬을 구현합니다. 더 이상 고민하지 않고 Java 버블 정렬에 대해 알아보겠습니다.
자바 버블 정렬이란 무엇입니까?
버블 정렬은 인접한 요소를 비교하고 잘못된 순서로 나타날 경우 교체하여 값을 정렬하는 알고리즘입니다.
이 프로세스는 목록의 모든 항목이 올바르게 정렬될 때까지 반복됩니다. 버블 정렬을 사용하여 목록을 오름차순 또는 내림차순으로 정렬할 수 있습니다.
버블 정렬은 알고리즘 수업에서 처음 배우는 정렬입니다. 삽입 정렬이나 선택 정렬과 같은 다른 정렬보다 이해하기 쉽고 정렬 알고리즘에 대한 좋은 소개를 제공하기 때문입니다.
버블 정렬은 데이터가 이미 거의 정렬되었을 때 가장 효과적입니다. 그러나 데이터가 전혀 정렬되지 않은 경우 다른 유형의 정렬이 더 효율적일 수 있습니다.
버블 정렬은 어떻게 작동합니까?
Java 버블 정렬을 위한 코드 작성을 시작하기 전에 먼저 이 알고리즘이 실제로 어떻게 구현되는지 이해해야 합니다.
다음 목록을 고려하십시오.
참가자의 81%는 부트캠프에 참석한 후 기술 직업 전망에 대해 더 자신감을 느꼈다고 말했습니다. 지금 부트캠프에 참여하십시오.
부트캠프 졸업생은 부트캠프 시작부터 첫 직장을 찾는 데까지 6개월도 채 걸리지 않았습니다.
| 5 | 9 | 2 | 7 |
버블 정렬은 목록의 첫 번째 요소와 두 번째 요소를 비교하는 것으로 시작합니다.
첫 번째 요소가 두 번째 요소보다 크면 이러한 요소가 위치를 바꿉니다. 이 경우 5는 9보다 크지 않으므로 요소는 동일한 위치에 유지됩니다.
그런 다음 정렬은 목록의 다음 두 항목을 비교합니다. 9는 2보다 크므로 다음 두 숫자가 바뀝니다.
| 5 | 2 | 9 | 7 |
이 프로세스는 목록의 모든 항목이 비교될 때까지 반복됩니다. 이 경우 수행할 비교가 하나 더 있습니다. 9가 7보다 큽니까? 9는 7보다 크므로 다음 숫자가 바뀝니다.
| 5 | 2 | 7 | 9 |
우리 목록이 거의 주문되었습니다. 모든 항목이 비교되면 모든 요소가 정렬될 때까지 버블 정렬이 다시 시작됩니다.
5는 2보다 크므로 이 숫자는 서로 바뀝니다.
| 2 | 5 | 7 | 9 |
이제 목록이 올바르게 정렬되었습니다. 버블 정렬은 목록의 끝에 도달할 때까지 숫자를 계속 비교한 다음 중지합니다. 이것이 버블 정렬의 전부입니다. 일단 익숙해지면 사용하기 쉬운 알고리즘입니다.
자바 버블 정렬을 작성하는 방법
이론을 아는 것은 한 가지이지만 Java 버블 정렬에 대해 배우기 위해 여기에 왔습니다. Java에서 버블 정렬을 구현하는 방법에 대해 논의하는 것이 가장 좋습니다.
버블 정렬에는 두 가지 유형이 있습니다.
- 표준 거품 정렬
- 최적화된 거품 정렬
표준 버블 정렬은 배열이 정렬된 경우에도 가능한 모든 비교를 수행합니다. 이렇게 하면 버블 정렬을 실행하는 데 걸리는 시간이 늘어납니다. 이것은 정렬을 덜 효율적으로 만듭니다.
최적화된 거품 정렬은 추가 변수를 사용하여 목록이 정렬되었는지 여부를 추적합니다. 이렇게 하면 목록이 정렬되자마자 정렬을 중지할 수 있습니다.
표준 버블 정렬을 작성하는 것으로 시작하겠습니다.
표준 거품 정렬
시작하려면 Arrays 라이브러리를 코드로 가져올 것입니다. 나중에 코드에서 이것을 사용하여 정렬된 숫자 목록을 콘솔에 출력할 것입니다.
import java.util.Arrays;
이제 문제가 해결되었으므로 알고리즘 작성을 시작할 수 있습니다.
Java 프로그램의 코드를 저장하는 BubbleSort라는 클래스와 정렬을 수행하는 함수를 정의하는 것으로 시작하겠습니다.
class BubbleSort {
void sortNumbers(int array[]) {
int size = array.length;
for (int item = 0; item < size - 1; item++) {
for (int j = 0; j < size - item - 1; j++) {
if (array[j] > array[j + 1]) {
int temporary = array[j];
array[j] = array[j + 1];
array[j + 1] = temporary;
}
}
}
}
}
sortNumbers라는 함수를 선언했습니다. 변수를 매개변수로 받아들입니다. 이 함수는 우리가 지정한 숫자 목록의 크기를 계산하는 것으로 시작합니다.
이것이 계산되면 for 루프가 초기화됩니다. 이 루프는 배열의 모든 항목을 살펴봅니다. 배열의 각 항목을 비교할 수 있는 또 다른 for 루프를 초기화합니다.
목록 왼쪽에 있는 항목이 오른쪽에 있는 숫자보다 크면 값이 바뀝니다. 그렇지 않으면 아무 일도 일어나지 않습니다.
"임시"라는 변수에 왼쪽 값을 할당하여 이 교환을 수행합니다. 비교의 왼쪽에 있던 값을 오른쪽에 할당합니다. 그런 다음 왼쪽의 값에 임시 변수의 값이 할당됩니다.
6과 5가 비교된다면, 그것들은 교환될 것입니다. 따라서 목록은 6, 5와 같이 표시됩니다.
우리 프로그램은 아직 아무것도 하지 않습니다. 우리는 함수를 호출하고 정렬할 목록을 제공하는 메인 프로그램을 작성하지 않았습니다.
sortNumbers 아래에 다음 코드를 추가합니다. 코드의 기능:
public static void main(String args[]) {
int[] toSort = { 5, 9, 2, 7 };
BubbleSort sortingAlgorithm = new BubbleSort();
sortingAlgorithm.sortNumbers(toSort);
System.out.println(Arrays.toString(toSort));
}
정렬하려는 값 목록을 저장하는 toSort라는 변수를 선언했습니다. 그런 다음 다음 코드 줄에서 sortNumbers를 호출하는 데 사용하는 sortingAlgorithm이라는 BubbleSort 클래스의 인스턴스를 선언했습니다. 함수. 이 함수가 호출되면 목록이 정렬됩니다.
마지막으로 Arrays.toString()을 사용합니다. 메서드를 사용하여 목록을 문자열로 변환하여 콘솔에 출력할 수 있습니다. 코드 반환:
[2, 5, 7, 9]
이제 정렬된 배열이 생겼습니다!
최적화된 버블 정렬
코드를 더 효율적으로 만드는 방법이 있습니다. 바로 지금, 우리의 정렬은 가능한 모든 비교를 할 때까지 계속됩니다. 즉, 배열이 정렬되더라도 해당 비교가 완료될 때까지 정렬이 계속됩니다.
코드에 새 변수를 추가하여 이 동작을 방지할 수 있습니다. 이렇게 하면 목록이 바뀌면 정렬을 중지할 수 있습니다. 이 변수를 sortNumbers에 추가해 보겠습니다. 이전 기능:
class BubbleSort {
void sortNumbers(int array[]) {
int size = array.length;
for (int item = 0; item < size - 1; item++) {
boolean hasSwapped = false;
for (int j = 0; j < size - item - 1; j++) {
if (array[j] > array[j + 1]) {
int temporary = array[j];
array[j] = array[j + 1];
array[j + 1] = temporary;
hasSwapped = true;
}
}
if (hasSwapped == false) {
break;
}
}
}
}
코드를 세 가지 변경했습니다. 첫 번째 for 루프 내에서 "hasSwapped"라는 변수를 선언했습니다. 이 변수는 스왑이 이루어졌는지 여부를 추적합니다. 기본적으로 이 변수는 "거짓"으로 설정됩니다. 스왑이 이루어지면 이 변수의 값은 "true"로 설정됩니다.
for 루프의 끝에 hasSwapped가 false인지 확인하기 위해 if 문을 추가했습니다. 스왑이 수행되지 않은 경우 배열이 정렬됩니다. "break" 키워드를 사용하여 hasSwapped가 false인 경우 루프 실행을 중지합니다.
이전에 작성한 메인 프로그램을 사용하여 코드를 실행하고 어떤 일이 일어나는지 봅시다:
[2, 5, 7, 9]
목록이 정렬되었지만 이번에는 알고리즘이 더 효율적입니다. 정렬할 값이 더 많은 더 큰 목록을 사용하면 이 알고리즘의 우수한 성능이 더 명확해집니다. 이제 자바로 최적화된 버블 정렬을 작성했습니다!
결론
버블 정렬은 목록을 오름차순 또는 내림차순으로 정렬하는 데 사용됩니다. 인접한 값을 비교하고 순서가 잘못된 경우 교환하여 작동합니다.
버블 정렬에는 표준 및 최적화의 두 가지 유형이 있습니다. 표준 버블 정렬은 미리 정의된 수의 스왑을 수행하는 반면 최적화된 버블 정렬은 목록이 정렬될 때까지 정렬을 유지합니다.
이제 전문가처럼 Java로 버블 정렬을 작성할 준비가 되었습니다!