O(N^2) 정렬

haruponea·2021년 3월 28일
0

알고리즘

목록 보기
1/1

정렬은 데이터를 특정한 기준에 따라 나열하는 것입니다. 알고리즘 문제를 풀 때 입력받은 자료를 정렬하는 경우도 많고 면접에서 자주 나오는 문제일 뿐만 아니라 이진탐색을 위해서 반드시 정렬을 해줘야 하기 때문에 잘 알고 있어야 합니다. 여러가지 정렬 알고리즘 중 O(N^2)의 시간복잡도를 가지는 정렬 알고리즘들을 알아봅시다.

목차

  1. 거품 정렬(Bubble sort)
  2. 선택 정렬(Selection sort)
  3. 삽입 정렬(Insertion sort)

1. 거품 정렬(Bubble sort)

거품 정렬은 앞에서부터 인접한 두 원소들을 비교하여 큰 값을 오른쪽으로 이동시켜 오른쪽에 최대값을 배치시키는 정렬방법입니다. 아래 이미지에서 정렬되지 않은 부분은 푸른 색, 비교중인 원소는 초록색, 정렬된 부분은 붉은 색으로 표시했습니다.

특징
추가적인 메모리를 필요로 하지않는 제자리 정렬입니다. 또한 원소 하나를 정렬 시키는데 리스트의 길이에 비례하는 비교가 필요하고 전체 원소의 개수만큼 반복하기 때문에 시간복잡도는 O(N^2)입니다.

Python

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
>
>
def bubble_sort(array):
    for i in range(len(array) - 1):
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
>
>
bubble_sort(array)
print(array)  #ouput: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

2. 선택 정렬(Selection sort)

선택 정렬은 아직 정렬되지 않은 리스트에서 최소값을 찾고 그 값을 맨 앞에 위치한 값과 바꾸는 과정을 반복합니다. 아래 이미지에서 정렬되지 않은 부분은 푸른 색, 최소값은 연두색, 정렬된 리스트는 붉은 색으로 표시했습니다.

  1. 푸른 색 리스트에서 최소값을 찾습니다.
  2. 최소값을 푸른 색 리스트의 맨 앞의 값과 바꿉니다. 이 과정에서 맨 앞의 값은 정렬되었다고 봅니다.
  3. 맨 앞의 값을 제외하고 남은 리스트에서 마지막 데이터가 남을 때 까지 반복합니다.
  4. 마지막 데이터는 가만히 두어도 이미 정렬된 상태이므로 정렬를 종료합니다.


특징
선택 정렬은 추가적인 메모리 공간을 거의 사용하지 않는 제자리 정렬입니다. 시간복잡도는 N - 1번 만큼 최소값을 찾아서 교체해줘야 하고 매 교체마다 리스트의 길이에 비례하는 비교연산이 필요합니다. 위 그림처럼 구현했을 때 연산횟수는 N + (N-1) + (N-2) + ・・・+ 2로 볼 수 있고 O(N^2)의 시간복잡도를 가집니다.

Python

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
>
>
def selection_sort(array):
    for i in range(len(array)):
        min_idx = i
        for j in range(i + 1, len(array)):
            if array[min_idx] > array[j]:
                min_idx = j
        array[i], array[min_idx] = array[min_idx], array[i]
>
>
selection_sort(array)
print(array) #ouput: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

3. 삽입 정렬(Insertion sort)

삽입정렬은 특정한 데이터를 적절한 위치에 삽입하는 알고리즘입니다. 단, 특정한 데이터의 앞부분은 이미 정렬되어 있다고 가정합니다. 특정한 데이터의 앞부분에서 특정한 데이터보다 작은 값을 만날 때까지 이동시키면 됩니다. 설명만 들으면 무슨 말인지 이해가 쉽게 안될텐데 그림으로 보면 쉽게 이해할 수 있습니다.
정렬된 부분은 붉은 색, 정렬되지 않은 부분은 파란 색, 특정한 데이터는 초록색으로 표시했습니다. 특정한 데이터를 정렬된 부분의 적절한 위치에 삽입해야 하는데 특정한 데이터보다 작은 데이터가 나올 때까지 왼쪽으로 이동시키면 됩니다. 이것이 가능한 이유는 특정한 데이터의 앞쪽이 항상 정렬된 상태이기 때문입니다.

특징
삽입 정렬 역시 제자리 정렬로 추가적인 메모리 사용이 없습니다. 삽입정렬의 시간복잡도도 O(N^2)인데 삽입 정렬은 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다. 최선의 경우 O(N)의 시간복잡도를 가집니다.

Python

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
>
>
def insertion_sort(array):
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j] < array[j - 1]:
                array[j], array[j - 1] = array[j - 1], array[j]
            else:
                break
>
>
insertion_sort(array)
print(array)  #ouput: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

0개의 댓글