Use Lomuto's partitioning algorithm to partition the following list 3 29 2 49 36 4 14 6 9 12 The size of the partitions, you'll note are not very equal. Exchange values 3 and 9 (make 9 the first element and 3 the ninth element) and perform the partition again. Obviously, the equality of the partitions depends on the chosen pivot. Having the average case performance for QuickSelect being linear depends on Lomuto partitioning producing "good" partitions on average. There's a technique that guarantees linear QuickSort performance, but it is too complicated. Suggest a simple pivot choosing technique that might produce better results even in the worst cases for Lomuto (a sorted list and a reverse sorted list).

Thank you in advance!