코드카타 week 5_day 2

버블정렬(Bubble Sort)

• 버블정렬: 인접한 데이터를 교환해서 정렬하는 알고리즘.
  알고리즘의 정렬되는 모습이 마치 거품처럼 보인다고 해서 붙여진 이름입니다.

예제) 정렬되지 않은 수 6 5 3 2 8 이 있을 때, 인접한 두 수를 비교하여 더 큰 것을 우측으로 이동시킵니다.

• index 0 <-> 1: 6 5 3 2 8 -> 5 6 3 2 8
• index 1 <-> 2: 5 6 3 2 8 -> 5 3 6 2 8
• index 2 <-> 3: 5 3 6 2 8 -> 5 3 2 6 8
• index 3 <-> 4: 5 3 2 6 8 -> 5 3 2 6 8
  이렇게 제일 마지막 두 수 까지 비교하면, 제일 큰 수가 제일 마지막 index에 위치하는 것을 알 수 있습니다.
• 다시 처음부터 시작합니다.
  5 3 2 6 8 -> 3 5 2 6 8
• 3 5 2 6 8 -> 3 2 5 6 8
• 3 2 5 6 8 -> 3 2 5 6 8
  이번 교환에는 index 2까지 비교하고 멈추면 됩니다. 마지막 index는 이미 제일 큰 수가 정렬된 상태이기 때문입니다. 이런식으로 계속 비교하고 교체하면 됩니다.!

문제
nums라는 배열을 주면, 버블정렬 알고리즘으로 배열을 정렬해주세요.

const bubbleSort = nums => {
  // 여기에 코드를 작성해주세요.
}

풀이

1. 첫번째 루프

• index j와 index j+1의 값을 비교하여 index j의 값이 크면 서로 값을 바꾼다

let nums = [6, 5, 3, 2, 8]
for(let j=0; j<nums.length; j++){
  if(nums[j] > nums[j+1]){
    [nums[j], nums[j+1]] = [nums[j+1], nums[j]];
  }
  console.log(j, nums)
}  

2. j번째 루프

• 순회하려는 배열nums의 마지막 index가 1씩 감소해야 하도록 하는 index j에 대한 for문으로 1.을 감싼다

let nums = [6, 5, 3, 2, 8]
  for(let i=nums.length; i>0; i--){
    for(let j=0; j<i; j++){
      if(nums[j] > nums[j+1]){
   		[nums[j], nums[j+1]] = [nums[j+1], nums[j]];
  	  }  
    }
    console.log(i, nums)
  }

결과

const bubbleSort = nums => {
  for(let i=nums.length; i>0; i--){
    for(let j=0; j<i; j++){
      if(nums[j] > nums[j+1]){
   		[nums[j], nums[j+1]] = [nums[j+1], nums[j]];
  	  }  
    }
  }
  return nums;
}

다른 풀이 by ChatGPT

const bubbleSort = (nums) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
      }
    }
  }
  return nums;
}

표현식이 조금 다를 뿐 동일한 풀이방법임을 알 수 있었다