[엘리스] 절댓값 순 정렬

절댓값 순 정렬

문제 : n개의 숫자가 주어질 때, 이를 절댓값을 기준으로 오름차순 정렬하는 프로그램을 작성하세요. 만약 두 수의 절댓값이 같다면, 더 작은 숫자가 앞에 위치하게 됩니다. 이 실습 문제는 Quick sort로 구현해주세요.

 

입력 : 첫 번째 줄에 n개의 숫자가 주어집니다.

 

출력 : 절댓값을 기준으로 오름차순 정렬한 결과를 출력합니다.

 

입력 예시

-2 1 3 9 -5 6 7 -3

출력 예시

1 -2 -3 3 -5 6 7 9

풀이

1. Quick Sort

2. 절댓값 순 정렬

• 기저조건 : array가 1개 이하이면 자기자신 출력
• 임의로 pivot 출력 (중앙에 있는 값)
• pivot이 크면 왼쪽(left), pivot이 작으면 오른쪽(right), pivot이랑 같은데 음수이면 왼쪽 양수이면 오른쪽(equal)
• left에 대해서 QuickSort, right에 대해서 QuickSort 진행 (QuickSort(left) + equal + QuickSort(right))

import sys
sys.setrecursionlimit(100000)

def quickSort(array) :
    # 1. 기저조건 : array가 1개 이하이면 자기자신 출력 
    if len(array) < 2 :
        return array

    # 2. 임의로 pivot 출력 (중앙에 있는 값) 
    pivot = array[len(array)//2]

    # 3. left : pivot보다 작은 값, right : pivot보다 큰 값, equal : pivot하고 같은 값(절댓값 분리를 위함) 
    left = []
    right = []
    equal = []


    for x in array :
        # pivot이 크면 왼쪽 
        if abs(pivot) > abs(x) :
            left.append(x)

        # pivot이 작으면 오른쪽 
        elif abs(pivot) < abs(x) :
            right.append(x)

        # pivot이랑 같은데, 음수이면 왼쪽 양수이면 오른쪽 
        else :
            if x < 0 :
                equal = [x] + equal
            else :
                equal.append(x)

    # 4. 재귀호출로 left, right 각각에 대해 QuickSort진행
    return quickSort(left) + equal + quickSort(right)

def sortAbs(array):
    '''
    절댓값을 기준으로 오름차순 정렬한 결과를 반환하는 함수를 작성하세요.
    '''
    return quickSort(array)

def main():
    line = [int(x) for x in input().split()]

    print(*sortAbs(line))

if __name__ == "__main__":
    main()

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn