bubble sort java java sorting algorithms code examples
이 튜토리얼은 주요 Java 정렬 알고리즘, 거품 정렬 구현 및 코드 예제와 함께 Java의 거품 정렬을 설명합니다.
정렬 알고리즘은 컬렉션의 요소를 특정 순서로 배치하는 알고리즘 또는 프로 시저로 정의 할 수 있습니다. 예를 들어, 정수의 ArrayList와 같은 숫자 컬렉션이있는 경우 ArrayList의 요소를 오름차순 또는 내림차순으로 정렬 할 수 있습니다.
마찬가지로 문자열 컬렉션의 문자열을 알파벳 또는 사전 순으로 정렬 할 수 있습니다. 이것이 Java의 정렬 알고리즘이 등장하는 곳입니다.
테스터를위한 Python 인터뷰 질문 및 답변
학습 내용 :
자바의 주요 정렬 알고리즘
정렬 알고리즘은 일반적으로 시간과 공간의 복잡성에 따라 평가됩니다. Java는 컬렉션 또는 데이터 구조를 정렬하거나 정렬하는 데 사용되는 다양한 정렬 알고리즘을 지원합니다.
아래 표는 최상의 / 최악의 경우 복잡성과 함께 Java에서 지원되는 주요 정렬 알고리즘을 보여줍니다.
| 시간 복잡성 | ||||
|---|---|---|---|---|
| 기수 정렬 | 선형 정렬 알고리즘. | O (nk) | O (nk) | O (nk) |
| 정렬 알고리즘 | 기술 | 최고의 사례 | 최악의 경우 | 평균 사례 |
| 버블 정렬 | 현재 요소를 인접한 요소와 반복적으로 비교합니다. 각 반복이 끝날 때 가장 무거운 요소가 적절한 위치에 버블 링됩니다. | 의 위에) | O (n ^ 2) | O (n ^ 2) |
| 삽입 정렬 | 컬렉션의 각 요소를 적절한 위치에 삽입합니다. | 의 위에) | O (n ^ 2) | O (n ^ 2) |
| 병합 정렬 | 분할 및 정복 접근 방식을 따릅니다. 컬렉션을 더 간단한 하위 컬렉션으로 나누고 정렬 한 다음 모든 것을 병합합니다. | O (nlogn) | O (nlogn) | O (nlogn) |
| 빠른 정렬 | 가장 효율적이고 최적화 된 정렬 기술. 분할 및 정복을 사용하여 컬렉션을 정렬합니다. | O (nlogn) | O (n ^ 2) | O (nlogn) |
| 선택 정렬 | 컬렉션에서 가장 작은 요소를 찾아 모든 반복이 끝날 때 적절한 위치에 배치합니다. | O (N ^ 2) | O (N ^ 2) | O (N ^ 2) |
| 힙 정렬 | 요소는 최소 힙 또는 최대 힙을 빌드하여 정렬됩니다. | O (nlogn) | O (nlogn) | O (nlogn) |
위 표에 제공된 정렬 기술 외에도 Java는 다음 정렬 기술도 지원합니다.
- 버킷 정렬
- 계산 정렬
- 쉘 정렬
- 빗 정렬
그러나 이러한 기술은 실제 응용 프로그램에서 거의 사용되지 않으므로 이러한 기술은이 시리즈의 일부가 아닙니다.
자바의 버블 정렬 기법에 대해 살펴 보겠습니다.
자바에서 버블 정렬
버블 정렬은 Java의 모든 정렬 기술 중 가장 간단합니다. 이 기술은 인접한 두 요소를 반복적으로 비교하고 원하는 순서가 아닌 경우 서로 교체하여 컬렉션을 정렬합니다. 따라서 반복이 끝날 때 가장 무거운 요소가 버블 링되어 올바른 위치를 주장합니다.
A (0), A (1), A (2), A (3),… .A (n-1)에 의해 주어진 목록 A에 n 개의 요소가있는 경우 A (0)은 A (1과 비교됩니다. ), A (1)은 A (2)와 비교됩니다. 첫 번째 요소가 두 번째 요소보다 큰지 비교 한 후 두 요소가 순서가 맞지 않으면 교체됩니다.
버블 정렬 알고리즘
버블 정렬 기법의 일반적인 알고리즘은 다음과 같습니다.
1 단계: i = 0 ~ N-1의 경우 2 단계를 반복합니다.
2 단계: J = i + 1 to N – 반복합니다
3 단계 : A (J)> A (i) 인 경우
A (J)와 A (i) 교체
(내부 for 루프의 끝)
(외부 for 루프 인 경우 종료)
4 단계 : 출구
이제 예시적인 예를 사용하여 버블 정렬 기법을 시연 해 보겠습니다.
크기 5의 배열을 가져 와서 버블 정렬 알고리즘을 설명합니다.
버블 정렬을 사용하여 배열 정렬
다음 목록이 정렬됩니다.
품질 보증 엔지니어 인터뷰 질문 및 답변
위에서 볼 수 있듯이 배열은 완전히 정렬되어 있습니다.
위의 그림은 아래와 같이 표 형식으로 요약 할 수 있습니다.
| 통과하다 | 정렬되지 않은 목록 | 비교 | 정렬 된 목록 |
|---|---|---|---|
| {3,6,11,4,15} | {11.4} | {3,6,4,11,15} | |
| 1 | {11, 3, 6,15,4} | {11.3} | {3,11,6,15,4} |
| {3,11,6,15,4} | {11.6} | {3,6,11,15,4} | |
| {3,6,11,15,4} | {11.15} | {3,6,11,15,4} | |
| {3,6,11,15,4} | {15.4} | {3,6,11,4,15} | |
| 두 | {3,6,11,4,15} | {3,6} | {3,6,11,4,15} |
| {3,6,11,4,15} | {6.11} | {3,6,11,4,15} | |
| 삼 | {3,6,4,11,15} | {3,6} | {3,6,4,11,15} |
| {3,6,4,11,15} | {6.4} | {3,4,6,11,15} | |
| {3,4,6,11,15} | 분류 됨 |
위의 예에서 볼 수 있듯이 가장 큰 요소는 모든 반복 / 패스마다 적절한 위치로 버블 링됩니다. 일반적으로 N-1에 도달하면 (여기서 N은 목록의 총 요소 수) 통과합니다. 전체 목록이 정렬됩니다.
버블 정렬 코드 예
아래 프로그램은 버블 정렬 알고리즘의 Java 구현을 보여줍니다. 여기에서는 숫자 배열을 유지하고 두 개의 for 루프를 사용하여 배열의 인접한 요소를 탐색합니다. 인접한 두 요소가 순서가 맞지 않으면 서로 바뀝니다.
import java.util.*; class Main{ // Driver method to test above public static void main(String args()) { //declare an array of integers int intArray() = {23,43,13,65,11,62,76,83,9,71,84,34,96,80}; //print original array System.out.println('Original array: ' + Arrays.toString(intArray)); int n = intArray.length; //iterate over the array comparing adjacent elements for (int i = 0; i intArray(j+1)) { int temp = intArray(j); intArray(j) = intArray(j+1); intArray(j+1) = temp; } //print the sorted array System.out.println('Sorted array: ' + Arrays.toString(intArray)); } } 산출:
원래 배열 : (23, 43, 13, 65, 11, 62, 76, 83, 9, 71, 84, 34, 96, 80)
정렬 된 배열 : (9, 11, 13, 23, 34, 43, 62, 65, 71, 76, 80, 83, 84, 96)
자주 묻는 질문
Q # 1) Java의 정렬 알고리즘은 무엇입니까?
대답: 정렬 알고리즘은 컬렉션의 요소를 원하는 방식으로 정렬하거나 정렬 할 수있는 알고리즘 또는 절차로 정의 할 수 있습니다.
다음은 Java에서 지원되는 일부 정렬 알고리즘입니다.
- 버블 정렬
- 삽입 정렬
- 선택 정렬
- 병합 정렬
- Quicksort
- 기수 정렬
- 힙 정렬
질문 # 2) Java에서 최고의 정렬 알고리즘은 무엇입니까?
대답: 병합 정렬은 Java에서 가장 빠른 정렬 알고리즘입니다. 실제로 Java 7은 Collections.sort () 메서드를 구현하기 위해 내부적으로 병합 정렬을 사용했습니다. 빠른 정렬은 또 다른 최상의 정렬 알고리즘입니다.
질문 # 3) Java에서 버블 정렬이란 무엇입니까?
대답: 버블 정렬은 Java에서 가장 간단한 알고리즘입니다. 버블 정렬은 항상 목록에서 인접한 두 요소를 비교하고 원하는 순서가 아닌 경우 서로 바꿉니다. 따라서 모든 반복 또는 패스가 끝날 때 가장 무거운 요소가 적절한 위치로 버블 링됩니다.
질문 # 4) 버블 정렬 N 인 이유두?
대답: 버블 정렬을 구현하기 위해 두 개의 for 루프를 사용합니다.
자바에서 목록을 인스턴스화하는 방법
수행 된 총 작업은 다음과 같이 측정됩니다.
내부 루프가 수행 한 작업량 * 외부 루프가 실행되는 총 횟수.
n 요소 목록의 경우 내부 루프는 각 반복에 대해 O (n)에 대해 작동합니다. 외부 루프는 O (n) 반복을 위해 실행됩니다. 따라서 전체 작업은 O (n) * O (n) = O (n두)
문 # 15) 버블 정렬의 장점은 무엇입니까?
답변 : 버블 정렬의 장점은 다음과 같습니다.
- 코딩과 이해가 쉽습니다.
- 알고리즘을 구현하려면 몇 줄의 코드가 필요합니다.
- 정렬은 제자리에서 수행됩니다. 즉, 추가 메모리가 필요하지 않으므로 메모리 오버 헤드가 없습니다.
- 정렬 된 데이터는 즉시 처리 할 수 있습니다.
결론
지금까지 Java의 Bubble Sort 정렬 알고리즘에 대해 설명했습니다. 또한 버블 정렬 기법을 사용하여 배열을 정렬하는 알고리즘과 자세한 그림을 살펴 보았습니다. 그런 다음 Java 프로그램을 Bubble Sort에 구현했습니다.
다음 자습서에서는 Java의 다른 정렬 기술을 계속 진행합니다.