[Python][leetCode] List Sort(리스트 정렬)

코딩테스트/LeetCode

[Python][leetCode] List Sort(리스트 정렬)

jungmin.park 2023. 10. 30. 19:12

https://leetcode.com/problems/sort-list/description/

Sort List - LeetCode

Can you solve this real interview question? Sort List - Given the head of a linked list, return the list after sorting it in ascending order. Example 1: [https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg] Input: head = [4,2,1,3] Output: [1,

leetcode.com

문제설명

연결 리스트가 주어졌을때 퀵 정렬로 정렬하는 방식으로 구현해보았다.

quick sort 방식은

pivot을 마지막에 두고

i, j를 두어서 i는 정렬된 자리를 찾을 역할, j는 순회를 하는 방식으로 사용했다.

이번에는 pivot을 리스트의 가장 맨 앞에 있는 값으로 하고

left와 right 빈 리스트를 만들어 pivot 보다 작으면 left, pivot 보다 크면 right로 데이터를 넣어

재귀함수로 구현 하는 것이다.

    def quicksort_2(self,data):
        if len(data) <= 1:
            return data

        pivot = data[0]
        left, right = list(), list()

        for index in range(1, len(data)):
            if pivot > data[index]:
                left.append(data[index])
            else:
                right.append(data[index])

        return self.quicksort_2(left) + [pivot] + self.quicksort_2(right)

    def quicksort_2(self,data):
        if len(data) <= 1:
            return data

        pivot = data[0]
        left, right = list(), list()

        for index in range(1, len(data)):
            if pivot > data[index]:
                left.append(data[index])
            else:
                right.append(data[index])

        return self.quicksort_2(left) + [pivot] + self.quicksort_2(right)