04_bubbleSort

---

문제

---

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다.

버블 정렬 알고리즘은 아래와 같습니다.

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

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

입력

---

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr[i]의 길이는 1,000 이하

출력

---

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

---

• 위에서 설명한 알고리즘을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

---

let output = bubbleSort([2, 1, 3]);
console.log(output); // --> [1, 2, 3]

Advanced

---

• 아래의 힌트를 바탕으로 (최선의 경우) 수행 시간을 단축할 수 있도록 코드를 수정해보세요.
• 위에서 설명된 알고리즘 1~3의 과정 중 어떤 요소도 위치가 바뀌지 않은 경우, 배열이 정렬된 상태라는 것을 알 수 있습니다.

수도코드

---

sort사용을 하지 않고 bubble처럼 순차적으로 계산
for문으로 배열 진입 -> 내부에 또 다른 for문으로 각 배열 간 비교
처음으로 한바퀴를 다 돌면 다시 상위 for로 진행
전부 완료시 break로 탈출(이미 정렬이 된 상태에서도 계속 순회할 수 있기 때문)

Code

---

const bubbleSort = function (arr) {
	// TODO: 여기에 코드를 작성합니다.
  // arr 길이를 가진 변수 n 생성
  let n = arr.length;
  // 전체 순환 for문 생성(오름차순 정렬이 한 번 끝나면 다시 돌기)
  for(let i=0; i<n; i++){
    // [2,1] 일 경우 앞의 요소 값을 저장해줄 변수 swap 생성
  	let swap = 0;
    // 배열 요소를 비교하기 위한 for문 생성
    // j<n-1-i인 이유는 -1은 for문 내에서 arr[j+1]로 마지막 요소까지 부르기 때문이고 -i는 이미 진행이 완료된 부분은 다시 할 필요가 없기 때문
    // 예를 들어 [1,10,4,3] 을 진행하는 경우
    // 첫 순환 시 [1,4,3,10]이 된다.
    // 다음 i가 1이 되며 다시 for문을 돌 때 굳이 마지막에 있는 10까지갈 필요가 없기 때문에 n-1-i를 해주는 것이다.
    for(let j=0; j<n-1-i; j++){
      // arr[j]>arr[j+1]일 경우 swap을 통해 서로의 값을 바꾼다.
    	if(arr[j] > arr[j+1]){
          swap = arr[j]
          arr[j] = arr[j+1]
          arr[j+1] = swap
        }
    }
    // break가 없다면 loop가 이어져 실행초과가 된다.
    if(!swap) break
  }
  return arr;
}

키워드

• break