4: 알고리즘-4(버블 정렬:Bubble Sort)

버블 정렬(bubble sort)

정렬 알고리즘 중 하나로 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법

버블 정렬은 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중하기 때문에 접근법은 간단하지만 단 하나의 요소를 정리하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있음

---

임의의 순서로 나열되어 있는 6개의 숫자를 오름차순으로 정렬

 

6 3 8 5 2 7	3 6 8 5 2 7	3 6 5 8 2 7	3 6 5 2 8 7	3 6 5 2 7 8(1회전)
3 5 6 2 7 8	3 5 2 6 7 8(2회전)	3 2 5 6 7 8(3회전)	2 3 5 6 7 8(4회전)

• 마치 거품이(비교 및 교환)이 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식 같아서 이러한 정렬 방식을 버블 정렬이라고 함
• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를... 이런 식으로 (마지막-1) 번째 자료와 마지막 자료를 비교해 교환하면서 자료를 정렬함
• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외됨. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어나게 됨

---

버블 정렬을 의사코드로 나타내기

 

Repeat n-1 times
//n명이 있고 서로를 비교한다면 최대 n-1번을 비교할 수 있음(6명이면 최대 5번 비교)
  For i from 0 to n-2
  //1회전이 끝나고 나면 2회전부터는 맨 마지막 자료를 제외
    if i'th and i + 1'th elements out of order
    //i가 0부터 시작할 때 i번째 사람과 i+1번째 사람의 순서가 잘못됐다면 
      swap them
      //자리를 바꿔라

 

• 바깥 반복문은 n-1번 반복하고 안쪽 반복문 또한 n-1번 반복 → (n-1) x (n-1) = n^2n+1
• n이 커질수록 n^2가 미치는 영향이 더 커지기 때문에 지수가 가장 큰 n^2의 영향력이 커져서 제일 중요!
• 버블 정렬 실행 시간의 상한을 Big O로 나타내면 O(n^2)이라고 할 수 있음(즉 선형 탐색이나 이진 탐색보다 더 시간이 많이 들게 됨! 
• 정렬이 되어 있는지 여부에 관계없이 루프를 돌며 비교를 해야 하므로 버블 정렬 실행 시간의 하한도 여전히 Ω(n^2)

---

실행시간을 나타내기 위해 사용되는 Big O 표기

 

O(n^2): 버블정렬

O(n log n)

O(n): 선형검색

O(log n): 이진검색

O(1)

---

실행시간을 나타내기 위해 사용되는 Big Ω 표기

 

Ω(n^2): 버블정렬

Ω(n log n)

Ω(n):배열안에 존재하는 값의 개수 세기

Ω(log n)

Ω(1): 선형검색, 이진검색

 

 

https://www.boostcourse.org/cs112/joinLectures/41307

4: 알고리즘-2(알고리즘 표기법)

https://www.boostcourse.org/cs112/joinLectures/41307

모두를 위한 컴퓨터 과학 (CS50 2019)

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog