버블정렬(BubbleSort)

y20ng·2024년 8월 13일

알고리즘

목록 보기

2/6

버블 정렬(Bubble Sort)이란?

인접한 두 개의 원소를 비교한 후 교환하는 과정을 반복하여 데이터를 정렬하는 방식

💡정렬 과정

BubbleSort

첫번째 원소부터 인접한 원소와 비교하여 자리를 교환해가며 마지막 자리까지 이동
하나의 사이클이 끝나면 가장 큰 원소가 마지막 자리로 위치한다.
배열의 길이가 N이라고 할때 N-1번만큼 수행한다.

버블정렬 시간복잡도:

$O(N^2)$

아래의 코드를 살펴보면 (N-1)*(N-1-i) 번 반복하는 것을 알 수 있다.
따라서 O(N^2)의 시간복잡도를 갖는다.

function bubble_sort(arr[])
  set N = arr.size
  
  for i = 0 ... i < N - 1
    for j = 0 ... j < N - 1 - i
      if arr[j] > arr[j + 1]
        set tmp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = tmp
  
  return arr

📌 N-1까지만 수행하는 이유:

(N - 1)개가 제자리로 가게 된다면, 나머지 한 개는 남아있는 자리로 가게 될테니 N번을 돌지 않아도 된다!

💻 Java 코드 구현 예시

import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
		int[] arr = {5,2,6,1,7};
		int N = arr.length;
		System.out.println("정렬 전의 배열: "+Arrays.toString(arr));
			for(int i=0; i< N-1; i++) {    // i: 사이클마다 데이터가 정렬될 위치
			for(int j=0; j< N-i-1; j++) {  // j: 인접한 데이터와 비교할 인덱스
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
			System.out.println(i+1+"번째 사이클: "+ Arrays.toString(arr));
		}
		
	}
}