버블 정렬(bubble sort)

여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘

알고리즘

1. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꾼다. (swap)
2. 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꾼다. (swap)
3. 1, 2를 마지막까지 반복 (마지막에서 두 번째 요소와 마지막 요소를 비교)
4. 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려남
5. 1~3의 과정을 첫 요소부터 다시 반복
6. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려남
7. 1~3의 과정을 총 n번(배열의 크기) 반복

예시

arr = [ 1, 4, 2, 5, -2, 3 ]를 오름차순 정렬하는 과정

Step1

• 배열의 첫번째 요소와 두번째 요소 비교를 반복함
• Step1의 결과, 가장 큰 요소가 맨 마지막으로 밀려남
  

Step2

• 가장 큰 요소가 맨 마지막으로 밀려났기 때문에 비교하는 횟수가 하나 줄어듦
• Step2의 결과, 두 번째로 큰 요소가 자리잡음
  

Step3

• 두 번째로 큰 요소가 자리잡았기 때문에 비교하는 횟수가 하나 더 줄어듦
• Step3의 결과, 세 번째로 큰 요소가 자리잡음
  

Step4

• 세 번째로 큰 요소가 자리잡았기 때문에 비교하는 횟수가 하나 더 줄어듦
• Step4의 결과, 네 번째로 큰 요소가 자리잡음
  

Step5

• 네 번째로 큰 요소가 자리잡았기 때문에 비교하는 횟수가 하나 더 줄어듦
• Step5의 결과, 배열이 오름차순으로 정렬됨
  

코드 작성해보기

주의사항

temp변수에 앞의 요소 일단 저장해두기

앞의 요소에 뒤의 요소를 바로 할당할 수 없음

❌ 앞의 요소에 뒤의 요소를 바로 할당했을 때

for(let j = 0; j < ( arr.length - i -1 ); j++){ 
  if(arr[j] > arr[j+1]){  
    arr[j] = arr[j + 1] // 여기서 이미 arr[j]가 arr[j+1]로 재할당됨
    arr[j+1] = arr[j] //앞의 코드로 인해 arr[j+1]에 재할당된 arr[j]가 할당됨. 즉 arr[j+1]에 arr[j+1]이 할당됨
  }
}

⭕️ 임시 변수 temp을 이용해서 앞의 요소를 먼저 저장하기

   for(let j = 0; j < ( arr.length - i -1 ); j++){ 
     if(arr[j] > arr[j+1]){  
       let temp = arr[j]
       arr[j] = arr[j + 1]
       arr[j+1] = temp
     }
   }

완성본

const bubbleSort = function (arr) {
  
 //배열의 크기만큼 비교 반복하기
 for(let i = 0; i < arr.length; i++){
   
   // 마지막 i번째 요소는 이미 자리잡았음
   for(let j = 0; j < ( arr.length - i -1 ); j++){ 
     
     // 앞의 요소가 뒤의 요소보다 큰지 확인
     if(arr[j] > arr[j+1]){  
       
       // 앞의 요소가 뒤의 요소보다 크면 두 요소를 바꿈
       let temp = arr[j]
       arr[j] = arr[j + 1]
       arr[j+1] = temp
     }
   }
 }
 return arr;
}

코드 최적화하기

문제점

앞선 코드의 경우, 배열 정렬이 끝나더라도 코드가 계속 실행된다는 문제가 있음
따라서, 배열 정렬이 끝나면 코드가 더이상 실행되지 않도록 수정하기

수정한 코드

const bubbleSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  let temp;
  let isSwapped = false;

  for(let i = 0; i < arr.length; i++) {
    
    //1. i번째가 처음 실행될 때 isSwapped를 false로 초기화
    //3. arr[j] <= arr[j+1] 일 때 isSwapped는 false가 됨
    isSwapped = false; 
    
    for(let j = 0; j < arr.length; j++) {
      //2. arr[j] <= arr[j+1] 되면 if문을 실행하지 않고 다음 j로 넘어감.
      if(arr[j] > arr[j + 1]) { 
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        isSwapped = true;
      }
    }
    
    //더이상 정렬을 하지 않아도 되면 코드 실행하지 않기
    if(!isSwapped){
      break;
    }
  }
  return arr;
};

참고자료
Bubble Sort algorithm using JavaScript