Why is my C++ Quick Sort Recursive Solution TLE?


  • 0
    L

    I'm not sure whether this Quick Sort Solution is right and bug free, but why Limited Time Exceeded?

    class Solution {
    private:
        ListNode* getMiddle(ListNode* head) {
            ListNode* slow = head;
            ListNode* fast = head -> next;
            while (fast && fast -> next) {
                slow = slow -> next;
                fast = fast -> next -> next;
            }
            return slow;
        }
    
        ListNode* partition(ListNode* head) {
            int x = head ? head -> val : 0;
            ListNode* leftDummy = new ListNode(0);
            ListNode* rightDummy = new ListNode(0);
            ListNode* left = leftDummy;
            ListNode* right = rightDummy;
            
            while (head) {
                if (head -> val < x) {
                    left -> next = head;
                    left = left -> next;
                }
                else {
                    right -> next = head;
                    right = right -> next;
                }
                head = head -> next;
            }
            
            right -> next = NULL;
            left -> next = rightDummy -> next;
            
            return leftDummy -> next;
        }
        
    public:
        ListNode* sortList(ListNode* head) {
            if (!head || !head -> next) {
                return head;
            }
            ListNode* tail = head;
            head = partition(head);
            // cout << head -> val << endl;
            
            ListNode* right = sortList(tail -> next);
            tail -> next = NULL;
            ListNode* left = sortList(head);
            tail -> next = right;
            
            return left;
        }
    };
    

  • 0

    There is totally unnecessary to adopt quick sort here since its complexity will also O(n^2) so it will be actually better using insertion sort.


  • 0
    B

    mergesort is the best choice


  • 0

    I use quick sort first and i failed too. Did you failed at the case 13313131....?
    I think the reason is that we choose the first node as pivot and we do not deal with the equal number case. sorry about having no time to view your code.
    (so that if every time the pivot we choose is the largest or the smallest ,it will be meet the worst case which is O(n^2) complexity)
    If you want to fix it, try to split the list into 3 parts: left is small than pivot, right is larger, and middle is equal to the pivot.
    BTW, i dont think insertion is O(nlogn), since you cant get an logn way to find wihch position to insert...
    check my sulotion here https://discuss.leetcode.com/topic/58354/my-c-solution-in-merge-sort-and-quick-sort-witch-comment-40ms-82ms hope this can help you.


Log in to reply
 

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