[Algorithm] 정렬 (Sorting)

정렬(Sorting)은 데이터를 어떠한 기준에 따라서 순서대로 나열하는 것입니다.

정렬 알고리즘은 가장 기본이 되는 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort)부터 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort), 계수 정렬(Count Sort) 등 매우 다양합니다.

 

코딩테스트에서는 Python 기본 정렬 라이브러리를 사용하면 충분히 빠른 시간내에(O(NlogN)) 정렬을 수행할 수 있습니다.

따라서, 정렬 라이브러리 사용 예제 몇 가지를 확인해 보겠습니다.

 

<리스트 정렬>

def solution(arr):
    sorted_arr = arr.copy()

    sorted_arr.sort()
    # sorted_arr.sort(reverse=True)
    # sorted_arr = sorted(sorted_arr)
    # sorted_arr = sorted(sorted_arr, reverse=True)

    return sorted_arr


arr = [15, 27, 12]

results = solution(arr)
print(results) # [12, 15, 27]

리스트 객체의 sort() 메소드를 사용하여 정렬할 수 있고, 다른 방법으로는 sorted()함수의 리턴으로 정렬된 리스트를 얻을 수 있습니다. reverse옵션의 default는 False이며, 오름차순입니다. 반대로 True일 경우 내림차순입니다.

 

<튜플 정렬>

def solution(keys, values):
    arr = []

    for key, value in zip(keys, values):
        arr.append((key, value))

    sorted_arr = sorted(arr, key=lambda x: x[1])
    # sorted_arr = sorted(arr, key=lambda x: x[1], reverse=True)

    return sorted_arr


names = ['Mike', 'Joe', 'Tony']
scores = [95, 78, 85]

results = solution(names, scores)
print(results) # [('Joe', 78), ('Tony', 85), ('Mike', 95)]

이름과 점수를 입력으로 받았을 때, 점수를 기준으로 정렬하기 위한 방법입니다.

먼저 이름과 점수를 튜플 형태로 만들고(이름, 점수) 리스트에 저장합니다.

이후 sorted함수에 lambda를 사용하여 정렬합니다. key=lambda x: x[1]에서 arr을 정렬할 때 x[1], 즉 점수를 기준으로 정렬한다는 의미입니다. x는 lambda로 사용되기 때문에, key=lambda aaaa: aaaa[1]식으로 아무 이름이나 사용하면 됩니다.