TIL. 버블정렬 알고리즘 문제풀이

버블 정렬

버블 정렬(bubble sort) 알고리즘은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

• 기본 원리는 각 요소를 반복적으로 비교하고 필요에 따라 위치를 교환하는 것이다. 이렇게 함으로써, 가장 큰 값이 배열의 끝으로 '거품'처럼 떠오르게 된다. 이 과정을 배열의 모든 요소가 정렬될 때까지 반복한다.

버블 정렬의 특징

• 버블 정렬의 시간 복잡도는 최악의 경우에 𝑂(𝑛2)이며, 이는 배열의 크기가 커질수록 비효율적임을 의미한다.
• 하지만 구현이 간단하여 이해하기 쉽고, 작은 데이터 세트에 대해서는 괜찮은 성능을 보일 수 있다고 한다. 🧐
• 또한 이미 정렬된 배열에 대해서는 매우 빠르게 동작하며, 이 경우 최선의 시간 복잡도는 𝑂(𝑛)이다. 이런 특성 때문에 교육적인 목적으로 많이 사용된다.

버블 정렬의 단계

• 인접 요소 비교: 현재 요소가 다음 요소보다 크면 두 요소의 위치를 교환한다.
  이로 인해 가장 큰 요소가 배열의 끝으로 이동한다.
• 한 단계 완료: 배열의 각 요소를 순회하며 비교하고 교환하는 과정을 배열의 끝까지 진행한다.
  첫 번째 순회 후, 가장 큰 요소가 배열의 맨 끝에 위치하게 된다.
• 반복 수행: 이미 정렬된 최종 요소를 제외하고 남은 배열에 대해 이 과정을 반복한다.
• 정렬 완료: 모든 요소가 정렬될 때까지 위의 과정을 반복한다.

버블 정렬이 사용되는 경우

버블 정렬은 그 자체로는 성능이 좋지 않기 때문에 대규모 데이터 세트나 성능이 중요한 애플리케이션에서는 일반적으로 사용되지 않는다고 한다. 🥲

• 교육 목적: 버블 정렬은 알고리즘의 기본 개념을 이해하기 위한 좋은 예제로 사용된다. 이 알고리즘은 비교와 교환 메커니즘을 쉽게 보여주기 때문에 프로그래밍과 알고리즘의 기초를 배우는 데 도움이 된다.

• 간단한 스크립트 또는 프로토타입: 작은 데이터 세트를 빠르게 정렬해야 할 때 버블 정렬은 코드가 간단하고 이해하기 쉬우므로 유용할 수 있다. 프로토타이핑이나 테스트 목적으로 빠른 구현이 필요한 경우에 선택될 수 있다.

• 실시간 업데이트가 필요한 작은 데이터 세트: 데이터가 실시간으로 작은 단위로 변경되고 그 즉시 정렬이 필요한 경우, 이미 거의 정렬된 데이터 세트에 대한 버블 정렬의 성능이 괜찮을 수 있다. 버블 정렬은 최선의 경우 𝑂(𝑛)의 시간 복잡도를 가질 수 있으므로, 소량의 데이터에 대해 빠른 반복 정렬이 가능하다.

• 안정성이 요구되는 경우: 버블 정렬은 안정 정렬 방법이다. 즉, 동일한 값을 가진 요소들 사이의 상대적인 순서가 정렬 과정에서 유지된다. 이 특성은 같은 값에 대해 추가적인 정보를 유지해야 하는 데이터 정렬 시 중요할 수 있다.😀

문제 설명

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 버블정렬입니다.

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

▣ 출력설명
오름차순으로 정렬된 수열을 출력합니다.

▣ 입출력 예

input	output
13 5 11 7 23 15	5 7 11 13 15 23

풀이

👉 1차

function bubbleSort(arr) {
  let count = 0;

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

const arr = [13, 5, 11, 7, 23, 15];
console.log(bubbleSort(arr));

1. for문을 돌려서 첫번째 요소와 두번째 요소를 검사한다.
   2중 for문 대신 j를 i+1로 정의하고 while문을 써보기로 한다.
2. 첫번째 요소와 두번째 요소의 크기를 비교하여 오른쪽보다 왼쪽이 높다면 서로 바꾼다.
3. 1차 순환이 끝나면 마지막 요소는 가장 큰 요소가 위치하게 된다. 이제 다음 순환이 필요하게 되는데 이때, while문을 써서 배열의 길이만큼 다시 돌려주는 방법으로 여러차례 순환하기로 했다. 🧐

• arr.length; 에서 arr.length - 1; 로 수정. arr.length를 초과하여 배열의 범위를 넘어서지 않는 조건을 추가했다.

❓ 문제점
👉 매 while 루프마다 전체 배열을 불필요하게 반복하고, 이미 정렬된 요소에 대해서도 계속 비교를 수행한다.😱

👉 2차

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

• 이중 for 루프를 사용해서 풀어보자.
• 기본적으로 위와 비슷하지만 이중으로 도는 for문에서는 중복으로 무한루프가 돌지않도록 조건을 j<i+2 로 해두었다.

❓ 문제점
👉 이 코드는 버블정렬 알고리즘을 구현하지 못했다. 이 코드는 각 요소를 바로 다음 요소와 한번만 비교하고 교환하므로 배열이 전체적으로 정렬되지 않는다.

👉 3차

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) { // ⭐️
      if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
    }
  }
  return arr;
}

• i 루프: 이 루프는 전체 배열을 순회.
  i는 0부터 arr.length - 1 까지 반복하며, 각 반복에서 배열의 끝 부분에서 시작하여 정렬된 요소를 제외하고 나머지 부분을 순회.
• j 루프: i에 대한 각 반복마다 j 루프가 실행.
  이 루프는 배열의 시작부터 arr.length - i - 1 까지 실행되며, 이는 정렬이 이미 완료된 요소는 다시 비교하지 않도록 한다. ⭐️
• arr[j] 와 arr[j+1] 을 비교해서 arr[j] 가 arr[j+1] 보다 크면, 두 요소의 위치를 교환한다. 이를 통해, 더 큰 요소가 오른쪽으로 이동하게 된다. 이 과정은 각 j 루프마다 반복되며, 각 순회의 끝에서 가장 큰 요소가 배열의 끝으로 "버블링" 된다. 😮

✍️ solution

function solution(arr) {
  let answer = arr;
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return answer;
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));