6.이코테 - 정렬 알고리즘

김혁·2022년 1월 23일
2

이코테

목록 보기
4/9
post-thumbnail

이코테 정렬 알고리즘

1. 기준에 따라 데이터를 정렬

정렬 알고리즘 개요

정렬 (sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 대 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 가장 많이 사용되는 알고리즘 중 하나다.
정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색(Binary search)가 가능하다.

선택정렬

데이터가 무작위로 있을때 컴퓨터는 어떻게 정렬할까? 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까? 이것을 선택 정렬(Selection Sort) 이라고 한다.

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(N^2)

선택 정렬은 기본 정렬 라이브러리를 포함해 뒤에서 다룰 알고리즘과 비교했을 때 매우 비효율적이다. 다만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택정렬 소스코드 형태에 익숙해질 필요가 있다. 그러므로 선택 정렬 소스코드를 자주 작성해볼 것을 권한다.

삽입정렬

삽입정렬은 선택에 비해 구현 난이도가 높은 편이지만 선택정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다. 삽입정렬은 데이터가 정렬 되어 있을 때 훨씬 효율적이다.

array = [7,5,9,0,3,1,6,4,2,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(N^2)이다. 삽입정렬의 데이터는 리스트가 거의 정렬되어 있는 상태에서는 매우 빠르게 동작한다는 점이다. 최선의 경우 O(N)

퀵정렬

퀵정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?
퀵 정렬에서는 피벗 pivot이 사용된다. 방식은 책을 참고하도록 하자. 리스트의 원소가 1개라면, 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능하다. 그러므로 리스트를 그대로 반환하면 된다.

array = [7,5,9,0,3,1,6,4,2,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)

이것을 조금 pythonic하게 소스코드를 작성해보자

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

def quick_sort(array):

  if len(array) <= 1:
    return array

  pivot =array[0]
  tail  = array[1:]

  left_side = [x for x in tail if x <= pivot]
  right_side =[x for x in tail if x > pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)


print(quick_sort(array))

퀵 정렬의 시간 복잡도

선택과 삽입 정렬은 최악의 경우에도 O(N^2)을 보장한다. 퀵정렬의 시간 복잡도는 O(N*logN)이다. 이러한 시간복잡도를 가지는 이유는 책을 참고하자. 컴퓨터는 로그의 밑으로 2를 가지게 된다. 퀵정렬 같은 경우는 피벗을 기준으로 절반씩 나누어지면서 정렬 되기 때문에 정렬과정을 나열하고 높이를 계산해보면 logN이 나온다. 그러므로 시간복잡도가 위와같이 도출되는 이유이다.

계수정렬

계수정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 모든 데이터가 양의 정수인 상황을 가정해보자. 데이터의 개수가 N, 데이터 중 최댓값이 k일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(n+k)을 보장한다. 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬은 앞서 다루었던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식이 아니다.

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

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

for i in range(len(array)):
  count[array[i]] += 1

for i in range(len(count)):
  for j in range(count[i]):
    print(i,end=' ')

계수 정렬의 시간 복잡도

데이터의 개수를 N, 데이터 중 최댓값의 크기를 K 라고 할 때, 계수 정렬의 시간 복잡도는 O(n+k)이다.

계수 정렬의 공간 복잡도

심각한 비효울성을 초래할 수 있다. 예를 들어 데이터가 0과 999,999. 단 2개만 존재한다고 가정해보자. 이럴 대에도 리스트의 크기가 100만 개가 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 예를 들어 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적이다. 반면에 앞서 설명한 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵정렬을 이용하는 것이 유리하다. 다시 말해 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다. 하지만 조건만 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적으로 사용할 수 있다. 계수 정렬의 공간 복잡도는 O(N+K)

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동작방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(N+K)이다.

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

result = sorted(array)
print(result)

array.sort()
print(array)

정렬 라이브러리의 시간 복잡도

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(N*logN)을 보장한다. 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다.

  1. 정렬 라이브러리로 풀 수 있는 문제
  2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
  3. 더 빠른 정렬이 필요한 문제

실전문제2 - 위에서 아래로 p. 178

나의 코드)

문제를 보고 정렬 라이브러리로 풀 수 있는 문제의 형태로 파악하였고 라이브러리를 이용하여서 해결하였다.

정답 코드)

나의 코드와 동일

이 문제는 수의 개수가 50개 이하로 매우 적으며, 모든 수는 1이상 100,000 이하이므로 어떠한 정렬 알고리즘을 사용해도 문제를 해결할 수 있다. 앞서 공부한 선택, 삽입 등 아무거나 사용해도 상관없지만 간결해지는 라이브러리를 사용하는 것이 best이다.

실전문제3 - 성적이 낮은 순서로 학생 출력하기 p.180

정답 코드)

이 문제에서는 학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(n*logn) 을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다. 따라서 기본 정렬 라이브러리를 사용하는 것이 효과적이다.

여기서 기억해야 할 것은
a.sort() => 파괴적
sorted(a) => 비파괴적

둘 다 reverse와 key를 가질 수 있는데

a = sorted(array, reverse = True)
a = sorted(array, reverse = False)
  1. 내림차순 2. 오름차순 코드 그대로 이해하면 된다.
array = [(0,1),(2,2)]
a=sorted(array, key lambda x : x[1])

튜플의 두 번째 원소를 기준으로 정렬된다. sort의 key는 함수가 들어와야 하므로 파이썬에서는 람다를 자주 사용한다

람다는 lambda 매개변수 : 표현식 으로 표현된다.

ex)

map(lambda x,y : x+y, range(5)) 

comment)
람다의 중요성을 느꼈다. 정렬을 복습하면서 람다와 관련된 것도 마스터 하자.

실전문제4 - 두 배열의 원소 교체

나의 코드)

comment)
이 문제를 풀면서 문제를 조금 꼼꼼히 보자라고 느꼈다 맞을 문제도 틀리니깐 문제다 ㄹㅇ ㅋㅋㅋㅋㅋㅋㅋ 나는 k번 다 바꾸게끔 했지만, 생각해보면 바꿔서 손해일 수 도 있다 그러므로 바꿀때마다 b배열의 원소가 더 큰지 확인하는 조건문이 필요하다.

정답 코드)

이걸로 정렬은 끝났다. 생각보다 문제들이 쉬어서 금방 끝냈지만.. 과연 이렇게나 쉬울까... 군대에서 코딩하기 쉽지 않네 ㄹㅇ..

profile
군도리

1개의 댓글

comment-user-thumbnail
2022년 2월 12일

와우 가슴이 웅장해지네요!! 감사합니다

답글 달기