버블 정렬 (Bubble Sort)

Created on November 21, 2023

2023   ·   Study

💡 버블정렬 함수

먼저 알고리즘을 알고있지만 복붙이나 복습을 위해 찾아온 사람들을 위해 코드를 먼저 보여주겠다.

처음 보는거라면 꼭 아래로 내려가 이해해보도록 하자.

파이썬 (Python)

  • 오름차순 (Bubble Sort - Ascending)
def bubbleSort_ASC(arr):
    n = len(arr)
    for i in range(n-1, -1, -1):
        for j in range(0, i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
  • 내림차순 (Bubble Sort - Descending)
def bubbleSort_DESC(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-1, i, -1):
            if arr[j] > arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
    return arr

자바 (Java)

  • 오름차순 (Bubble Sort - Ascending)
public static void bubblesort_ASC(int[] arr) {
  int temp = 0;
  for(int i=0;i<arr.length;i++) {
    for(int j=0; j < arr.length - i - 1 ; j++) {
      if(arr[j]>arr[j+1]) {
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
      }
    }
  }
}
  • 내림차순 (Bubble Sort - Descending)
    public static void bubblesort_DESC(int[] arr) {
  int temp = 0;
  for(int i=0;i<arr.length;i++) {
    for(int j=0; j < arr.length - i - 1 ; j++) {
      if(arr[j]<arr[j+1]) {
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
      }
    }
  }
}

💡 버블정렬 (Bubble Sort) ?

버블 정렬은 원소를 정렬할 때 사용하며, 원소가 거품처럼 올라오는 것처럼 보여 버블 정렬이라는 이름이 붙여졌다.

💡 알고리즘 이해

가장 큰 수부터 차례대로 맨 뒤로 이동시켜 고정한다고 생각하면 쉽다.

각 단계에서 일어나는 일

다음 원소와 비교했을때, 지금의 원소가 더 크다면 순서를 바꾼다.

현재 원소와 다음 원소 비교 3 2 5 4 1
arr[j]>arr[j+1] 2 3 5 4 1
arr[j]<=arr[j+1] (변경 X) 2 3 5 4 1
arr[j]>arr[j+1] 2 3 4 5 1
arr[j]>arr[j+1] 2 3 4 1 5

한 단계마다 가장 큰 수가 제일 뒤로 가게 된다.

모든 단계에서 일어나는 일

각 단계에서 정해진 가장 큰 수를 고정하고 그 앞부분에서 단계를 또 시작한다.

정렬 전 5 2 3 4 1
1단계 2 3 4 1 5
2단계 2 3 1 4 5
3단계 2 1 3 4 5
4단계 1 2 3 4 5

💡 코드 이해

먼저, 배열의 두 원소를 바꾸는 함수부터 만들어보자.

다음 함수는 int타입 배열의 i번째 값과 j번째 값을 바꾸는 함수이다.

public static void swap (int[] arr, int i, int j) {
  int temp = arr[i]; // temp에 i번째 값 저장
  arr[i]=arr[j];		 // i번째에 j번째 값 저장
  arr[j]=temp;			 // j번째 값에 저장했던 원래의 i번째 값 넣기
}

미리 만들었던 swap 함수를 사용하여 bubblesort 함수를 만들어보자.

public static void bubblesort(int[] arr) {
  for(int i=0;i<arr.length;i++) {				// 단계를 i번 반복
    for(int j=0; j < arr.length - i - 1 ; j++) { // 고정된 것을 제외하고 반복
      if(arr[j]>arr[j+1]) { //현재 원소가 다음 원소보다 크면
        swap(arr,j,j+1); //다음 원소와 바꾼다.
      }
    }
  }
}

하지만 우리는 똑똑하니까 한번에 해보자.

두 함수를 합치면 다음과 같다.

public static void bubblesort(int[] arr) {
  for(int i=0;i<arr.length;i++) { 				
    for(int j=0; j < arr.length - i - 1 ; j++) {	
      if(arr[j]>arr[j+1]) { //오름차순일 경우 부호를 반대로 해주면 된다.
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
      }
    }
  }
}

💡 코드 테스트 - 백준 2750번: 수 정렬하기

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();
		
		bubblesort(arr);
		
		for(int i=0;i<n;i++) {
			System.out.println(arr[i]);
		}
		
	}
	
	public static void bubblesort(int[] arr) {
		  for(int i=0;i<arr.length;i++) {
		    for(int j=0; j < arr.length - i - 1 ; j++) {
		      if(arr[j]>arr[j+1]) {
						int temp = arr[j];
						arr[j] = arr[j+1];
						arr[j+1] = temp;
		      }
		    }
		  }
		}
}

Output

1
2
3
4
5

💡 시간복잡도

시간 복잡도가 무엇인지 모른다면 이 글을 참고하자.

[알고리즘] 시간 복잡도 (Time Complexity)

이미 정렬이 되어있는지에 상관 없이 무조건 for문을 2번 돌면서 비교를 하기 때문에

버블 정렬의 시간 복잡도는 best, worst, average case 모두 O(n^2) 이다.

💡 정리

장점

  • 구현이 아주 간단하다.
  • 알고리즘을 이해하기 쉽다.

단점

  • 하나의 원소를 옮기는데 여러번 교환해야 하는 일이 발생한다.
  • 이미 옳은 위치에 정렬되어있는 상태의 요소도 교환되는 일이 많다.
  • 정렬 알고리즘 중에서 가장 느리고 효율성이 떨어진다.

💡 결론

버블정렬 알고리즘은 처음 알고리즘을 공부하기엔 좋지만 너무 비효율적이기 때문에 쓸 일이 없다.