[알고리즘] 버블정렬

 

버블정렬

 

버블 정렬은 인접한 두 요소를 비교하여, 앞 요소가 뒤 요소보다 클 경우 두 요소의 위치를 교환하는 방식으로 정렬하는 알고리즘이다.

이를 반복하면 가장 큰 수가 배열의 맨 뒤로 이동하게 됩니다. 각 순회가 끝날 때마다 정렬되지 않은 부분 중 가장 큰 요소가 마지막 위치에 고정된다.

 

버블정렬은 외부루프에서는 n-1번을 돌고 내부 루프에서는 n-1-i 번의 비교를 수행하므로 시간복잡도는 N^2이다.

삽입정렬과 마찬가지로 배열이 길어질수록 비효율적이나 구현은 간단하다. 

 

 

 

Scanner sc = new Scanner(System.in);

int n = Integer.parseInt(sc.next());
int[] arr = new int[n];

for(int i=0; i<n; i++){
    arr[i] = sc.nextInt();
}

//버블정렬 알고리즘 구현
for(int i=0; i<n-1; i++){
    for(int j=0; j<n-1-i; j++){
        if(arr[j] > arr[j+1]){
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
    }
}

// 정렬된 배열 출력
for(int i=0; i<n; i++){
    System.out.print(arr[i] + " ");
}