버블정렬

버블정렬

간단하지만 비효율적인 정렬 알고리즘이며 이 알고리즘은 인접한 두 원소를 비교하고 필요에 따라 서로 위치를 교환하고 리스트를 정렬합니다. 이름이 버블 정렬로 된 유래는 정렬 과정 속에서 이동하는 모습이 거품이 수면에 올라온 모습으로 보여 버블 정렬, 거품 정렬이라고 합니다.

정렬 과정

1. 전체 배열을 순회합니다.

2. 인접한 두 원소를 비교합니다

• 첫 번째 원소와 두 번째 원소를 비교하고, 필요에 따라 위치를 교환합니다.
• 이후 두 번째 원소와 세 번째 원소를 비교하고, 필요에 따라 위치를 교환합니다.
• 이 과정을 마지막 원소까지 진행합니다.
• 이 단계가 끝나면 가장 큰 원소가 배열의 맨 끝으로 이동하게 됩니다.

3. 위 과정을 반복합니다

•  다시 배열의 처음부터 끝까지 돌면서 인접한 두 원소를 비교하고 교환합니다.
• 이를 배열의 크기만큼 반복하면서 가장 큰 값들이 맨 끝부터 순차적으로 정렬됩니다.
• 반복할 때마다 정렬되는 영역은 점점 줄어듭니다.

4. 모든 반복이 완료되면 정렬이 완료됩니다.

 

이러한 과정을 통해 거품 정렬은 리스트의 모든 요소를 순회하면서 가장 큰 값(또는 작은 값)을 찾아 맨 끝으로 이동시키는 방식으로 정렬을 합니다. 

Java Code

void bubbleSort(int[] arr) {
    int temp = 0;
    for(int i = 0; i < arr.length; i++) {      
        for(int j= 1 ; j < arr.length-i; j++) {
            if(arr[j-1] > arr[j]) {             

                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

코드 분석

bubbleSort 함수는 정수형 배열 arr을 파라미터로 받습니다.
temp라는 임시 변수를 사용하여 값을 교환할 때 임시로 값을 저장합니다.
바깥쪽 for 루프(i 변수를 이용)는 정렬을 위해 배열의 각 요소를 한 번씩 확인합니다.
i는 이미 정렬된 부분을 나타냅니다. 각 반복마다 큰 값들이 맨 뒤로 이동하므로, arr.length - i 만큼만 반복하면 됩니다.
안쪽 for 루프(j 변수를 이용)는 인접한 두 원소를 비교하여 필요에 따라 위치를 교환합니다.
j-1과 j번째 요소를 비교하여, 만약 이전 요소(arr [j-1])가 더 크다면 위치를 교환합니다.
교환할 때 temp 변수를 이용하여 두 값을 스왑합니다.
정렬이 완료된 배열을 Arrays.toString() 메서드를 통해 출력합니다.