정렬 알고리즘1: 버블, 선택, 삽입

참고

• 「취업을 위한 코딩 테스트이다 with 파이썬」 나동빈 지음
• 모두를 위한 컴퓨터 과학 (CS50 2019) https://www.boostcourse.org/cs112/joinLectures/41488?isDesc=false

 

구성 요소

1. 개념
2. 파이썬 구현 코드
3. 시간 복잡도
4. 장단점

---

버블 정렬(Bubble Sort)

• 개념

버블 정렬 동작 과정

데이터 내 인접한 두 요소를 비교하여 자리를 교환하거나 그대로 유지하는 정렬 방법이다.

위 그림은 버블의 각 단계를 나타낸 것으로, 파란색이 인접한 두 요소이다. 오름차순 정렬 기준, 왼쪽에 있는 값이 오른쪽에 있는 값보다 크다면 둘이 자리를 바꾼다. 이미 정렬되어 있는 상태(왼쪽 요소 < 오른쪽 요소)라면 그대로 다음 인덱스로 넘어간다. 데이터의 마지막 요소까지 비교가 끝나면, 가장 마지막에 있는 요소는 해당 데이터 내에서 가장 큰 값이 자리한다. 즉, 마지막 요소는 정렬이 완료된 상태이다.

인접한 두 요소 비교 작업을 총 n - 1번 반복하면 데이터가 오름차순 정렬된다. (n: 데이터 개수)

 

• 구현 코드

def bubble(data):
    length = len(data)
    for i in range(length-1):
        for j in range(1, length-i):
            if data[j-1] > data[j]:
                data[j-1], data[j] = data[j], data[j-1]
                
    return data

 

• 시간 복잡도

시간 복잡도는 for문이 중첩되어 있다. 외부 반복문을 (n - 1)번 실행하는 동안 내부 반복문은 (n - 1)번 실행되므로 결국 O(n²) 시간 복잡도를 갖는다. 이는 데이터가 이미 정렬되어 있더라도, 똑같이 O(n²) 시간 복잡도를 갖는다.

 

• 최적화

이를 최적화하는 방법이 없을까? 정렬된 데이터에서는 왼쪽 요소와 오른쪽 요소의 위치가 바뀌는 작업이 발생하지 않는다. 즉, 만약 어떤 라운드에서 인접한 요소 간 위치 변경이 발생하지 않았다면 이는 데이터가 정렬이 완료되었다는 의미이다.

따라서 위 코드에 위치 변경 발생 여부를 확인하는 변수를 선언함으로써 아래와 같이 코드를 최적화할 수 있다.

def bubble(data):
    length = len(data)
    for i in range(length-1):
        is_swap = False
        for j in range(1, length-i):
            if data[j-1] > data[j]:
                data[j-1], data[j] = data[j], data[j-1]
                is_swap = True

        if not is_swap:
            break
            
    return data

이때는 바깥 반복문이 최초로 실행되어 안쪽 반복문을 (n - 1)번 실행한 후 정렬 과정이 종료되므로, O(n)의 시간 복잡도를 가진다.

 

• 장단점

1. 개념과 구현이 간단하다.
2. 제자리 정렬(In-place sort)로, 기존 데이터 외 추가적인 메모리를 거의 사용하지 않는다.
3. 안정 정렬로, 중복된 값을 가진 요소들의 순서는 정렬 전후로 유지된다.

 

1. 시간 측면에서 효율적이지 않다.

 

 

 

선택 정렬(Selectino Sort)

• 개념

선택 정렬 동작 과정

정렬되지 않은 데이터 중에서 첫 번째 원소와 가장 작은 원소를 선택하여 서로 자리를 바꾸어나가는 정렬 방식이다. 위 그림에서 파란색은 정렬되지 않은 첫 번째 원소이고, 초록색은 정렬되지 않은 데이터 내 가장 작은 원소이다. 주황색 칸은 이미 정렬이 완료된 데이터이다.

선택 정렬은 정렬할 데이터가 어떠한 상태이든 상관없이 모든 원소를 비교한다.

 

• 구현 코드

def selection(data):
    length = len(data)
    for i in range(length):
        _min = min(data[i:])
        j = data.index(_min)

        data[i], data[j] = data[j], data[i]

    return data

 

• 시간 복잡도

처음에 가장 작은 원소를 찾는 데 n개의 데이터를 순회한다. 그 다음에는 1개의 데이터가 정렬되었으므로 나머지 (n - 1)개의 데이터를 순회한다. 그 다음엔 2개의 데이터가 정렬되었으므로 나머지 (n - 2)개의 데이터를 순회한다 ... 이 작업을 나머지 1개의 데이터까지 반복한다. 따라서 시간 복잡도는 O(n²)가 된다.

 

• 장단점

1. 구현과 코드가 직관적이며 간단하다.
2. 버블과 비교하여 실제 원소 간 위치 교환이 적게 발생한다.
3. 버블 정렬과 동일한 시간 복잡도를 가지지만, 실제로는 버블 정렬보다 조금 더 빠르다.
4. 제자리 정렬(In-place sort)로, 기존 데이터 외 추가적인 메모리를 거의 사용하지 않는다.

 

1. 시간 측면에서 효율적이지 않다.
2. 불안정 정렬로, 중복된 값을 가진 요소들의 순서가 정렬 전후로 보장되지 않는다.

 

 

 

삽입 정렬(Insertion Sort)

• 개념

삽입 정렬 동작 과정

왼쪽부터 데이터를 하나씩 확인하여 적절한 위치에 삽입하는 방식이다. 처음엔 5를 보는데, 원소가 1개일 때는 그 자체로 정렬된 것이므로 다음 원소 1을 확인한다. 1의 왼쪽 원소인 5와 비교하면 1은 5보다 왼쪽에 놓여야 하므로, 1을 5 앞쪽에 삽입한다. 그 다음 6은 왼쪽 원소인 5보다 크므로 현재 위치 그대로 유지하면 된다. 이렇게 새로운 데이터 1개가 정렬된 데이터 내에 적절한 위치에 삽입하는 과정이 반복된다.

이때 필요할 때만 특정 위치로 삽입되므로 만약 데이터가 거의 정렬되어 있는 상태라면 매우 효율적으로 동작한다.

 

• 구현 코드

def insertion(data):
    length = len(data)
    for i in range(length):
        for j in range(i, 0, -1):
            if data[j-1] < data[j]:
                break
            else:
                data[j-1], data[j] = data[j], data[j-1]

    return data

 

• 시간 복잡도

for문이 중첩되어 있다. 평균적으로 바깥 for문이 (n - 1)번 실행되는 동안 안쪽 for문은 1, 2, ... (n - 1)번 수행되어 O(n²) 시간 복잡도를 갖는다.

그러나 만약 데이터가 모두 정렬되어 있다면 바깥 for문이 (n - 1)번 실행되는 동안 안쪽 for문은 1번씩만 수행된다. 따라서 최선의 경우에는 O(n) 시간 복잡도를 갖는다.

 

• 장단점

1. 데이터가 거의 정렬되어 있다면 시간 복잡도가 O(n)으로, 속도가 빠르다.
2. 제자리 정렬(In-place sort)로, 기존 데이터 외 추가적인 메모리를 거의 사용하지 않는다.
3. 안정 정렬로, 중복된 값을 가진 요소들의 순서는 정렬 전후로 유지된다.

 

1. 버블이나 선택 정렬보다 구현하기 어렵다.
2. 데이터의 상태에 따라 시간 복잡도가 O(n²)과 O(n)을 넘나들어 성능 편차가 심하다.