자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Sorting and Searching(정렬, 이분검색과 결정알고리즘)_버블정렬)

 

2. 버블정렬

 

예시 입력 1 

6
13 5 11 7 23 15

예시 출력 1

5 7 11 13 15 23

 

 

버블정렬

 

버블 정렬(Bubble Sort)은 간단하고 이해하기 쉬운 정렬 알고리즘 중 하나입니다. 이 알고리즘은 인접한 두 원소를 비교하면서 필요한 경우 위치를 교환하여 배열을 정렬합니다. 버블 정렬은 배열을 왼쪽에서 오른쪽으로 순회하면서 큰 값을 오른쪽 끝으로 "버블링" 시키는 방식으로 동작합니다.

버블 정렬의 작동 과정은 다음과 같습니다:

1. 배열의 첫 번째 원소부터 시작하여 현재 원소와 다음 원소를 비교합니다.
2. 만약 현재 원소가 다음 원소보다 크다면 두 원소의 위치를 교환합니다.
3. 배열의 끝까지 이동한 후, 가장 큰 원소가 마지막 위치로 이동됩니다.
4. 위의 과정을 다시 반복하면서 두 번째로 큰 원소를 두 번째 마지막 위치로 이동시킵니다.
5. 이러한 과정을 반복하여 배열 전체를 정렬합니다.

// 배열을 순회하면서 인접한 두 원소를 비교하고 필요한 경우 위치를 교환하여 배열을 정렬합니다.
// 이러한 과정을 배열 전체에 대해 반복하면서 정렬을 완료합니다.
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        for (int i = 0; i < n - 1; i++) {
            swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 두 원소의 위치 교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // 만약 어떤 원소도 교환이 일어나지 않았다면 배열이 이미 정렬된 상태
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("원래 배열: " + Arrays.toString(arr));

        bubbleSort(arr);

        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

 

 

강의풀이

인전한 애들끼리 값을 비교해서 원소의 위치를 바꿔주는 것입니다.

이렇게해서 한번 다 돌고나면 오름차순일 경우 가장 큰 숫자가 맨 뒤로 갑니다.

 

 

만일 5다음에 그다음으로 큰 숫자인 21이 있다고 하면 맨 오른쪽으로 옮겨진 가장 큰 숫자 전까지만 비교합니다.

이렇게 비교 횟수가 하나 씩 줄어들어서 21이 4번 인덱스로 옮겨져야 합니다.

 

import java.util.Scanner;

public class Main {
    public int[] solution(int n, int[] arr ) {
   		// n이 5면 {0,1,2,3}해서 4바퀴 돌아야함 : n-1
        for (int i = 0; i < n-1; i++) {
        	// j는 반복문 도는 횟수가 하나씩 적어져야 합니다.
            // -i 한 이유: j는 하나씩 적게,
            // i가 1씩 커짐에 따라 j는 하나씩 감소한다
            for (int j = 0; j < n-i-1; j++) {
            	// 양 옆을 비교, 이웃한 두수를 비교
                // 앞 > 뒤, 뒤에가 작으면 스와프
                if(arr[j] > arr[j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        for (int x : T.solution(n, arr)) {
            System.out.print(x + " ");
        }
    }
}