퀵정렬 알고리즘

📋 퀵정렬 알고리즘

def quick_sort(input):
    if len(input) <= 1:
        return input  # 리스트의 길이가 1 이하면 바로 리턴

    pivot = input[0]  # 피벗을 리스트의 첫 번째 요소로 선택
    left = []  # 피벗보다 작은 값을 담을 리스트
    right = []  # 피벗보다 큰 값을 담을 리스트

    for i in range(1, len(input)):
        if input[i] < pivot:
            left.append(input[i])  # 피벗보다 작으면 left에 추가
        else:
            right.append(input[i])  # 피벗보다 크거나 같으면 right에 추가

    # 왼쪽 부분, 오른쪽 부분을 다시 퀵 정렬하고 병합
    return quick_sort(left) + [pivot] + quick_sort(right)

n = int(input())  # 리스트의 길이 입력

problem = []

for i in range(n):
    problem.append(int(input()))  # 원소 입력

result = quick_sort(problem)  # 퀵 정렬 수행

for i in range(n):
    print(result[i])  # 결과 출력

입력값

5 // 정렬할 정수의 개수 입력
3
2
4
1
5

출력값

1
2
3
4
5

삽질의 기록

n = int(input())

problem = []

for i in range(n):
    problem.append(int(input()))
def quick_sort(input):

    if len(input) == 1:
        return input[0]
    if len(input) == 2:
        if input[0] <= input[1]:
            return [input[0]] + [input[1]]
        else:
            return [input[1]] + [input[0]]

    pivot = input[0]
    low = 1
    high = len(input) - 1

    while high >= low:

        while input[low] > pivot or input[high] < pivot:

            if input[low] <= pivot:
                low += 1
            if input[high] >= pivot:
                high -= 1
            if high == 1:
                return [input[0]] + quick_sort(input[0:])
        if high > low:
            input[low], input[high] = input[high], input[low]
            low, high = high, low
            low += 1
            high -= 1

    input[0], input[high] = input[high], input[0]
    left_part = input[:low]
    right_part = input[low + 1:]

    return quick_sort(left_part) + [input[high]] + quick_sort(right_part)

print(quick_sort(problem))

결론적으로, 실패한 코드다. left와 right의 리스트를 새로 만들어서 거기에 요소를 담는 것이 아닌, 원래의 problem리스트를 찢어서 정렬하고싶었다. 근데 이것저것 수정하면서 예외적인 케이스를 다 입력해주어야 했고, 너무 많아져서 비효율적인 코드라는 것을 알게되었다.

예를 들어,

    if len(input) == 1:
        return input[0]
    if len(input) == 2:
        if input[0] <= input[1]:
            return [input[0]] + [input[1]]
        else:
            return [input[1]] + [input[0]]

퀵정렬을 재귀적으로 실행시키다가, 리스트에 요소가 1개 남았을 때, 2개 남았을 때 따로 생각해줘야하기 때문에 너무 복잡해진다.

또한, 피봇의 역할을 구현하기가 너무 복잡했다. problem리스트를 찢을 기준을 찾는 과정에서 low와 high가 계속 변하면서 경우에 따라, low와 high가 같아지는 현상도 발생한다.