[기본 정렬 알고리즘] 2. 버블 정렬(Bubble Sort)이란

 

 

 

1. 정렬 알고리즘이란? 

 

정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 그렇다면 왜 정렬 알고리즘을 사용해 데이터를 열거할까? 이유는 탐색하기 위해서다. 컴퓨터는 수 많은 데이터를 처리해야하는데 만약 데이터를 정렬하지 않는다면 데이터를 하나하나 일일이 탐색(순차 탐색)하여 원하는 데이터를 탐색해야 한다. 일반적으로 데이터를 삭제/삽입하기보다 탐색/조회하는 경우가 많기 때문에 매번 데이터를 탐색할 때마다 이런 식의 탐색은 매우 비효율적이다. 하지만 데이터가 일정한 규칙에 따라 순서대로 열거되었다면 다양한 탐색 방법을 이용하여 원하는 데이터를 빠르고 효율적으로 탐색할 수 있다. 

 

 

2. 버블 정렬(Bubble Sort)이란? 

 

- 버블 정렬이란 서로 인접한 두 원소의 선후관계를 확인하여 정렬하는 알고리즘이다. 배열의 맨 뒤쪽부터 차례대로 정렬된다. 

 

- 정렬 알고리즘 중 제자리 정렬 알고리즘 중 하나이다. 제자리 정렬 알고리즘이란 원소들의 갯수에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘으로, 버블 정렬의 경우 입력된 배열/리스트 중에 인접한 두 원소를 검사하여 앞의 원소 값이 뒤의 원소 값보다 큰 경우 두 원소의 위치를 교환하므로 입력 배열 외엔 추가적인 메모리가 필요하지 않다.

 

- 버블 정렬 순서

 

• 입력된 배열/리스트의 첫 인덱스의 값과 그 다음에 위치하는 두번째 인덱스 값을 비교한다.
• 앞의 원소의 값이 뒤의 원소의 값보다 크면 서로의 위치를 교환한다.
• 연속해서 다음 값과 비교하여 배열/리스트에서 가장 큰 값을 제일 뒷 부분에 정렬시킨다.
• 똑같은 방식으로 반복한다.

 

- 버블 정렬은 인접한 두 원소를 계속해 비교하므로 비교 횟수가 많고 상황에 따라 자리 교환 횟수도 많으므로 비효율적이다. 하지만 매우 직관적이고 간단한 알고리즘이다.

 

3. 버블 정렬의 예제 

 

 

 

4. 버블 정렬의 코드

 

public class Bubble {

	public int[] sort(int[] data) {
    
		int tmp = 0 ; // 데이터 교체할 때 임시 저장 변수

		for(int i = 0; i < data.length; i++){

			/* 마지막 항부터 정렬되므로 루프가 돈 만큼 연산하지 않음*/
			for( int j = 1; j < data.length - i; j++) { 
				if(arr[j-1] > arr[j]) // 인접한 두 원소 비교
					swap(data, j-1, j); // 위치 교환
			}
		}

		return data;
	}

	private static void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp; 
	}
}

 

 

 

5. 버블 정렬의 복잡도 

 

 

- 공간 복잡도 

  : 별도의 추가 공간을 사용하지 않고 입력된 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)의 공간 복잡도를 가진다.

 

- 시간 복잡도 

  : 총 두개의 for 루프를 이용하며 외부 루프를 통해 모든 인덱스에 접근하므로 기본적으로 O(N)의 시간 복잡도를 가진다. 이후 내부 루프를 통해 매 루프마다 인접한 원소의 크기를 비교하고 교환해야 하므로 추가적으로 O(N)의 시간이 필요하다. 그러므로 총 O(N²)의 시간 복잡도를 가진다. 

 

• 최선 시간 복잡도 : O(N²)
• 평균 시간 복잡도 : O(N²)
• 최악 시간 복잡도 : O(N²)