九. Sort 2 Kth Largest Element

Idea: Quicks sort is considered here for its time complexity is only O(nlogn)
While it is unnecessary to reorder other side(aimed value unattended) of array, so the time complexity reduced to O(n)

class Solution:
    # @param k & A a integer and an array
    # @return ans a integer
    def kthLargestElement(self, k, A):
        position = len(A)-1 - self.quicksort(A, 0, len(A)-1, k-1)
        return A[position]
        
    def quicksort(self, A, low, high, k):
        pivot = self.find_pivot(A,low, high)
        if pivot > k:
            position = self.quicksort(A, low, pivot-1, k)
            return position
        else:
            if pivot < k:
                position = self.quicksort(A, pivot+1, high, k)
                return position
            else:
                return pivot 
                
    def find_pivot(self, A, low, high):
        pivot = high
        leftwall = low
        
        for i in range(low, high):
            if A[i] < A[pivot]:
                A[leftwall], A[i] = A[i], A[leftwall]
                leftwall +=1
                
        A[high], A[leftwall] = A[leftwall], A[high]
        
        return leftwall