C#.

Your task is to write a method called 'Partition', which takes an array of integers as well as the index of the first and last elements of the portion of the array to be partitioned.

The partition method must take the elements in the array and, using the first element of the array as a pivot, order it such that all elements lower than the pivot value come before the pivot, and all elements higher than the pivot value come after the pivot. It must then return the new position of the pivot.

For instance, given the following array of 20 integers:

int[] array = { 27, 55, 23, 43, 32, 67, 19, 6, 45, 12, 23, 47, 2, 82, 63, 33, 71, 25, 55, 19 };

The first element is the pivot. Numbers lower than the pivot must be rearranged to appear before the pivot, while numbers higher than the pivot must come after it.

int[] array = { 27, 55, 23, 43, 32, 67, 19, 6, 45, 12, 23, 47, 2, 82, 63, 33, 71, 25, 55, 19 };

Calling Partition(array, 0, 21) to partition the entire array would reorganise it like this:

{ 2, 6, 12, 19, 19, 27, 55, 23, 43, 32, 67, 45, 23, 47, 82, 63, 33, 71, 25, 55 }

As you can see, numbers lower than the pivot (21) are on the left side of the array. Numbers greater than the pivot are on the right side, and the pivot itself appears in the middle. (In terms of the algorithm itself, it does not matter whether numbers that are exactly equal to the pivot go on the left or right side, as long as they consistently go on one side or the other). As the pivot has moved from position 0 in the array to position 5, the Partition() method returns the value 5.

The pseudocode is reproduced here for your convenience:

left = first, right = last // let the pivot value be the first element list[first] while (left < right) // while searches haven't met // find a small value in the right half while (list[right] > list[first]) decrement right end while // find a large value in the left half while (left < right) AND (list[left] <= list[first]) // still more to do increment left end while // if both found, then swap if (left < right) then swap the left and right elements end if end while // now put pivot in its place  pivot position = right(= left) swap the first and right elements return right // return pivot position 

Please use the sample code in your answer:

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;

namespace Partition { class Program { public static int Partition(int[] array, int first, int last) { // Write your Partition method here. // // Partition partitions the elements of array between array[first] // and array[last] (inclusive), using array[first] as the pivot. // // After Partition returns, all elements of a lower value than the // pivot will appear before the pivot in the array, while all // elements of a greater value will appear after the pivot. // // The return value is the new position of the pivot. // ... } public static void PrintArray(int[] array) { for (int i = 0; i < array.Length; i++) { if (i > 0) { Console.Write(", "); } Console.Write("{0}", array[i]); } Console.WriteLine(); }

public static void QuickSort(int[] array, int first, int last) { int pivot;

if (first < last) { pivot = Partition(array, first, last); QuickSort(array, first, pivot - 1); QuickSort(array, pivot + 1, last); } } static void Main(string[] args) { int[] array = new int[20]; Random rng = new Random(); for (int i = 0; i < array.Length; i++) { array[i] = rng.Next(0, 100); } Console.WriteLine("Unsorted array:"); PrintArray(array);

Console.WriteLine("Partitioned array:"); Partition(array, 0, array.Length - 1); PrintArray(array);

Console.WriteLine("Sorted array:"); QuickSort(array, 0, array.Length - 1); PrintArray(array);

Console.WriteLine(" Press enter to exit."); Console.ReadLine(); } } }