[Java] 버블 정렬 [Bubble Sort]
오늘은 알고리즘중 하나인
버블 정렬에 대해서 배워보겠습니다.
버블 정렬은 인접해있는 두 항목의 값을
비교해서 기준에 만족하면 서로의 값을 교환하는
정렬 방법입니다.
예를들어 배열에 6,5,4,2,1이 있다고 가정하면
처번쨰 턴에는 제일 큰 수를 오른쪽에 배치하고,
다음턴으로 넘어갑니다.
그 다음 큰 수를 같은 방법으로 오른쪽에 배치하고
정렬이 될 때까지 과정을 반복합니다.
코드를 살펴볼까요?
for(int i = 0; i< arr.length; i++) {
int temp = 0;
for(int j = 0; j < (arr.length-1);j++)
if(arr[j+1] < arr[j]) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;}}
인접해있는 두 값을 비교 후 더 큰 값을 뒤로 보냅니다.
이떄는 변수하나를 선언하여 그 값을 넣어주고
두 값을 바꿔줘야 뒤의 수가 앞에 수랑 같지 않게 됩니다.
이 과정을 배열의 길이만큼 반복하면 모두 정렬될 것입니다.
이떄 안쪽의 반복문의 길이는 배열의 길이에서 1을 뺸값을 넣어줍니다.
바꿀 때 인덱스 + 1을 넣어주기 떄문에 마지막 인덱스에서는
없는 인덱스와 비교하게 되기 때문입니다.
잘 정렬된 모습입니다.
public class PMain1_ {
public static void bubbleSort(int arr[]) {
System.out.print("기존 배열: ");
for (int i= 0 ; i < arr.length; i++) {
System.out.print(arr[i]);
}
for(int i = 0; i< arr.length; i++) {
int temp = 0;
for(int j = 0; j < (arr.length-1);j++)
if(arr[j+1] < arr[j]) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;}}
System.out.print("\n정렬된 배열: ");
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);}}
public static void main(String[] args) {
int [] arr = new int []{6,3,2,1,4};
bubbleSort(arr);}}
전체 코드입니다.
하지만 이러한 정렬은
성능에서 크게 효과를 보지 못합니다.
왜냐하면 Arrays.sort(arr);
기능을 쓰면 바로 정렬할 수 있기 때문입니다.
버블 정렬에 대해서 배워봤습니다!