1. Engineering
  2. Computer Science
  3. finish the partition and quicksort method to return a sorted...

Question: finish the partition and quicksort method to return a sorted...

Question details

Finish the Partition() and Quicksort() method to return a sorted array using Quicksort. Starting code is below:

import unittest

def partition(A, p, r):
   """
   Given an array A, partition the subarray A[p..r], using A[r] as the pivot value.

   :param A: the array to be merged
   :param p: the left boundary
   :param r: the right boundary
   :type A: list
   :type p: int
   :type r: int
   """
   pass
  
  
  

def QuickSort(A, p, r):
   """
   Sort the subarray A[p..r] in place, recursively.

   :param A: the input array
   :param p: left boundary of the subarray to be sorted
   :param r: right boundary of the subarray to be sorted
   :type A: list
   :type p: int
   :type r: int
   """
   pass  


class TestQuickSort( unittest.TestCase):
   """ A testing class - run automatically every time this
   script is called
   """

   # Partition
   def test_partition_1(self):

       A = [ 2, 8, 7, 1, 3, 5, 6, 4 ]
       q = partition(A, 0, 7)
       self.assertEqual( A, [2, 1, 3, 4, 7, 5, 6, 8] )
       self.assertEqual( q, 3)

   def test_partition_2(self):

       A = [ 5, 2, 4, 7, 1, 3, 2, 6 ]
       q = partition(A, 0, 7)
       self.assertEqual(A, [5, 2, 4, 1, 3, 2, 6, 7])
       self.assertEqual(q, 6)


   def test_partition_2_single_elements_halves(self):
       """ Special case: 2-element array"""
       A = [ 4, 7 ]
       q = partition(A, 0, 1)
       self.assertEqual( A, [4, 7])
       self.assertEqual( q, 1)

   def test_partition_3(self):
       """ Emtpy L-partition """
      
       A = [7, 12, 6, 15, 32, 39, 35, 31, 41, 38, 47, 1 ]
       partition(A, 0, 11)
       self.assertEqual( A, [1,12,6,15,32,39, 35, 31, 41, 38, 47,7])

   def test_partition_4(self):
       """ Emtpy R-partition """
      
       A = [7, 12, 6, 15, 32, 39, 35, 31, 41, 38, 47, 50 ]
       partition(A, 0, 11)
       self.assertEqual( A, [7,12,6,15,32,39, 35, 31, 41, 38, 47,50])

   def test_quicksort_1(self):
       """ Non repeated numbers"""
      
       A = [1, 12, 6, 15, 32, 39, 35, 31, 41, 38, 47, 7 ]
       QuickSort(A, 0, 11)
       self.assertEqual( A, [1,6,7,12,15,31,32,35,38,39,41,47])

   def test_quicksort_2(self):
       """ Repeated numbers """
      
       A = [ 5, 2, 4, 7, 1, 3, 2, 6 ]
       QuickSort(A, 0, 7)
       self.assertEqual( A, [ 1, 2, 2, 3, 4, 5, 6, 7 ])

   def test_quicksort_uneven_length(self):
       """ Array of uneven length """
      
       A = [ 5, 4, 7, 1, 3, 2, 6 ]
       QuickSort(A, 0, 6)
       self.assertEqual( A, [ 1, 2, 3, 4, 5, 6, 7 ])
  
   def test_quicksort_2_element_array(self):
       """special case: 2-element array """
      
       A = [ 5, 4 ]
       QuickSort(A, 0, 1)
       self.assertEqual( A, [4, 5])
  
   def test_quicksort_1_element_array(self):
       """ special case: 1-element array"""
      
       A = [ 5 ]
       QuickSort(A, 0, 0)
       self.assertEqual( A, [5])


def main():
   unittest.main()

if __name__ == '__main__':
   main()

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution