Quick Sort on Linked List



Sort the given Linked List using quicksort. which takes O(n^2) time in worst case and O(nLogn) in average and best cases, otherwise you may get TLE.

Input:
In this problem, method takes 1 argument: address of the head of the linked list. The function should not read any input from stdin/console.
The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list.
There are multiple test cases. For each test case, this method will be called individually.

Output:
Set *headRef to head of resultant linked list.

User Task:
The task is to complete the function quickSort() which should set the *headRef to head of the resultant linked list.

Constraints:
1<=T<=100
1<=N<=200

Note: If you use "Test" or "Expected Output Button" use below example format




#User function Template for python3


def quickSort(head):

    a=[]

    while head:

        a.append(head.data)

        head=head.next

    p=Quick(a) #Calling QuickSort in


    for i in p:

        print(i,end=" ")

def Quick(a):

    if len(a)<=1:

        return a

    else:

        pivot=a.pop()

        left=[]

        right=[]

        for x in a:

           if x<pivot: 

               left.append(x)

           else: 

               right.append(x)

    return Quick(left)+[pivot]+Quick(right)

    

Comments

Post a Comment

Popular posts from this blog

Large Factorial of array

You are given an array   A   of integers of length   N . You need to calculate factorial of each number. The answer can be very large, so print it modulo   10 9  + 7 .   Example 1: Input: N = 5 A[] = {0, 1, 2, 3, 4} Output: 1 1 2 6 24 Explanation: Factorial of 0 is 1, factorial of 1 is 1, factorial of 2 is 2,  factorial of 3 is 6 and so on. Example 2: Input: N = 3 A[] = {5, 6, 3} Output: 120 720 6 Explanation: Factorial of 5 is 120, factorial of 6 is 720,  factorial of 3 is 6. Your Task: Complete the function  factorial()  which takes   list  a  and single integer  n , as input parameters and returns a list of factorials of the numbers in the list a.
Read more

Value equal to index value

Given an array   Arr   of   N   positive integers. Your task is to find the elements whose value is equal to that of its index value. Example 1: Input: N = 5 Arr[] = {15, 2, 45, 12, 7} Output: 2 Explanation: Only Arr[2] = 2 exists here. Example 2: Input: N = 1 Arr[] = {1} Output: 1 Explanation: Here Arr[1] = 1 exists. Your Task:   You don't need to read input or print anything. Your task is to complete the function  valueEqualToIndex()  which takes the array of integers  arr[]   and  n  as parameters and returns an array of indices where the given conditions are satified. When there is not such element exists then return an empty array of length 0. Expected Time Complexity:  O(N) Expected Auxiliary Space:  O(1) Note : There can be more than one element in the array which have same value as their index. You need to include every such element's index. Follows 1-based indexing of the array. Constraints: 1 ≤ N ≤ 10 5 1 ≤ Arr[i] ≤ 10 6
Read more

Largest Element in Array

  Given an array A[] of size n . The task is to find the largest element in it.   Example 1: Input: n = 5 A[] = {1, 8, 7, 56, 90} Output: 90 Explanation: The largest element of given array is 90.   Example 2: Input:   n = 7 A[] = {1, 2, 0, 3, 2, 4, 5} Output: 5 Explanation: The largest element of given array is 5.    def largest( arr, n):     return max(arr) #{ #  Driver Code Starts #Initial Template for Python 3 def main():     T = int(input())     while(T > 0):         n = int(input())         a = [int(x) for x in input().strip().split()]         print(largest(a, n))         T -= 1 if __name__ == "__main__":     main()    
Read more