Section 11. 버블 정렬

Section 11. 버블 정렬

현재 유데미와 코드스테이츠 강의를 통해 알고리즘을 학습하고 있습니다.
본 포스트는 해당 강의에 대한 내용 정리를 목적으로 합니다.

1. 버블 정렬이란

버블 정렬(bubble sort)는 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다.

버블 정렬 알고리즘은 아래와 같습니다.
1. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다(swap)
2. 두 번째 요소가 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다.(swap)
3. 1, 2를 마지막까지 반복합니다.(마지막에서 두 번째 요소와 마지막 요소를 비교)
4. 1 ~ 3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
5. 1 ~ 3의 과정을 첫 요소부터 다시 반복합니다.
6. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
7. 1 ~ 3의 과정을 총 n번(배열의 크기) 반복합니다.

이 모습이 마치 '거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부릅니다.

2. 문제 및 의사 코드

• 문제 :
  정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야합니다.
• 입력 1 : arr
  • number 타입을 요소로 갖는 배열
  • arr[i]는 정수
  • arr[i]의 길이는 1,000 이하
• 출력
  • number타입을 요소로 갖는 배열을 리턴해야 합니다.
  • 배열의 요소는 오름차순으로 정렬되어야 합니다.
  • arr[i] <= arr[j] (i<j)
• 의사 코드
  • i라는 변수를 가지고 배열의 맨 끝에서 루프를 시작해서 맨 앞에서 끝납니다.
  • 외부 루프 안에는 j라는 변수가 포함된 내부 루프가 있고, 내부 루프는 처음부터 i - 1 까지 실행됩니다.
  • 만약 내부 루프 안에서 arr[j]가 arr[j+1]보다 크다면 두 수의 값을 바꿉니다(swap!)
  • 정렬된 배열을 반환합니다.
  • 최적화를 진행합니다.(noSwaps)
• reference

function bubbleSort(arr){
	let noSwaps;
  	for(let i = arr.length; i > 0; i--){
    	noSwaps = true;
    	for(let j = 0; j < i - 1; j++){
        	if(arr[j] > arr[j+1]){
            	let temp = arr[j];
             	arr[j] = arr[j+1];
              	arr[j+1] = temp;
            	noSwaps = false;
            }
        }
      if(noSwaps) break;
    }
  return arr;
}

// 의사 코드는 동일하지만 다른 형태의 코드입니다.
function bubbleSort(arr){
  const swap = (arr, idx1, idx2) => {
  	[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };
	let noSwaps;
  	for(let i = arr.length; i > 0; i--){
    	noSwaps = true;
    	for(let j = 0; j < i - 1; j++){
        	if(arr[j] > arr[j+1]){
    		swap(arr, j, j+1)       
            noSwaps = false;
            }
        }
      if(noSwaps) break;
    }
  return arr;
}

3. 버블 정렬의 시간 복잡도

일반적으로는 n제곱입니다. 왜냐하면 중첩 루프가 있기 때문입니다.
그러나 데이터가 거의 정렬됐거나 이미 정렬이 끝난 상태에서 noSwaps 변수가 있는 위 코드를 사용할 때는 선형 시간(linear time)에 더 가깝습니다. 이럴 때는 O(n) 입니다.