Sort

10 Aug 2021 • Algorithm Explained

선택 정렬

  • 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
    min_index = i
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

print(array)
  • 시간복잡도는 약 O(N2)

삽입 정렬

  • 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입
  • 자기 왼쪽에 있는 원소들을 다 확인해서 자기보다 크면 그 원소의 왼쪽에 삽입. 자기보다 작으면 그 자리에 유지.
array = [7,5,9,0,3,1,6,2,4,8]

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

print(array)
  • 시간복잡도는 O(N2). 하지만 리스트가 어느정도 정렬되어 있는 상황에선 중첩된 for문을 전부 진행할 필요가 없기 때문에 빠르게 동작.
  • 정렬이 거의 되어 있는 상황에서는 아래 나와 있는 퀵 정렬보다 빠르게 작동

퀵 정렬

  • 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈.
array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start+1
    right = end
    
    while left <= right:
        while left <= end and array[left] <= array[pivot]:
            left += 1
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]

    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

# 재귀함수 사용

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    tail = array[1:]
    
    left = [x for x in tail if x <= pivot]
    right = [x for x in tail if x > pivot]
    
    return quick_sort(left) + [pivot] + quick_sort(right)

print(quick_sort(array))
  • 시간복잡도는 O(NlogN)
  • 최악의 경우 시간복잡도는 O(N2)
  • 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 작동

계수 정렬

  • 데이터의 개수가 N이고, 최댓값이 K일 때, K+1 크기의 리스트를 선언하고, 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴.
  • 최악의 경우에도 O(N+K)의 시간복잡도를 보장함.
  • 따라서 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 가능.
  • 데이터의 범위만 한정되어 있다면 효과적으로 사용 가능.
  • 중복되는 데이터가 많을 경우 적합.

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

temp = [0]*(max(array)+1)

for i in array:
    temp[i] += 1

for j in range(len(temp)):
    for k in range(temp[j]):
        print(j, end = ' ')

내장함수

  • sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어짐. 퀵 정렬 보다는 느리지만 최악의 경우에도 O(NlogN) 보장.
  • sort()의 경우 리스트를 바로 정렬. 이 밖에도 key 매개변수를 입력으로 받을 수 있는데, 이는 정렬 기준을 뜻함.

Overall Tip

  • 문제에서 별도의 요구가 없다면 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용.
 Algorithm  Sort

Comments

Related Posts