버블정렬(bubble sort)

Sungmin·2023년 5월 18일
0

CS지식

목록 보기
2/6

버블정렬?

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
(인접한 두 개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환)

구체적인 개념

  • 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를 ... 비교하여 교환하면서 자료를 정렬한다.

  • 1회전 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에선 맨끝에 있는 자료는 정렬에서 제외, 2회전 수행하면 끝에서 두 번째 자료까지 정렬에서 제외.

특징

  • 장점
    • 구현이 매우 간단.
  • 단점
    • 순서에 맞지 않은 요소를 인접한 요소와 교환
    • 모든 다른 요소들과 교환되어야 한다.
    • 특정 요소가 최종 정렬위치에 이미 있는 경우라도 교환되는 일이 일어난다.

시간복잡도

  • O(n^2)

profile
Let's Coding

0개의 댓글