Bubble 정렬 알고리즘 Python 목록 예제 사용

무엇이 Bubbl전자 정렬?

Bubble 정렬 인접한 두 값을 비교하여 목록 항목을 오름차순으로 정렬하는 데 사용되는 정렬 알고리즘입니다. 첫 번째 값이 두 번째 값보다 높으면 첫 번째 값이 두 번째 값 위치를 차지하고 두 번째 값이 첫 번째 값 위치를 차지합니다. 첫 번째 값이 두 번째 값보다 낮으면 교환이 수행되지 않습니다.

이 프로세스는 목록의 모든 값이 비교되고 필요한 경우 교체될 때까지 반복됩니다. 각 반복을 일반적으로 패스라고 합니다. 버블 정렬의 패스 수는 목록의 요소 수에서 XNUMX을 뺀 것과 같습니다.

이번에 Bubble 정렬 중 Python 지도 시간 당신은 배울 것이다:

구현 Bubble 정렬 알고리즘

우리는 구현을 세(3) 단계, 즉 문제, 해결책, 모든 언어에 대한 코드를 작성하는 데 사용할 수 있는 알고리즘으로 분류할 것입니다.

문제

항목 목록은 무작위 순서로 제공되며 항목을 순서대로 배열하고 싶습니다.

다음 목록을 고려해 보세요.

[21,6,9,33,3]

해법

두 개의 인접한 요소를 비교하고 첫 번째 값이 두 번째 값보다 높으면 교체하는 목록을 반복합니다.

결과는 다음과 같아야 합니다.

[3,6,9,21,33]

암호알고리즘

버블 정렬 알고리즘은 다음과 같이 작동합니다.

단계 1) 총 요소 수를 가져옵니다. 주어진 목록의 총 항목 수를 가져옵니다.

단계 2) 수행할 외부 패스 수(n – 1)를 결정합니다. 길이는 목록에서 XNUMX을 뺀 값입니다

단계 3) 외부 패스 1에 대해 내부 패스(n – 1)회 수행합니다. 첫 번째 요소 값을 가져와서 두 번째 값과 비교합니다. 두 번째 값이 첫 번째 값보다 작으면 위치를 바꿉니다.

단계 4) 외부 패스(n – 3)에 도달할 때까지 1단계 패스를 반복합니다. 목록에서 다음 요소를 가져온 다음 모든 값이 올바른 오름차순으로 배치될 때까지 3단계에서 수행한 프로세스를 반복합니다.

단계 5) 모든 패스가 완료되면 결과를 반환합니다. 정렬된 목록의 결과를 반환합니다.

단계 6) 알고리즘 최적화

목록이나 인접 값이 이미 정렬된 경우 불필요한 내부 전달을 피하세요. 예를 들어, 제공된 목록에 오름차순으로 정렬된 요소가 이미 포함되어 있는 경우 루프를 조기에 중단할 수 있습니다.

최적화 Bubble 정렬 알고리즘

기본적으로 버블 정렬 알고리즘은 Python 목록이 이미 정렬되었는지 여부와 관계없이 목록의 모든 항목을 비교합니다. 주어진 목록이 이미 정렬된 경우 모든 값을 비교하는 것은 시간과 리소스의 낭비입니다.

버블 정렬을 최적화하면 불필요한 반복을 방지하고 시간과 리소스를 절약하는 데 도움이 됩니다.

예를 들어 첫 번째 항목과 두 번째 항목이 이미 정렬되어 있으면 나머지 값을 반복할 필요가 없습니다. 아래 그림과 같이 반복이 종료되고 프로세스가 완료될 때까지 다음 반복이 시작됩니다. Bubble 정렬 예.

최적화는 다음 단계를 사용하여 수행됩니다.

단계 1) 내부 루프에서 스와핑이 발생했는지 모니터링하는 플래그 변수를 만듭니다.

단계 2) 값의 위치가 바뀌면 다음 반복을 계속합니다.

단계 3) 혜택의 위치가 바뀌지 않은 경우 내부 루프를 종료하고 외부 루프를 계속 진행합니다.

최적화된 버블 정렬은 필요한 단계만 실행하고 필요하지 않은 단계는 건너뛰기 때문에 더 효율적입니다.

시각적 표현

5개의 요소 목록이 주어졌을 때 다음 이미지는 버블 정렬이 값을 정렬할 때 어떻게 반복되는지 보여줍니다.

다음 이미지는 정렬되지 않은 목록을 보여줍니다.

첫 번째 반복

단계 1)

값 21과 6을 비교하여 어느 것이 다른 것보다 큰지 확인합니다.

21은 6보다 크므로 21은 6이 차지한 위치를 차지하고 6은 21이 차지했던 위치를 차지합니다.

수정된 목록은 이제 위와 같습니다.

단계 2)

값 21과 9가 비교됩니다.

21은 9보다 크므로 21과 9의 위치를 바꿉니다.

이제 새 목록은 위와 같습니다.

단계 3)

21과 33의 값을 비교하여 더 큰 값을 찾습니다.

값 33은 21보다 크므로 교환이 발생하지 않습니다.

단계 4)

33과 3의 값을 비교하여 더 큰 값을 찾습니다.

값 33은 3보다 크므로 위치를 바꿉니다.

첫 번째 반복이 끝나면 정렬된 목록은 위와 같습니다.

두 번째 반복

두 번째 반복 이후의 새 목록은 다음과 같습니다.

세 번째 반복

세 번째 반복 이후의 새 목록은 다음과 같습니다.

네 번째 반복

네 번째 반복 이후의 새 목록은 다음과 같습니다.

Python 예

다음 코드는 구현 방법을 보여줍니다 Bubble 정렬 알고리즘 Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

위의 버블 정렬 프로그램을 실행하면 Python 다음 결과를 생성합니다

[6, 9, 21, 3, 33]

코드 설명

에 대한 설명은 Python Bubble 정렬 프로그램 코드는 다음과 같습니다

이리,

매개변수 theSeq를 허용하는 bubbleSort 함수를 정의합니다. 코드는 아무것도 출력하지 않습니다.
배열의 길이를 가져오고 값을 변수 n에 할당합니다. 코드는 아무것도 출력하지 않습니다
버블 정렬 알고리즘을 (n – 1)번 실행하는 for 루프를 시작합니다. 이것이 외부 루프입니다. 코드는 아무것도 출력하지 않습니다
스왑이 발생했는지 여부를 결정하는 데 사용되는 플래그 변수를 정의합니다. 이는 최적화 목적입니다. 코드는 아무것도 출력하지 않습니다
목록의 모든 값을 첫 번째부터 마지막까지 비교하는 내부 루프를 시작합니다. 코드는 아무것도 출력하지 않습니다.
if 문을 사용하여 왼쪽 값이 바로 오른쪽 값보다 큰지 확인합니다. 코드는 아무것도 출력하지 않습니다.
조건이 true로 평가되면 theSeq[j] 값을 시간 변수 tmp에 할당합니다. 코드는 아무것도 출력하지 않습니다
theSeq[j + 1]의 값은 theSeq[j]의 위치에 할당됩니다. 코드는 아무것도 출력하지 않습니다
변수 tmp의 값은 theSeq[j + 1] 위치에 할당됩니다. 코드는 아무것도 출력하지 않습니다
플래그 변수에는 스왑이 발생했음을 나타내기 위해 값 1이 할당됩니다. 코드는 아무것도 출력하지 않습니다
if 문을 사용하여 변수 플래그의 값이 0인지 확인합니다. 코드는 아무것도 출력하지 않습니다.
값이 0이면 내부 루프에서 벗어나는 break 문을 호출합니다.
정렬된 후 theSeq의 값을 반환합니다. 코드는 정렬된 목록을 출력합니다.
난수 목록을 포함하는 변수 el을 정의합니다. 코드는 아무것도 출력하지 않습니다.
bubbleSort 함수의 값을 변수 결과에 할당합니다.
변수 결과의 값을 인쇄합니다.

Bubbl전자 정렬의 장점

버블 정렬 알고리즘의 장점은 다음과 같습니다.

이해하기 쉽습니다
목록이 이미 또는 거의 정렬되었을 때 매우 잘 수행됩니다.
광범위한 메모리가 필요하지 않습니다.
알고리즘에 대한 코드를 작성하는 것은 쉽습니다.
다른 정렬 알고리즘에 비해 공간 요구 사항이 최소화됩니다.

Bubble 정렬 단점

버블 정렬 알고리즘의 단점은 다음과 같습니다.

큰 목록을 정렬할 때는 성능이 좋지 않습니다. 시간과 자원이 너무 많이 소요됩니다.
주로 학문적 목적으로 사용되며 실제 응용 프로그램에는 사용되지 않습니다.
목록을 정렬하는 데 필요한 단계 수는 n차입니다.²

복잡성 분석 Bubble 정렬

복잡성에는 세 가지 유형이 있습니다.

1) 복잡성 정렬

정렬 복잡도는 목록을 정렬하는 데 걸리는 실행 시간과 공간을 표현하는 데 사용됩니다. 버블 정렬은 목록을 정렬하기 위해 (n – 1)번의 반복을 수행하는데, 여기서 n은 목록의 총 요소 수입니다.

2) 시간 복잡도

버블 정렬의 시간 복잡도는 O(n²)

시간 복잡도는 다음과 같이 분류될 수 있습니다.

최악의 경우 – 제공된 목록이 내림차순으로 표시됩니다. 알고리즘은 [Big-O] O(n)으로 표현되는 최대 실행 횟수를 수행합니다.²)
최고의 사례 – 제공된 목록이 이미 정렬되어 있는 경우 발생합니다. 알고리즘은 [Big-Omega] Ω(n)으로 표현되는 최소 실행 횟수를 수행합니다.
평균 사례 – 이것은 목록이 무작위 순서로 정렬된 경우 발생합니다. 평균 복잡도는 [Big-theta] ⊝(n으로 표현됩니다.²)

3) 공간 복잡도

공간 복잡도는 목록을 정렬하는 데 필요한 추가 공간의 양을 측정합니다. 버블 정렬은 값 교환에 사용되는 시간 변수에 대해 하나(1)의 추가 공간만 필요합니다. 따라서 공간 복잡도는 O(1)입니다.

제품 개요

버블 정렬 알고리즘은 인접한 두 값을 비교하고 왼쪽 값이 오른쪽 값보다 작은 경우 이를 교환하는 방식으로 작동합니다.
버블 정렬 알고리즘을 구현하는 것은 비교적 간단합니다. Python. for 루프와 if 문만 사용해야 합니다.
버블 정렬 알고리즘이 해결하는 문제는 항목의 무작위 목록을 가져와 이를 순서 있는 목록으로 바꾸는 것입니다.
데이터 구조의 버블 정렬 알고리즘은 최소한의 반복을 수행하므로 목록이 이미 정렬되어 있을 때 가장 잘 수행됩니다.
버블 정렬 알고리즘은 목록이 역순일 때 제대로 수행되지 않습니다.
버블러 정렬의 시간 복잡도는 O(n²) 및 O(1)의 공간 복잡도
버블러 정렬 알고리즘은 실제 응용 프로그램이 아닌 학술 목적에 가장 적합합니다.
최적화된 버블 정렬은 이미 정렬된 값을 확인할 때 불필요한 반복을 건너뛰어 알고리즘을 더욱 효율적으로 만듭니다.