Quick Sort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot.
Given an array arr[], its starting position is low (the index of the array) and its ending position is high(the index of the array).
Note: The low and high are inclusive.
Implement the partition() and quickSort() functions to sort the array.
Example 1:
Input: 
N = 5 
arr[] = { 4, 1, 3, 9, 7}
Output:
1 3 4 7 9
Example 2:
Input: 
N = 9
arr[] = { 2, 1, 6, 10, 4, 1, 3, 9, 7}
Output:
1 1 2 3 4 6 7 9 10
Your Task: 
You don't need to read input or print anything. Your task is to complete the functions partition()  and quickSort() which takes the array arr[], low and high as input parameters and partitions the array. Consider the last element as the pivot such that all the elements less than(or equal to) the pivot lie before it and the elements greater than it lie after the pivot.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(logN)
Constraints:
1 <= N <= 10^{3}
1 <= arr[i] <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Divide and conquer

Starter code: #User function Template for python3



class Solution:

    #Function to sort a list using quick sort algorithm.

    def quickSort(self,arr,low,high):

        # code here

    

    def partition(self,arr,low,high):

        # code here

    

Solutions:
class Solution:

	def quickSort(self, arr, low, high):
		if low < high:
			p_index = self.partition(arr, low, high)
			self.quickSort(arr, low, p_index - 1)
			self.quickSort(arr, p_index + 1, high)

	def partition(self, arr, low, high):
		pivot = arr[low]
		(left, right) = (low, high)
		while left < right:
			while arr[left] <= pivot and left < high:
				left += 1
			while arr[right] > pivot and right > low:
				right -= 1
			if left < right:
				(arr[left], arr[right]) = (arr[right], arr[left])
		(arr[low], arr[right]) = (arr[right], arr[low])
		return right


class Solution:

	def quickSort(self, arr, low, high):
		if low <= high:
			pi = self.partition(arr, low, high)
			self.quickSort(arr, low, pi - 1)
			self.quickSort(arr, pi + 1, high)

	def partition(self, arr, low, high):
		pivot = arr[low]
		i = low + 1
		j = high
		while i <= j:
			while i <= j and arr[i] <= pivot:
				i += 1
			while i <= j and arr[j] > pivot:
				j -= 1
			if i < j:
				(arr[i], arr[j]) = (arr[j], arr[i])
		pivot_index = j
		(arr[low], arr[pivot_index]) = (arr[pivot_index], arr[low])
		return pivot_index


class Solution:

	def quickSort(self, arr, low, high):
		return arr.sort()


class Solution:

	def quickSort(self, arr, low, high):
		if low < high:
			p = self.partition(arr, low, high)
			self.quickSort(arr, low, p - 1)
			self.quickSort(arr, p + 1, high)
		return arr

	def partition(self, arr, low, high):
		pivot = arr[high]
		swap_marker = low - 1
		for index_i in range(low, high + 1):
			if pivot >= arr[index_i]:
				swap_marker += 1
				if arr[swap_marker] > arr[index_i]:
					tmp = arr[swap_marker]
					arr[swap_marker] = arr[index_i]
					arr[index_i] = tmp
		return swap_marker


import random

class Solution:

	def quickSort(self, arr, low, high):
		if low >= high:
			return arr
		else:
			return self.partition(arr, low, high)

	def partition(self, arr, low, high):
		if low >= high:
			return arr
		pivot = arr[random.randrange(low, high)]
		i = low
		j = high
		while True:
			while arr[i] < pivot:
				i += 1
			while arr[j] > pivot:
				j -= 1
			if i <= j:
				if i < j:
					tmp = arr[i]
					arr[i] = arr[j]
					arr[j] = tmp
				i += 1
				j -= 1
			if i > j:
				break
		self.partition(arr, low, j)
		self.partition(arr, i, high)
		return arr


class Solution:

	def quickSort(self, arr, low, high):
		if low >= high:
			return
		p = self.partition(arr, low, high)
		self.quickSort(arr, low, p - 1)
		self.quickSort(arr, p + 1, high)

	def partition(self, arr, low, high):
		p = arr[low]
		i = low
		j = high
		while i < j:
			if arr[i] <= p:
				i += 1
			elif arr[j] >= p:
				j -= 1
			else:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
				j -= 1
		if p < arr[i]:
			p = i - 1
		else:
			p = i
		(arr[low], arr[p]) = (arr[p], arr[low])
		return p


class Solution:

	def p(self, arr, low, high):
		piviot = arr[low]
		i = low
		j = high
		while i < j:
			while arr[i] <= piviot and i < high:
				i += 1
			while arr[j] > piviot and j > low:
				j -= 1
			if i < j:
				(arr[i], arr[j]) = (arr[j], arr[i])
		(arr[low], arr[j]) = (arr[j], arr[low])
		return j

	def quickSort(self, arr, low, high):
		if low < high:
			j = Solution.p(self, arr, low, high)
			Solution.quickSort(self, arr, low, j - 1)
			Solution.quickSort(self, arr, j + 1, high)


class Solution:

	def quickSort(self, arr, low, high):
		if high <= low:
			return
		pi = self.partition(arr, low, high)
		self.quickSort(arr, low, pi - 1)
		self.quickSort(arr, pi + 1, high)

	def partition(self, arr, low, high):
		pivot = arr[high]
		i = low - 1
		for j in range(low, high):
			if arr[j] < pivot:
				i = i + 1
				(arr[i], arr[j]) = (arr[j], arr[i])
		(arr[i + 1], arr[high]) = (arr[high], arr[i + 1])
		return i + 1


class Solution:

	def quickSort(self, arr, l, h):
		if l < h:
			p = self.partition(arr, l, h)
			self.quickSort(arr, l, p - 1)
			self.quickSort(arr, p + 1, h)

	def partition(self, arr, l, h):
		piv = arr[h]
		i = l - 1
		for j in range(l, h):
			if arr[j] <= piv:
				i += 1
				(arr[i], arr[j]) = (arr[j], arr[i])
		(arr[i + 1], arr[h]) = (arr[h], arr[i + 1])
		return i + 1


class Solution:

	def quickSort(self, arr, low, high):
		arr.sort()

	def partition(self, arr, low, high):
		pass


class Solution:

	def quickSort(self, arr, low, high):
		if low < high:
			mid = self.partition(arr, low, high)
			self.quickSort(arr, low, mid)
			self.quickSort(arr, mid + 1, high)

	def partition(self, arr, low, high):
		pivot = arr[low]
		i = low - 1
		j = high + 1
		while True:
			i += 1
			while arr[i] < pivot:
				i += 1
			j -= 1
			while arr[j] > pivot:
				j -= 1
			if i >= j:
				return j
			(arr[i], arr[j]) = (arr[j], arr[i])


class Solution:

	def quickSort(self, arr, low, high):
		if low >= high:
			return
		i = low
		j = high
		pme = i + (j - i) // 2
		while i <= j:
			if arr[i] <= arr[pme]:
				i += 1
			elif arr[j] >= arr[pme]:
				j -= 1
			else:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
				j -= 1
		if pme < j:
			(arr[pme], arr[j]) = (arr[j], arr[pme])
			pme = j
		elif i < pme:
			(arr[pme], arr[i]) = (arr[i], arr[pme])
			pme = i
		self.quickSort(arr, low, pme - 1)
		self.quickSort(arr, pme + 1, high)


class Solution:

	def quickSort(self, arr, low, high):
		if high > low:
			pivot = arr[low]
			i = low + 1
			j = high
			while j >= i:
				if arr[i] < pivot:
					i += 1
				elif arr[j] > pivot:
					j -= 1
				else:
					temp = arr[i]
					arr[i] = arr[j]
					arr[j] = temp
					i += 1
					j -= 1
			arr[low] = arr[j]
			arr[j] = pivot
			self.quickSort(arr, low, j - 1)
			self.quickSort(arr, j + 1, high)


class Solution:

	def quickSort(self, arr, low, high):
		if low >= high:
			return
		pivotIndex = self.partition(arr, low, high)
		self.quickSort(arr, low, pivotIndex - 1)
		self.quickSort(arr, pivotIndex + 1, high)
		return

	def partition(self, arr, low, high):
		pivotVal = arr[low]
		start = low + 1
		end = high
		while start <= end:
			while start <= high and arr[start] <= pivotVal:
				start += 1
			while end >= low and arr[end] > pivotVal:
				end -= 1
			if start < end:
				(arr[start], arr[end]) = (arr[end], arr[start])
		(arr[low], arr[end]) = (arr[end], arr[low])
		return end


import random

class Solution:

	def quickSort(self, arr, low, high):
		if low >= high:
			return
		p = self.partition(arr, low, high)
		self.quickSort(arr, low, p - 1)
		self.quickSort(arr, p + 1, high)

	def partition(self, arr, low, high):
		r = random.randint(low, high)
		(arr[low], arr[r]) = (arr[r], arr[low])
		pindex = low
		curr = pindex + 1
		ptr2 = high
		while True:
			if arr[curr] <= arr[pindex]:
				curr += 1
				if curr > ptr2:
					break
			if arr[curr] >= arr[pindex]:
				(arr[curr], arr[ptr2]) = (arr[ptr2], arr[curr])
				ptr2 -= 1
				if curr > ptr2:
					break
		(arr[pindex], arr[ptr2]) = (arr[ptr2], arr[pindex])
		return ptr2


class Solution:

	def quickSort(self, arr, low, high):
		if low < high:
			pivot = self.partition(arr, low, high)
			self.quickSort(arr, low, pivot - 1)
			self.quickSort(arr, pivot + 1, high)

	def partition(self, arr, low, high):
		pivot = arr[low]
		start = low
		while low <= high:
			while low <= high and arr[low] <= pivot:
				low += 1
			while high >= low and arr[high] > pivot:
				high = high - 1
			if low <= high:
				(arr[low], arr[high]) = (arr[high], arr[low])
		(arr[low - 1], arr[start]) = (pivot, arr[low - 1])
		return low - 1


class Solution:

	def quickSort(self, arr, low, high):
		p = sorted(arr)
		m = 0
		for i in range(len(arr)):
			arr[i] = p[m]
			m += 1

	def partition(self, arr, low, high):
		pass


class Solution:

	def par(self, arr, low, high):
		pivot = arr[high]
		i = low - 1
		for j in range(low, high):
			if arr[j] <= pivot:
				i += 1
				(arr[i], arr[j]) = (arr[j], arr[i])
		(arr[i + 1], arr[high]) = (arr[high], arr[i + 1])
		return i + 1

	def quickSort(self, arr, low, high):
		if low < high:
			d = self.par(arr, low, high)
			self.quickSort(arr, low, d - 1)
			self.quickSort(arr, d + 1, high)


class Solution:

	def quickSort(self, arr, low, high):
		if low >= high or low < 0:
			return arr
		else:
			p = self.partition(arr, low, high)
			self.quickSort(arr, low, p - 1)
			self.quickSort(arr, p + 1, high)
		return arr

	def partition(self, arr, low, high):
		arr_tmp = arr
		pivot = arr[high]
		i = low - 1
		for j in range(low, high):
			if arr[j] <= pivot:
				i += 1
				(arr[i], arr[j]) = (arr[j], arr[i])
		i += 1
		(arr[i], arr[high]) = (arr[high], arr[i])
		return i


class Solution:

	def partition(self, arr, low, high):
		temp = arr[high]
		p = low - 1
		for i in range(low, high):
			if arr[i] < temp:
				p += 1
				(arr[p], arr[i]) = (arr[i], arr[p])
		(arr[p + 1], arr[high]) = (arr[high], arr[p + 1])
		return p + 1

	def quickSort(self, arr, low, high):
		if low < high:
			pivot = self.partition(arr, low, high)
			self.quickSort(arr, low, pivot - 1)
			self.quickSort(arr, pivot + 1, high)
		return arr


class Solution:

	def quickSort(self, arr, low, high):
		if low < high:
			part = self.partition(arr, low, high)
			self.quickSort(arr, low, part - 1)
			self.quickSort(arr, part + 1, high)
		else:
			return

	def partition(self, arr, low, high):
		pivot = arr[low]
		i = low + 1
		j = high
		while True:
			while j >= i and arr[j] >= pivot:
				j -= 1
			while i <= j and arr[i] <= pivot:
				i += 1
			if i <= j:
				(arr[i], arr[j]) = (arr[j], arr[i])
			else:
				break
		(arr[low], arr[j]) = (arr[j], arr[low])
		return j


class Solution:

	def quickSort(self, arr, low, high):
		if low >= high:
			return
		p = self.partition(arr, low, high)
		self.quickSort(arr, low, p - 1)
		self.quickSort(arr, p + 1, high)

	def partition(self, arr, low, high):
		pivot = arr[low]
		i = low + 1
		j = high
		while i <= j:
			while i <= j and arr[i] <= pivot:
				i += 1
			while i <= j and arr[j] > pivot:
				j -= 1
			if i < j:
				(arr[i], arr[j]) = (arr[j], arr[i])
		p_ind = j
		(arr[low], arr[p_ind]) = (arr[p_ind], arr[low])
		return p_ind


class Solution:

	def quickSort(self, A, low, high):
		if low < high:
			pindex = self.partition(A, low, high)
			self.quickSort(A, low, pindex - 1)
			self.quickSort(A, pindex + 1, high)

	def partition(self, A, low, high):
		pivot = A[high]
		pindex = low
		for i in range(low, high):
			if A[i] <= pivot:
				(A[i], A[pindex]) = (A[pindex], A[i])
				pindex += 1
		(A[pindex], A[high]) = (A[high], A[pindex])
		return pindex


class Solution:

	def quickSort(self, arr, low, high):
		if low < high:
			pivot = self.partition(arr, low, high)
			self.quickSort(arr, low, pivot - 1)
			self.quickSort(arr, pivot + 1, high)

	def partition(self, arr, low, high):
		pivot = low
		i = low
		j = i + 1
		while j <= high:
			if arr[j] >= arr[pivot]:
				j += 1
			else:
				i = i + 1
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 1
		(arr[i], arr[pivot]) = (arr[pivot], arr[i])
		return i


class Solution:

	def quickSort(self, arr, low, high):
		if len(arr) < 2:
			return
		if low < high:
			loc = self.partition(arr, low, high)
			self.quickSort(arr, low, loc - 1)
			self.quickSort(arr, loc + 1, high)

	def partition(self, arr, low, high):
		pivot = arr[high]
		i = low - 1
		for j in range(low, high):
			if arr[j] <= pivot:
				i += 1
				(arr[i], arr[j]) = (arr[j], arr[i])
		(arr[i + 1], arr[high]) = (arr[high], arr[i + 1])
		return i + 1


class Solution:

	def quickSort(self, a, l, h):
		if l < h:
			p = self.partition(a, l, h)
			self.quickSort(a, l, p)
			self.quickSort(a, p + 1, h)

	def partition(self, a, l, h):
		pivot = a[l]
		i = l - 1
		j = h + 1
		while True:
			i = i + 1
			while a[i] < pivot:
				i = i + 1
			j = j - 1
			while a[j] > pivot:
				j = j - 1
			if i >= j:
				return j
			(a[i], a[j]) = (a[j], a[i])


class Solution:

	def quickSort(self, arr, p, q):
		if p < q:
			mid = self.partition(arr, p, q)
			self.quickSort(arr, p, mid - 1)
			self.quickSort(arr, mid + 1, q)
		return arr

	def partition(self, arr, p, q):
		i = p
		pivot = arr[p]
		for j in range(i + 1, q + 1):
			if arr[j] < pivot:
				i += 1
				(arr[i], arr[j]) = (arr[j], arr[i])
		(arr[i], arr[p]) = (arr[p], arr[i])
		return i


class Solution:

	def quickSort(self, arr, low, high):
		if low < high:
			mid = self.partition(arr, low, high)
			self.quickSort(arr, low, mid - 1)
			self.quickSort(arr, mid + 1, high)
		return arr

	def partition(self, arr, low, high):
		pivot = low
		start = low + 1
		end = high
		while True:
			while start <= end and arr[start] <= arr[pivot]:
				start += 1
			while start <= end and arr[end] >= arr[pivot]:
				end -= 1
			if start <= end:
				(arr[start], arr[end]) = (arr[end], arr[start])
			else:
				break
		(arr[pivot], arr[end]) = (arr[end], arr[pivot])
		return end


class Solution:

	def quickSort(self, arr, low, high):
		if low > high:
			return
		pivot = self.partition(arr, low, high)
		self.quickSort(arr, low, pivot - 1)
		self.quickSort(arr, pivot + 1, high)

	def partition(self, arr, low, high):
		pivot_index = low
		low += 1
		moving_pointer = low
		while low <= high:
			if arr[low] < arr[pivot_index]:
				(arr[low], arr[moving_pointer]) = (arr[moving_pointer], arr[low])
				moving_pointer += 1
			low += 1
		(arr[moving_pointer - 1], arr[pivot_index]) = (arr[pivot_index], arr[moving_pointer - 1])
		return moving_pointer - 1


class Solution:

	def quickSort(self, arr, low, high):
		if low < high:
			partition = self.partition(arr, low, high)
			self.quickSort(arr, low, partition)
			self.quickSort(arr, partition + 1, high)
		return arr

	def partition(self, arr, low, high):
		pivote = arr[low]
		i = low - 1
		j = high + 1
		while True:
			j -= 1
			while pivote < arr[j]:
				j -= 1
			i += 1
			while arr[i] < pivote:
				i += 1
			if i < j:
				temp = arr[j]
				arr[j] = arr[i]
				arr[i] = temp
			else:
				return j


class Solution:

	def quickSort(self, arr, low, high):
		self.partition(arr, low, high)
		return arr

	def partition(self, arr, low, high):
		if low >= high:
			return
		pivotIdx = low
		leftIdx = low + 1
		rightIdx = high
		while leftIdx <= rightIdx:
			if arr[leftIdx] > arr[pivotIdx] and arr[rightIdx] < arr[pivotIdx]:
				(arr[leftIdx], arr[rightIdx]) = (arr[rightIdx], arr[leftIdx])
			if arr[leftIdx] <= arr[pivotIdx]:
				leftIdx += 1
			if arr[rightIdx] >= arr[pivotIdx]:
				rightIdx -= 1
		(arr[pivotIdx], arr[rightIdx]) = (arr[rightIdx], arr[pivotIdx])
		isLeftArraySmaller = rightIdx - 1 - low < high - (rightIdx + 1)
		if isLeftArraySmaller:
			self.partition(arr, low, rightIdx - 1)
			self.partition(arr, rightIdx + 1, high)
		else:
			self.partition(arr, rightIdx + 1, high)
			self.partition(arr, low, rightIdx - 1)


class Solution:

	def quickSort(self, arr, low, high):
		s = arr.sort()
		return s

	def partition(self, arr, low, high):
		s = arr.sort()
		returns


class Solution:

	def quickSort(self, arr, low, high):
		if low >= high:
			return
		pivot_idx = self.partition(arr, low, high)
		self.quickSort(arr, low, pivot_idx - 1)
		self.quickSort(arr, pivot_idx + 1, high)

	def partition(self, arr, low, high):
		pivot = high
		idx = low - 1
		for j in range(low, high):
			if arr[j] <= arr[pivot]:
				idx += 1
				(arr[idx], arr[j]) = (arr[j], arr[idx])
		(arr[idx + 1], arr[pivot]) = (arr[pivot], arr[idx + 1])
		return idx + 1


class Solution(object):

	def quickSort(self, nums, low, high):
		if low < high:
			pivot = self.partition(nums, low, high)
			self.quickSort(nums, low, pivot - 1)
			self.quickSort(nums, pivot + 1, high)
		return nums

	def partition(self, nums, low, high):
		pivot = low
		(left, right) = (low + 1, high)
		while left <= right:
			while left <= right and nums[left] <= nums[pivot]:
				left += 1
			while left <= right and nums[pivot] < nums[right]:
				right -= 1
			if left <= right:
				(nums[left], nums[right]) = (nums[right], nums[left])
		(nums[pivot], nums[right]) = (nums[right], nums[pivot])
		return right


import random

class Solution:

	def quickSort(self, arr, low, high):
		self.partition(arr, low, high)
		return arr

	def partition(self, arr, low, high):
		if low >= high:
			return
		pivot = random.randint(low, high)
		(arr[pivot], arr[low]) = (arr[low], arr[pivot])
		(smaller, bigger) = (low + 1, high)
		while smaller <= bigger:
			if arr[smaller] < arr[low]:
				smaller += 1
			elif arr[bigger] > arr[low]:
				bigger -= 1
			else:
				(arr[smaller], arr[bigger]) = (arr[bigger], arr[smaller])
				smaller += 1
				bigger -= 1
		(arr[low], arr[bigger]) = (arr[bigger], arr[low])
		self.partition(arr, low, bigger)
		self.partition(arr, bigger + 1, high)


class Solution:

	def quickSort(self, arr, low, high):
		if high <= low:
			return
		p = Solution.partition(self, arr, low, high)
		Solution.quickSort(self, arr, low, p - 1)
		Solution.quickSort(self, arr, p + 1, high)

	def partition(self, arr, low, high):
		p1 = low + 1
		p2 = high
		while p1 <= p2:
			if arr[p1] <= arr[low]:
				p1 += 1
			elif arr[p2] > arr[low]:
				p2 -= 1
			else:
				(arr[p1], arr[p2]) = (arr[p2], arr[p1])
				p1 += 1
				p2 -= 1
		(arr[low], arr[p2]) = (arr[p2], arr[low])
		return p2