ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [python]버블 정렬
    Programming/python 2019. 10. 20. 00:17

    버블 정렬(Bubble sort)이란?


    버블 정렬이란, 두 인접한 원소를 검사하여 정렬하는 방법이다. 거품 정렬이라고도 불리며 원소의 이동하는 모습이 거품이 수면으로 올라오는 듯한 것처럼 보이기 때문에 지어진 이름이다.

    버블정렬의 특징


    장점

    • 구현이 간단하다.

    단점

    • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하려면 배열의 모든 다른 요소들과 교환해야하는 필요 이상의 교환이 생긴다

     

    시간 복잡도


    시간 복잡도가 O(n²)로 상당히 느린편이지만 코드가 단순하기 때문에 자주 사용된다.

     

    코드


    #버블 정렬
    #리스트 a를 버블 정렬로 정렬함
    def bubble_sort(a):
        n = len(a)
        for i in range(0,n-1):
            for j in range(n-1):
                if a[j] > a[j+1]:
                    a[j], a[j+1] = a[j+1], a[j]
        return a
    a = [7,3,20,5,12,1]
    print(bubble_sort(a))

    [7, 3, 20, 5, 12, 1] 7과 3을 비교한다
    [3, 7, 20, 5, 12, 1] 7이 더 크므로 둘을 교환한다
    [3, 7, 5, 20, 12, 1] 20과 5를 비교해서 20이 더 크므로 교환한다
    [3, 7, 5, 12, 20, 1] 20과 12를 비교해서 20이 더 크므로 교환한다
    [3, 7, 5, 12, 1, 20] 20과 1을 비교해서 20이 더 크므로 교환한다
    [3, 5, 7, 12, 1, 20] 7과 5를 비교해서 7이 더 크므로 교환한다
    [3, 5, 7, 1, 12, 20] 12와 1을 비교해서 12가 더 크므로 교환한다
    [3, 5, 1, 7, 12, 20] 7과 1을 비교해서 7이 더 크므로 교환한다
    [3, 1, 5, 7, 12, 20] 5와 1을 비교해서 5가 더 크므로 교환한다
    [1, 3, 5, 7, 12, 20] 3과 1을 비교해서 3이 더 크므로 교환한다

    'Programming > python' 카테고리의 다른 글

    (python)날짜로 파일 제목 만들기  (0) 2019.12.09
    큐와 스택은 무엇인가  (0) 2019.11.03
    [python]퀵 정렬  (0) 2019.10.18
    [python]합병 정렬  (0) 2019.10.18
    [python]삽입 정렬  (0) 2019.10.16

    댓글

Copyright 2023. 은유 All rights reserved.