[알고리즘] 버블 정렬

[알고리즘] 버블 정렬

2020. 5. 2. 15:39ㆍStudy/about Algorithm

정렬 알고리즘(Sorting Algorithm)이란, 대소 관계를 비교할 수 있는 항목에 따라 일정한 순서대로 순서가 있는 데이터의 원소들의 위치를 변경하는 작업입니다[1]. 이 중 버블 정렬(Bubble sort)에 대해 알아보도록 하겠습니다.

< 목 차 >

1. 알고리즘

2. 구현

3. 최적화

4. 시간 복잡도

* 특별한 언급이 없는 이상 오름차순 정렬을 기준으로 설명합니다 :)

* 본 글에서는 Python을 중심으로 설명합니다.

1. 알고리즘

버블 정렬(Bubble sort)은 인접한 두 원소를 검사하여 정렬하는 방법입니다[2]. 이때, 정렬하고자하는 데이터는 '순서가 있는 데이터'이어야 합니다. 만약 순서가 없다면 대소 관계를 비교할 수 없어 정렬 알고리즘을 적용할 수 없습니다.

[영상 1] 버블 정렬 시각화 자료

위 동영상은 오름차순으로 버블 정렬하는 과정을 시각화 한 자료입니다. 빨간색 막대가 지나가면서 뒷부분부터 점점 정렬되는 모습을 확인하실 수 있습니다. 하지만 이 영상만으로는 어떤 프로세스로 진행되는지 파악하기 어려우실 것 입니다(만약 단번에 이해가 되셨다면 다음 목차로 넘어가셔도 좋습니다). 따라서 다음과 같이 5개의 원소를 가진 Python 리스트를 가정하여 오름차순으로 버블 정렬 하는 과정을 차근차근 살펴봅시다.

1 ) 첫 번째 원소부터 검사하는 경우

버블 정렬은 이웃한 두 원소간의 대소 관계를 비교하여 교환하는 과정을 반복합니다. 첫 번째 원소부터 검사를 진행할 때, 자신의 값과 다음에 올 값을 비교하여 자신이 더 크면 자리바꿈을, 자신이 더 작다면 그 자리를 유지하게 됩니다^[각주:1]. 즉, 정리를 하면 다음과 같습니다.

현재 위치의 데이터 값 > 다음 위치의 데이터 값 ⇒ 자리바꿈

현재 위치의 데이터 값 < 다음 위치의 데이터 값 ⇒ 유지

이 대소 관계를 바탕으로 첫 번째 원소부터 검사를 시작해봅시다. 이때, 현재 위치를 노란색으로, 비교 대상(다음 위치)을 초록색으로, 정렬이 완료된 원소는 빨간색으로 표시하였습니다.

[그림 1] 예제 1, 첫 번째 패스 (검사 시작위치가 첫 번째 원소인 경우)

앞에서부터 리스트를 쭉 한번 훑은 결과 리스트의 다섯 번째 원소 값이 5임을 알게되었습니다. 그 과정을 살펴보면, 연산^[각주:2]은 총 4회 소요되었으며, 리스트를 모두 검사한 뒤 단 하나의 값(다섯 번째 원소의 값)을 결정할 수 있게 되었습니다.

이와 같이 한 번 리스트를 훑는 과정을 '패스(pass)'라 일컬으며, 한 번의 패스로 하나의 값을 정렬할 수 있게 됩니다. 따라서 같은 방법으로 정렬이 모두 완료될 때까지 버블 정렬을 진행해보겠습니다. (이때, 이미 정렬이 완료된 원소에 대해서는 검사할 필요가 없으므로 이를 제외하고 진행합니다.)

[그림 2] 예제 1, 두 번째 패스 (검사 시작위치가 첫 번째 원소인 경우)

[그림 3] 예제 1, 세 번째 패스 (검사 시작위치가 첫 번째 원소인 경우)

[그림 4] 예제 1, 네 번째 패스 (검사 시작위치가 첫 번째 원소인 경우)

[그림 4]에서, 두 번째 원소의 값이 정해지면 첫 번째 원소의 값은 자동적으로 결정되므로 총 네 번의 패스를 통해 정렬을 완료할 수 있게 됩니다.

즉 정리해보면, 5개의 원소를 가진 리스트를 정렬하는데 총 4번의 패스가 필요했으며, 각 패스별 연산 횟수는 다음과 같습니다.

패스	연산 횟수	정렬 완료
첫 번째 패스	4번	5번째 원소
두 번째 패스	3번	4, 5번째 원소
세 번째 패스	2번	3, 4, 5번째 원소
네 번째 패스	1번	1, 2, 3, 4, 5번째 원소

이를 바탕으로 n개의 원소를 가진 리스트로 확장하여 생각해본다면, 다음과 같은 규칙을 발견하게 됩니다.

원소의 개수 : n개

패스 횟수 : n-1번

i번째 패스에서 연산 횟수 : n-i번

2 ) 마지막 원소부터 검사하는 경우

여기서 '꼭 첫 번째 원소부터 검사해야하는가?'라는 의문이 들 수도 있습니다.

이 질문에 대한 답은 '두 가지 방법 모두 가능합니다.'

뒤에서부터 조사하여도 결과는 같으나, 정렬이 완료되는 순서와 대소 비교 조건이 다르게 됩니다.

위의 예제 1^[각주:3]을 다시 가져와 살펴본다면,

마지막 원소부터 조사해나가기 때문에 현재 위치의 데이터 값이 다음^[각주:4] 위치의 데이터 값보다 큰 경우에 그 자리를 유지해야 오름차순으로 정렬할 수 있게 됩니다. 즉, 정리를 해보면 다음과 같습니다.

현재 위치의 데이터 값 > 다음 위치의 데이터 값 ⇒ 유지

현재 위치의 데이터 값 < 다음 위치의 데이터 값 ⇒ 자리바꿈

이 대소 관계를 바탕으로 마지막 원소부터 검사를 시작해봅시다. 이때, 현재 위치를 노란색으로, 비교 대상(다음 위치)을 초록색으로, 정렬이 완료된 원소는 빨간색으로 표시하였습니다.

[그림 5] 예제 1, 첫 번째 패스 (검사 시작위치가 마지막 원소인 경우)

[그림 6] 예제 1, 두 번째 패스 (검사 시작위치가 마지막 원소인 경우)

[그림 7] 예제 1, 세 번째 패스 (검사 시작위치가 마지막 원소인 경우)

[그림 8] 예제 1, 네 번째 패스 (검사 시작위치가 마지막 원소인 경우)

위 [그림 5~8]을 바탕으로 연산 횟수와 정렬 완료된 원소를 정리해보면 다음과 같습니다.

패스	연산 횟수	정렬 완료
첫 번째 패스	4번	1번째 원소
두 번째 패스	3번	1, 2번째 원소
세 번째 패스	2번	1, 2, 3번째 원소
네 번째 패스	1번	1, 2, 3, 4, 5번째 원소

즉, 검사 시작 위치에 따라 결과는 달라지지 않는다는 것을 알 수 있습니다. 하지만 검사 시작 위치, 오름차순/내림차순에 따라 검사 조건^[각주:5] 이 달라지므로 이에 유의하셔야 합니다.

2. 구현

앞서 우리는 다음과 같은 규칙을 발견할 수 있었습니다.

원소의 개수 : n개

패스 횟수 : n-1번

i번째 패스에서 연산 횟수 : n-i번

즉, n개의 원소를 가진 리스트는 n-1번 검사가 진행되어야 정렬이 완료되며, i번째 패스에서 연산 횟수는 n-i번으로 패스별로 연산횟수가 달라짐을 알 수 있습니다. 이렇듯 연관된 두 사건에 대해서는 어떤 방식으로 구현해야 할까요?

네, 바로 이중 for문을 활용하면 쉽게 구현할 수 있습니다. 겉 for문을 패스의 횟수(n-1회), 속 for문을 검사 과정(패스에서의 연산)이라 하면 쉽게 풀이 가능합니다. 단, 검사 시작 위치에 따라 속 for문의 조건 범위가 달라지기 때문에 두 가지 경우를 나누어 살펴보겠습니다.

1 ) 첫 번째 원소부터 검사하는 경우

먼저, 리스트의 첫 번째 원소부터 검사하는 경우에 대해 살펴봅시다. 본격적으로 코딩을 하기 전에 수도 코드^[각주:6]를 통해 간단히 구조를 파악해봅시다.

# pseudo code
procedure bubbleSort_head_ascendingOrder
    arr = list of sortable items
    for each i in 0 to (length(arr)-1) do :
        for each j in 0 to (length(arr)-i-1) do :
            if arr[j] > arr[j+1] :
                swap(arr[j], arr[j+1])
            end if
        end for
    end for
end procedure

겉 for문의 경우에는 패스의 횟수를 의미하기 때문에 n-1회 실행되어야 하므로 i의 범위는 쉽게 이해하실 수 있으실 것 입니다^[각주:7].

0 ≤ i < n-1

하지만 문제는 속 for문입니다. 속 for문의 경우에는 i 번째 패스에서의 연산 횟수를 의미하기 때문에 n-i회 실행되어야 할 것 같지만 뒤에 '-1'이 덧붙여져 있습니다. 이는 앞서 정렬 과정을 시각화한 자료^[각주:8]에서 각 패스별로 정렬 완료 직전의 상황(마지막 비교 및 교환 연산)들만 모아보면 j의 규칙 쉽게 찾을 수 있습니다([그림 9] 참조).

0 ≤ j < n-i-1

[그림 9] 각 패스별 정렬 완료 직전의 상황 (검사 시작위치가 첫 번째 원소인 경우)

따라서 이를 Python으로 구현하면 다음과 같습니다.

"""
Bubble sort, Starting position : arr[0], Ascending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def bubbleSort(arr) :
    n = len(arr)
    
    for i in range(0, n-1) :
        for j in range(0, n-i-1) :
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
                
    print("Sort complete : ", arr)

아직도 for문의 조건이 잘 이해되지 않는다면, 다음 영상의 코드와 같이 중간에 print문을 작성하여 한번 출력해보세요! 혹은 여기에서 각 step별로 i와 j 그리고 리스트의 변화를 실시간으로 확인할 수 있습니다.

[영상 2] 예제 1, 정렬 과정 시각화 영상 (검사 시작위치가 첫 번째 원소인 경우)

2 ) 마지막 원소부터 검사하는 경우

다음으로, 리스트의 마지막 원소부터 검사를 시작하는 경우에 대해 살펴봅시다. 이번에도 본격적으로 코딩을 하기 전에 수도 코드를 통해 간단히 구조를 파악해봅시다.

# pseudo code
procedure bubbleSort_tail_ascendingOrder
    arr = list of sortable items
    for each i in 0 to (length(arr)-1) do :
        for each j in (length(arr)-1) downto i do :
            if arr[j-1] > arr[j] :
                swap(arr[j], arr[j-1])
            end if
        end for
    end for
end procedure

겉 for문의 경우에는 <첫 번째 원소부터 검사하는 경우>와 마찬가지로 패스의 횟수를 의미하기 때문에 i의 범위는 다음과 같습니다.

0 ≤ i < n-1

이번에도 문제는 속 for문입니다. 언뜻 봐서는 어떻게 나온 범위인지 쉽게 감이 안잡히지만, 마찬가지로 앞서 정렬 과정을 시각화한 자료^[각주:9]에서 각 패스별 정렬 완료 직전의 상황들만 모아보면 쉽게 j의 규칙을 찾을 수 있습니다([그림 10] 참조).

i < j ≤ n-1

[그림 10] 각 패스별 정렬 완료 직전의 상황 (검사 시작위치가 마지막 원소인 경우)

따라서 이를 Python으로 구현하면 다음과 같습니다.

"""
Bubble sort, Starting position : arr[-1], Ascending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def bubbleSort(arr) :
    n = len(arr)
    
    for i in range(0, n-1) :
        for j in range(n-1, i, -1) :
            if arr[j-1] > arr[j] :
                arr[j-1], arr[j] = arr[j], arr[j-1]
                
    print("Sort complete : ", arr)

[영상 3] 예제 1, 정렬 과정 시각화 영상 (검사 시작위치가 마지막 원소인 경우)

3 ) 내림차순의 경우

내림차순의 경우에는 if문의 대소 비교 조건만 바꿔주면 됩니다. 오름차순과 같은 이치이므로 추가 설명은 하지 않겠습니다.

첫 번째 원소부터 검사하는 경우의 코드는 다음과 같습니다.

"""
Bubble sort, Starting position : arr[0], Descending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def bubbleSort(arr) :
    n = len(arr)
    
    for i in range(0, n-1) :
        for j in range(0, n-i-1) :
            if arr[j] < arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
                
    print("Sort complete : ", arr)

마지막 원소부터 검사하는 경우의 코드는 다음과 같습니다.

"""
Bubble sort, Starting position : arr[-1], Descending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def bubbleSort(arr) :
    n = len(arr)
    
    for i in range(0, n-1) :
        for j in range(n-1, i, -1) :
            if arr[j-1] < arr[j] :
                arr[j-1], arr[j] = arr[j], arr[j-1]
                
    print("Sort complete : ", arr)

* 구현 Tip
: 정렬 알고리즘에서 가장 많이 실수하는 부분이 '조건'입니다. 오름차순 및 내림차순에 따라 if문의 조건이 달라지고, 검사 시작 위치에 따라 속 for문의 조건이 달라지므로 이에 주의하여 코딩하면 실수를 줄일 수 있습니다 :)

3. 최적화

* 특별한 언급이 없는 이상 검사 시작위치가 첫 번째 원소인 경우, 그리고 오름 차순 정렬을 기준으로 설명합니다 :)

1 ) 최적화 1 | 중간 패스에서 이미 정렬이 완료 된 경우

이제 다른 예제를 살펴봅시다. 다음과 같이 앞 부분의 원소가 일부 정렬된 리스트를 버블 정렬을 이용하여 정렬해봅시다.

눈치 채신 분들도 계시겠지만, 첫 번째 패스에서 이미 정렬이 완료된 것을 확인할 수 있습니다. 하지만 앞서 제시한 구현방식대로 정렬을 진행하게 되면, 이미 정렬이 완료되었다 하더라도 for문의 조건이 끝나지 않아 무의미한 연산을 지속하게됩니다. 즉, 한 번의 패스로 해결할 수 있는 것을 for문의 조건으로 인해 무조건 n-1회 실행하게 됩니다([그림 12] 참조). 따라서 앞서 제시한 구현방식은 최적화된 방식이 아니므로 무의미한 연산을 제외하여 알고리즘을 더 개선해야 할 필요성이 있습니다.

그렇다면 어떻게 최적화 할 수 있을까요? 우선 기존의 구현 방식에서 가장 문제가 되었던 부분이 '정렬이 이미 완료되었지만, for문을 탈출하지 못하는 경우'입니다. 따라서 if문을 추가하여 만약 모두 정렬이 완료 되었다면 break를 통해 for문을 빠져나오도록 작성하면 됩니다. 여기서 모두 정렬이 완료되었음을 알아내기 위해서는 이전 패스에서 자리바꿈이 발생했는지 여부^[각주:10]를 따지면 되므로 boolean형을 이용하여 판별해주면 됩니다.

따라서 Python을 통해 구현해보면 다음과 같습니다.

"""
Bubble sort Optimization, Starting position : arr[0], Ascending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def bubbleSort(arr) :
    n = len(arr)
    
    for i in range(0, n-1) :
        swapped = False
        
        for j in range(0, n-i-1) :
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
                
        if not swapped : 
            break
                
    print("Sort complete : ", arr)

최적화 된 코드로 다시 예제 2번의 리스트를 정렬해보면 불필요한 연산은 진행되지 않음을 확인할 수 있습니다([그림 13] 참조).

2 ) 최적화 2 | 뒷 부분의 원소가 일부 정렬 된 경우

또 다른 예제를 살펴봅시다. 이번에도 일부 정렬된 리스트이지만, 예제 2^[각주:11]와는 달리 뒷 부분의 원소가 일부 정렬되어있습니다. 또한, 문제 상황을 더 잘 파악할 수 있도록 원소의 개수를 늘려보았습니다.

첫 번째 패스를 진행 한 결과, 마지막 원소의 값이 7임을 알게 되었습니다. 하지만, 자세히 보면 4, 5, 6 번째 원소도 이미 정렬됨을 확인할 수 있습니다. 따라서 최적화되지 않은 코드로 정렬을 진행했을 때, 2, 3, 4번째 패스에서는 아무런 자리바꿈도 일어나지 않을 것입니다. 또한, 예제 3의 경우에는 세 번째 패스에서 이미 정렬이 완료됨을 확인할 수 있습니다([그림 15] 참조). 따라서 불필요한 연산량을 줄여 패스 횟수를 줄일 필요성이 있습니다.

그렇다면 어떻게 최적화 할 수 있을까요? 우리는 [그림 14]에서 아이디어를 얻을 수 있습니다. [그림 14]를 보면, ④번째 검사부터 자리바꿈이 발생하지 않았는데, 이는 4번째 원소부터 마지막 원소까지 부분적으로 먼저 정렬이 완료되었음을 의미합니다. 즉, 최종적으로 자리바꿈이 발생한 곳을 파악하여 다음 패스에서 그 곳까지만 검사를 진행하게 된다면 불필요한 연산을 줄이고, 패스의 횟수 또한 획기적으로 줄일 수 있습니다.

따라서 Python을 통해 구현해보면 다음과 같습니다.

"""
Bubble sort Optimization, Starting position : arr[0], Ascending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

Reference : Dale Seo, Burbble sort, <https://www.daleseo.com/sort-bubble/>

@author: Hannah_Noh
"""

def bubbleSort(arr) :
    n = len(arr)
    end = n-1 # end : Last swap position(index)
    
    while end > 0 :
        last_swap = 0 # If swap doesn't happen(Already sorted)
        
        for i in range(0, end) :
            if arr[i] > arr[i+1] :
                arr[i], arr[i+1] = arr[i+1], arr[i]
                last_swap = i
                
        end = last_swap
                
    print("Sort complete : ", arr)

최적화 된 코드로 다시 예제 2번의 리스트를 정렬해보면 불필요한 연산은 진행되지 않음을 확인할 수 있습니다([그림 16] 참조).

3 ) 마지막 원소부터 검사하는 경우

마지막 원소부터 검사하는 경우도 같은 사고 과정으로 이루어지므로 추가 설명은 생략하겠습니다.

최적화 1 (중간 패스에서 이미 정렬이 완료 된 경우)의 코드는 다음과 같습니다.

"""
Bubble sort Optimization, Starting position : arr[-1], Ascending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def bubbleSort(arr) :
    n = len(arr)
    
    for i in range(0, n-1) :
        swapped = False
        
        for j in range(n-1, i, -1) :
            if arr[j-1] > arr[j] :
                arr[j-1], arr[j] = arr[j], arr[j-1]
                swapped = True
                
        if not swapped : 
            break
                
    print("Sort complete : ", arr)

최적화 2 (앞 부분의 원소^[각주:12]가 일부 정렬 된 경우)의 코드는 다음과 같습니다.

"""
Bubble sort Optimization, Starting position : arr[-1], Ascending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def bubbleSort(arr) :
    n = len(arr)
    end = 0  # end : Last swap position(index)
    
    while end < (n-1) :
        last_swap = n-1 # If swap doesn't happen(Already sorted)
        
        for i in range(n-1, end, -1) :
            if arr[i-1] > arr[i] :
                arr[i-1], arr[i] = arr[i], arr[i-1]
                last_swap = i
                
        end = last_swap
                
    print("Sort complete : ", arr)

4. 시간 복잡도

시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킵니다[5]. 따라서 병렬 알고리즘에서는 비교 및 교환 연산의 횟수를 계산하면 쉽게 시간 복잡도를 구할 수 있습니다. 이때, 비교 및 교환하는 과정을 하나의 연산과정으로 본다는 것을 잊으시면 안됩니다!

1 ) 최악의 경우

모든 패스를 빠짐없이 실행할 때 가장 연산 횟수가 많으므로 이때를 최악의 경우라 할 수 있습니다. 원소의 개수가 n인 리스트가 있다고 했을 때, 생성되는 패스의 개수와 각 패스별 연산 횟수는 다음과 같습니다.

패스	연산 횟수
1 번째 패스	n-1회 연산
2 번째 패스	n-2회 연산
...	...
n-1 번째 패스	1회 연산

따라서 위의 연산 횟수를 모두 더하면^[각주:13] 최악의 경우 시간 복잡도를 구할 수 있게 됩니다([그림 17] 참조). 시간 복잡도는 n이 무한이 클 때를 가정하여 점근적으로 표기하므로, 최악의 경우 버블 정렬의 시간 복잡도는 O(n²)이 됩니다.

2 ) 최선의 경우

최선의 경우는 패스가 단 한번만 실행되는 경우 일 것입니다. 데이터가 어떤 형태일때 패스가 단 한번 실행될까요?

맞습니다. 입력된 데이터가 이미 모두 정렬된 상태이면 패스가 단 한번 실행되고 종료 될 것입니다. 원소의 개수가 n인 리스트가 있다고 할 때, 첫 번째 패스에서의 연산횟수는 n-1회이며, n이 무한으로 크다 했을 때 상수값은 무의미해지므로 시간복잡도는 다음과 같아집니다([그림 18] 참조).

3 ) 정리

따라서 버블 정렬의 시간 복잡도를 정리해보면 다음과 같습니다.

최악	평균	최선
O(n²)	O(n²)	O(n)

[ 참고 문헌 ]

[1] "정렬(1) -버블, 선택, 삽입, 퀵, 병합-" 강의자료, 이대원 교수님

[2] 거품 정렬, 위키백과, <https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC> (참고일 : 2020.05.01)

[3] [알고리즘] 거품 정렬 - Bubble Sort(Python, Java), Engineering Blog, 2017.10.28, <https://www.daleseo.com/sort-bubble/>, (참고일 : 2020.05.01)

[4] Bubble Sort, Timo Bingmann, 2013.05.19, <https://youtu.be/Cq7SMsQBEUw>, (참고일 : 2020.05.01)

[5] 시간 복잡도, 위키백과, <https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84>, (참고일 : 2020.05.01)

[ 각주 ]

오름차순 정렬이므로 [본문으로]
이때, 비교와 교환 과정을 통틀어서 한 번의 연산으로 처리한다. [본문으로]
a = [5, 3, 1, 4, 2] [본문으로]
여기서 다음이란, 현재 위치 바로 앞에 위치한 데이터입니다. ←방향으로 읽어나간다고 생각하시면 됩니다. [본문으로]
이에 관해서는 뒤에 이어지는 2. 구현 부분을 참조하십시오 [본문으로]
수도코드는 프로그램을 작성하기 전에 알고리즘의 모델을 대략적으로 모델링하는데 쓰이는 코드로, 특정 언어의 문법이 아닙니다 :) [본문으로]
혹시 이해가 되지 않으신다면, python에서 for문의 조건 범위를 떠올려 보세요 :) [본문으로]
[그림 1~4] 참조 [본문으로]
[그림 5~8] 참조 [본문으로]
자리바꿈이 발생하지 않았다는 것은 오름차순 및 내림차순 조건에 어긋난 원소가 없다는 뜻 이므로 이미 정렬되어있음을 알 수 있습니다. [본문으로]
a=[1, 2, 3, 5, 4] [본문으로]
이 경우에는, 검사 시작 위치가 마지막 원소이며, 앞쪽의 원소부터 정렬이 완료되므로 "앞 부분의 원소가 일부 정렬 된 경우"에 적용됩니다. [본문으로]
시그마 연산을 활용하면 쉽게 더할 수 있습니다 [본문으로]

저작자표시

'Study > about Algorithm' 카테고리의 다른 글

[알고리즘] 퀵 정렬 (0)	2020.05.02

[알고리즘] 퀵 정렬 2020.05.02

냐쨩의 포트폴리오

냐쨩의 포트폴리오

태그

최근글

댓글

공지사항

아카이브

1. 알고리즘

1 ) 첫 번째 원소부터 검사하는 경우

2 ) 마지막 원소부터 검사하는 경우

2. 구현

1 ) 첫 번째 원소부터 검사하는 경우

2 ) 마지막 원소부터 검사하는 경우

3 ) 내림차순의 경우

3. 최적화

1 ) 최적화 1 | 중간 패스에서 이미 정렬이 완료 된 경우

2 ) 최적화 2 | 뒷 부분의 원소가 일부 정렬 된 경우

3 ) 마지막 원소부터 검사하는 경우

4. 시간 복잡도

1 ) 최악의 경우

2 ) 최선의 경우

3 ) 정리

[ 참고 문헌 ]

[ 각주 ]

'Study > about Algorithm' 카테고리의 다른 글

관련글

티스토리툴바