// JavaScript 구현 (Swapped 최적화 적용)
function bubbleSort(arr) {
  const n = arr.length;
  console.log("초기 배열:", arr);
  
  for (let i = 0; i < n - 1; i++) {
    let swapped = false; // 이번 턴에 Swap이 일어났는지 추적
    
    // 매 패스마다 가장 큰 값이 뒤로 확정되므로 끝에서 i만큼 빼줌
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 배열 구조 분해 할당을 이용한 Swap
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    
    // 한 바퀴 돌았는데 단 한 번도 안 바뀌었다면? 이미 정렬 완료!
    if (!swapped) break;
  }
  
  return arr;
}

const arr = [5, 3, 1, 4, 2];
console.log("정렬 결과:", bubbleSort(arr));