O(n^2) 정렬 정리

Kyung yup Lee·2021년 3월 31일

알고리즘

목록 보기

23/33

정렬이란

정렬 알고리즘은 다양한 알고리즘의 기초들을 이용해야 하기 때문에, 이런 부분들을 갖추고 있는지 묻는 면접에서 질문으로 많이 나오게 된다.
이런 알고리즘의 기초에는

점근 표기법
분할 정복 알고리즘 (Divide & Conquer)
최악의 경우, 최선의 경우, 평균적인 경우

같은 개념들이 있으며, 정렬을 설명하기 위해서는 이런 개념들이 필요하다.

점근 표기법은 시간복잡와 공간복잡도를 표현하기 위해서 알고 있어야 하는 개념이고,

분할 정복 알고리즘은 시간복잡도를 줄인 정렬(O(NlogN)) 을 설명하기 위해서 반드시 알고 있어야 하는 개념이다.

정렬에는 여러가지 경우에 따라 시간복잡도가 달라지는 데, 이런 경우를 따지면서 시간복잡도를 계산해내는 방법을 익히기 좋다.

정렬 알고리즘의 조건

정렬 알고리즘의 출력은 비 내림차순이다. 즉, 이전 원소는 다음 원소보다 작지 않다.
- 오름차순이 아닌 이유는, 오름차순은 계속 수가 증가하는 개념이기 때문에, 값이 같은 것을 포함하지 않는다. 때문에 비 내림차순이라고 표현한다.
정렬 알고리즘의 출력은 입력을 재배열하여 만든 순열이다.
- 이 말은 입력 값이 있으면, 그 입력에 벗어나는 결과가 절대 나올 수 없다는 뜻이다.

정렬 알고리즘의 종류

In-place 알고리즘

정렬을 수행하는 데에 추가 메모리가 O(logN) 이하로 사용되는 알고리즘

추가적인 데이터를 사용하지 않고 주어진 배열 안에서 정렬을 해내는 알고리즘이다.
O(logN) 이라는 뜻은 정렬을 수행하는데 추가적인 변수가 필요할 수 있는데, 그것까지는 허용하겠다는 뜻이다.

Stable 알고리즘

동일 값의 정렬 전후에 순서가 유지되는 알고리즘

stable 알고리즘이 의미가 있는 경우는, 기준 값을 여러개를 두고 정렬을 하려고 할 때 의미가 있다.
[(3,3), (0,4), (3,2), (1,5)] 라는 배열을 정렬 하려고 할 때, 첫번째 원소를 기준으로 정렬을 하면 [(0,4), (1,5), (3,3), (3,2)] 라는 배열이 나올 수도 있고, [(0,4), (1,5), (3,2), (3,3)] 배열이 나올 수도 있다.
일반적으로 정렬했을 때 결과는 항상 같은 게 좋다. stable 하지 못한 알고리즘은 이런 부분들의 결과가 같을 것이라는 것을 장담하지 못하기 때문에, 고려사항이 많아진다.

O(n^2) 정렬

O(n^2) 시간복잡도를 갖는 정렬 방법에는 대표적으로 bubble sort, insertion sort, selection sort가 있다.

해당 정렬방법은, 모든 원소에 대해 모든 원소를 한번씩 비교해줌으로써 O(n^2) 의 시간복잡도를 가지게 되고, 보편적으로 생각해낼 수 있는 정렬 방법이다.

버블 정렬(bubble sort)

버블 정렬은 특정 원소의 바로 뒤의 값을 모든 원소에 대해서 비교하는 과정을 모든 원소에 대해서 실행한다.

때문에 현재 배열 안에서 추가적인 메모리를 사용하지 않고 공간복잡도 O(1)로 수행이 가능하고, 시간복잡도는

최악의 경우: O(n^2) : 완전히 뒤집힌 배열
최선의 경우: O(n) : 이미 정렬된 경우
평균적인 경우: O(n^2)

def bubble_sort(x):
    # 인접한 두 원소를 검사하여 정렬하고, 마지막 원소를 제외하고
    length = len(x) - 1
    for i in range(length):
        swapped = False
        for j in range(length - i):
            if x[j] > x[j+1]: # 인접 원소 비교
                swapped = True # 스왑을 실행했는지 확인
                x[j], x[j+1] = x[j+1], x[j] # 스왑
        if not swapped: # 스왑이 없었다면, 정렬이 끝난 것
            break
    return x

삽입 정렬(insertion sort)

앞 부분의 이미 정렬된 영역과, 아직 정렬되지 않은 영역으로 나눈다.
정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치에 하나씩 삽입한다.

앞 배열은 이미 정렬된 부분. 하지만 중간중간에 값이 들어갈 수 있다. 즉 정렬되지 않은 값들을 찾아내 정렬된 부분에 하나씩 쑤셔넣는 것. 그래서 삽입 정렬이다.

시간복잡도는 버블 정렬과 같다.

def insertion_sort(x):
    for i in range(1, len(x)): # 모든 원소에 대해서
        j = i - 1  # i 는 정렬되지않은 배열의 첫 원소, j 는 정렬된 배열의 마지막 원소
        key = x[i] # 정렬되지 않은 배열의 원소를 저장해서 정렬된 배열에 넣기 위한 key값
        while x[j] > key and j >= 0: # x[j]  가 key 보다 작은 순간일 때 까지. 
        # 즉 정렬되지 않은 대상 원소가 처음으로 정렬된 원소의 특정 원소보다 작아지는 순간, 정렬이 될 예정
            x[j + 1] = x[j] # 값을 삽입하기 위한 배열 인덱스 이동
            j -= 1 
        x[j + 1] = key # 삽입
    return x

선택 정렬(selection sort)

주어진 리스트 중 최소 값을 찾아, 맨 앞의 값과 교체한다.
맨 처음 위치를 제외하고 위 동작을 반복한다.

최소 값을 찾는데 O(n) 이 소모되고, 모든 원소를 반복하는데 O(n) 이 소모되서 총 O(n^2) 이 소모된다.

시간 복잡도

최악의 경우: O(n^2)
최선의 경우: O(n^2)
평균적인 경우: O(n^2)

def selection_sort(x):
    length = len(x)
    for i in range(length-1): # 
        index_min = i
        for j in range(i+1, length):
            if x[index_min] > x[j]:
                index_min = j

        x[i], x[index_min] = x[index_min], x[i]
    return x