[Python] 내장함수 sorted 구현

이번에는 어디든지 많이 사용되는 내장함수 sorted를 구현하려고 한다.

 

실제 업무나, 코딩테스트 등등 정말 실생활(?)에 많이 사용되는 함수라고 생각된다.

 

또 대학교에서 처음 언어를 배울 때 최적화 해서 구현하는 것이 과제로 많이 나온다.

 

 

sorted의 기능은 글자 그대로 sort를 해주는 함수이다.

 

오름차순이나 내림차순으로 정렬을 해줄 수 있다.

 

내가 C 개발자라 신기했던 것 일 수 있지만 python에서는 어떤 키 값으로 sort할지도 정해줄 수 있다.

 

그럼 사용 방법을 보자

 

test1 = [7, 4, 2, 6, 8]
print(sorted(test1))

#[2, 4, 6, 7, 8]

test2 = [(1, 2), (6, 2), (5, 3), (10, 5)]
print(sorted(test2))

#[(1, 2), (5, 3), (6, 2), (10, 5)]

 

이렇게 각 요소를 오름차순으로 정렬해준다.

값이 여러 개 있는 경우 이렇게 앞의 요소로 정렬해준다.

 

정렬 알고리즘은 매우 많은 종류가 있다. 대표적으로는 삽입, 선택, 버블 정렬을 꼽을 수 있다.

여기서는 버블정렬을 구현해보겠다.

 

버블정렬을 먼저 보면

 

버블 정렬은 첫 번째 두 번째, 두 번째 세 번째, 세 번째 네 번째, … 이런 식으로 (n-1)번째 자료와 n번째 자료를 비교하여 교환하면서 자료를 정렬한다.

이렇게 한 사이클을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2번째 사이클에서는 n번째 자료는 정렬에서 제외되고, 사이클이 끝나면 n-1 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 추가된다.

 

그럼 구현해보겠다.

 

def my_sorted(iterable, key=None, reverse=False):
  if key is None:
    key = lambda x: x

  iterable = list(iterable)

  for i in range(len(iterable),1,-1):
    for j in range(1,i):
      key_a, key_b = key(iterable[j-1]), key(iterable[j])
      if((key_a>key_b and reverse==False) or (key_a<key_b and reverse==True)):
        iterable[j-1], iterable[j] = iterable[j], iterable[j-1]

  return iterable

추가된 것은 key와 reverse부분인데 키가 없을때는 key를 그대로 쓰도록 lambda x: x를 해주었다.

또 reverse(내림차순)으로 변경될 것을 대비하여 if문에 or로 처리를 해주었다.

 

두 값을 바꾸는 방법은 C언어를 처음 배울 때 다들 쓰는 swap 방법도 있지만

python은 유저친화적인 언어기 때문에

이렇게 아주 쉽게 구현할 수 있다.

 

그러면 테스트 해보자

 

assert sorted(test1) == my_sorted(test1)
assert sorted(test2) == my_sorted(test2) 
assert sorted(test2, reverse=True) == my_sorted(test2, reverse=True)
assert sorted(test2, key=lambda x: x[1]) == my_sorted(test2, key=lambda x: x[1])

 

여기서 4번째 줄에서 key를 사용했는데 test2의 첫 번째 튜플 값이 아닌 두 번째 튜플 값으로 sorting을 한 것이다.

 

실행을 시켜보면 잘 구현 된 것을 확인할 수 있다.