[자료 구조와 알고리즘] 정렬 - 버블 정렬

2023. 5. 29. 20:22·📗 self-study/📗 inflearn

 

 

 

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘

 

정렬 - 버블 정렬

 

 

 

 

📍 버블 정렬(Bubble Sort)

👉🏻 가장 쉽게 생각할 수 있는 정렬 중 하나로 구현이 쉬우나 성능이 좋지는 않음

 

[4, 2, 3, 1]

// 앞에 있는 숫자와 그 뒤의 숫자를 비교해서 조건에 따라 자리를 바꿈
 _  _
[2, 4, 3, 1]
    _  _
[2, 3, 4, 1]
       _  _
[2, 3, 1, 4]

// 4(마지막 원소) 자리가 고정되었음(정렬 완료)

 _  _
[2, 3, 1] // 배열 유지
    _  _
[2, 1, 3]

// 3(마지막 원소) 자리가 고정되었음
 _  _
[1, 2]

// 남은 원소는 1 하나이므로 정렬 끝

 

 

 

📍 버블 정렬의 구현

[ bubble_sort.mjs ]

function BubbleSort(arr) {
    // 배열이 n개라면 n-1만큼 정렬해야 함
    for(let i = 0; i < arr.length - 1; i++) {
        // 하나의 원소는 원소의 개수에서 -1만큼 정렬해야 함
        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;
            }
        }
    }
}

let arr = [4, 2, 3, 1];

console.log("===== 정렬 전 =====");
console.log(arr);

BubbleSort(arr);

console.log("===== 정렬 후 =====");
console.log(arr);

 

 

 

📍 버블 정렬의 성능(빅 오 ver.)

👉🏻 길이 n 배열에서 반복문을 한 번 거칠 때마다 마지막 원소가 정렬됨

👉🏻 등차수열의 합의 모습이 됨 (n - 1) + (n - 2) + (n -3) + ... + 2 + 1

 

👉🏻 O(n^2) 

 

 

📍 버블 정렬의 장단점

👉🏻 장점: 이해와 구현 간단함

 

👉🏻 단점: 성능이 좋지 않음

 

저작자표시 비영리 변경금지 (새창열림)
'📗 self-study/📗 inflearn' 카테고리의 다른 글
  • [자료 구조와 알고리즘] 정렬 - 삽입 정렬
  • [자료 구조와 알고리즘] 정렬 - 선택 정렬
  • [자료 구조와 알고리즘] 재귀 - 하노이 탑
  • [자료 구조와 알고리즘] 재귀적으로 생각하기
천재강쥐
천재강쥐
  • 천재강쥐
    디버거도 버거다
    천재강쥐
  • 전체
    오늘
    어제
    • Category (467)
      • 진짜 너무 궁금한데 이걸 나만 몰라...? (0)
      • 💾 Portfolio (2)
      • 🐤 CodingTest (28)
        • Java (20)
        • ᕕ(ꐦ°᷄д°᷅)ᕗ❌ (5)
      • 🚀 from error to study (142)
        • AI (1)
        • Cloud (2)
        • DB (12)
        • Front-End (16)
        • Github (14)
        • Java (39)
        • Mac (7)
        • Normal (29)
        • Server (22)
      • 📘 certificate (44)
        • 📘 리눅스마스터1급 (1)
        • 📘⭕️ 정보처리기사 (40)
        • 📘⭕️ SQLD (3)
      • 📗 self-study (234)
        • 📗 inflearn (35)
        • 📗 생활코딩 (8)
        • 📗 KH정보교육원 당산지원 (190)
      • 🎨 Scoop the others (0)
        • 📖 Peeking into other people.. (0)
        • 🇫🇷 (0)
        • 📘⭕️ 한국사능력검정시험 심화 (11)
        • 오블완 (4)
  • 인기 글

  • hELLO· Designed By정상우.v4.10.1
천재강쥐
[자료 구조와 알고리즘] 정렬 - 버블 정렬
상단으로

티스토리툴바