AlgorithmSort

bubble sort

algorithm, bubble sort, python, sort
  • bubble sort(거품 정렬)
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • O(n^2)
  • simple sort
  • 마지막 전 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬
  • 한번 순회가 끝나면 가장 큰 자료가 맨뒤로 이동
  • 2번째 순회에서는 맨 끝에 있는 자료를 정렬에서 제외되는 방식

  • 순회할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어남

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    import random

    def bubble_sort(li):
     
        n = len(li)
        
        for i in range(n-1):
            for j in range(n-i-1):
                if li[j] > li[j+1]:
                    li[j], li[j+1] = li[j+1], li[j]

                    
    if __name__ == '__main__':
       
        while True:
            num_data = int(input('데이터 개수(종료:0):'))
            if not num_data:
                break
                
            data = [random.randint(1,100) for _ in range(num_data)]
            print(data)

            bubble_sort(data)
            print(data)

  • python에서의 두 변수 값 바꾸기(swap)

    • 보통 임시로 저장할 변수를 이용하여 바꿈

      1
      2
      3
      4
      5
      6
      7
      a = 10
      b = 20
      temp = a
      a = b
      b = temp
      print(a, b)
      >> 20 10

    • python에서는 한 줄로 바꾸기 가능

      1
      2
      3
      4
      5
      a = 10
      b = 20
      a, b = b, a
      print(a, b)
      >> 20 10
Share