버블 정렬(Bubble Sort) 에 대한 간단 정리 !

 

안녕하세요.

 

이는 면접 대비 맞춤 포스팅입니다.

 

그럼, 바로 진행하겠습니다.

 

 

 

 

 

버블 정렬이란 ?

---

  -  서로 인접한 두 원소를 검사하여 정렬하는 알고리즘.

 

  -  인접한 두 원소를 검사하여 크기 순서를 맞춘다. (SWAP)

 

  -  장점

    ->  구현이 매우 간단함.

 

  -  단점

    ->  일반적으로 SWAP(원소 자리 바꿈)이 MOVE(이동) 보다 복잡하기 때문에 거의 쓰이지 않음.

    ->  시간복잡도가 정렬 알고리즘 중 가장 높다. (비효율적)

 

  *** 시간복잡도 == Best : n^2, Avg : n^2, Worst : n^2

 

 

 

알고리즘 간단코드

---

직접 짠 코드. 화질이 구지다..

 

    -> 이런 방식으로 두 개의 for문이 필요하며 내부에는 SWAP을 진행함.

 

 

알고리즘 그림설명

---

초록 : 인접한 두 원소 선택 및 비교.  회색 : 정렬 완료.

 

코드를 바탕으로 진행되는 버블 정렬이다.

 

  1)  인접한 두 원소 선택해서 크기 비교

    -> 큰 수를 오른쪽에 배치

 

  2)  맨 오른쪽에 도달한 순간 자리 고정(=정렬 완료) (기존에 자리 고정한 원소 있으면 그 이전 인덱스)

 

  3)  1), 2) 를 모든 원소가 정렬 완료될 때 까지 반복

 

 

 

 

감사합니다.

 

 

 

 

 

 

그림 출처
https://www.thecshandbook.com/Bubble_Sort