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 = { 22, 50, 59, 21, 38, 65, 5, 48, 81, 60, 73, 54, 89, 75, 17, 44, 3, 49, 19, 13 };

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 = { 22, 50, 59, 21, 38, 65, 5, 48, 81, 60, 73, 54, 89, 75, 17, 44, 3, 49, 19, 13 };

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

{ 5, 13, 19, 21, 3, 17, 22, 48, 81, 60, 73, 54, 89, 75, 65, 44, 38, 49, 59, 50 }

As you can see, numbers lower than the pivot (22) 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 6, the Partition() method returns the value 6.

Lecture 9 contains detailed pseudocode for implementing this method on slides 31 and 32- however, it calls this method 'Split'. 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 

If the pseudocode is confusing it is recommend that you read the other slides about QuickSort and the Split algorithm first, to ensure you have a good grasp of the algorithm before you attempt to start implementing it.

The provided Main() method tests your Partition() method by calling it once on a randomly-generated array, then calls a QuickSort() method which uses your Partition() method to completely sort the array. You should get output similar to this when your method is working properly:

The exact numbers will vary as the array is randomly generated- however, the first number in the original array (79) is chosen as a pivot, and in the partitioned array, all numbers less than 79 come before it in the array and all numbers after 79 come after it in the array. The sorted array is correctly sorted in ascending order.

Note that the Main() method of the provided code is never called- only the Partition() method is called in order to test your program. This also means your Partition()method must be public.

If you still have difficulties, here are some tips when writing programs for AMS:

Do not write your program directly into the text box. You should copy and paste the sample code into Visual Studio, write your program there, run it and test it to make sure it works, then paste it into AMS. You only get a limited number of attempts at each AMS exercise, so make sure they count.

Sample code:

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(); } } }