Why my quick-sort get TLE ?


  • 0
    J

    Can anyone help me in finding the problem with the (ugly) code of quicksort ? Get TLE for a middle size input...

    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None
        def quick(lo, hi):
            if not lo or not hi: return None, None
            if lo==hi: return lo, hi
            lhead, ltail = None, None # head and tail for the parts smaller than pivot
            t = lo
            nd = t.next
            while t.next != hi:#partitioning
                nd = t.next
                if nd.val>lo.val: t = t.next
                else: 
                    if not lhead: lhead = nd
                    if not ltail: ltail = nd
                    elif nd.val==lo.val: #keys equal to lo put it to the end of left part
                        ltail.next, ltail = nd, nd
                        t.next, ltail.next = nd.next, None
                    else: #keys strictly smaller than lo put it to the end of left part
                        t.next = nd.next
                        nd.next = lhead
                        lhead = nd
                        
            # treat the case when t.next=hi
            if hi.val>=lo.val: t, t.next = hi, hi.next
            elif not lhead: lhead,ltail = hi, hi
            else: ltail.next, ltail = hi, hi
            rhead, rtail = (lo.next, t) if t!=lo else (None,None)
            #partition is over, we get 2 segments
            lhead,ltail = quick(lhead,ltail)
            rhead, rtail = quick(rhead, rtail)
            if ltail: ltail.next = lo
            lo.next = rhead
            if rtail: rtail.next = None
            return lhead, rtail
        tail = head
        while tail.next: tail = tail.next
        hd, tl = quick(head, tail)
        return hd

  • 0
    F

    Beacuse the quick sort may be O(N2) in the worst input


  • 0
    J

    But I performed a 3-way qsort (and this is easy as we are using linked lists)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.