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

버블 정렬

• 비교 방법

  • 옆과 비교하고 좌측/우측이 크면 교환한다.

  • 인접한 두 수를 비교해서 큰수를 앞/뒤로 보낸다.

• 과정

  • 요소의 개수 - 1 번을 돌리는데,

  • 1바퀴를 돌면, 젤 큰게/작은게 가장 왼쪽/오른쪽으로 이동한다.

  • 이것을 요소의 개수 -1번 까지 돌리면 모두 정렬이 완료 된다.

• 코드

#pseudo
​
for i in range(0,len(n)-1):
    #(0,n-1-i)에서 -i하는 이유는 젤 바깥쪽 루프가 1바퀴 돌 때마다, 맨마지막 부분이 정렬이 되기 때문이다.
    for j in range(0,len(n)-1-i): 
        if(j > j+1): #혹은 j > j+1
            교환

#python
​
n=[4,5,2,3,1]
for i in range(0,len(n)-1):
    for j in range(0,len(n)-1-i):
        if n[j] > n[j+1]: #오름 차순
            temp = n[j+1]
            n[j+1]=n[j]
            n[j] = temp
print(n)
​
# result : [1,2,3,4,5]

• 성능

  • 전체 원소의 개수가 n일 때 총 n-1번 순회하면 정렬이 끝나고 순회 할 때 마다 비교횟수를 계산해보면, (n-1) + (n-2) + ... + 2 + 1 은 n(n-1) / 2로 나타 낼 수 있다.

  • Best Case는 모두 정렬된 상태일 경우에는

    • O(n)

    • 왜냐하면, 모두 정렬이 되었다고 가정하면, 자리교환 부분이 없기 때문에, n-1번 만큼의 순회만 하면 된다. 그래서 n 이하의 -1은 상수 값이고, n 보다 차수가 낫기 때문에 무시하고 결론적으로 O(n) 이된다.

  • Worst Case일 때는 역순일 때, 원소를 비교할 때마다 자리 교환이 발생함으로

    • O(n^2)

      • O(n^2)의 판단 기준은,

        • 처음에 for문이 2번쓰였다는 것에서 바로 알 수 있고,

        • 원소 개수가 3개라고 가정할 때, 몇번 loop를 도는지를 보면

          • 원소 3개일 때, 2번의 loop를 돈다. 이것을 일반화 시키면

          • n * n-1 번 => n^2 - n 번이고, 이것의 시간복잡도를 계산하면

          • n^2 이하의 -n은 차수가 더 낮기 때문에 무시되고, 결론적으로 n^2만 남는다.

          • 그래서 O(n^2) 이 된다.