1: namespace Question6_ThreeWayPartition
2: { 3: /// <summary>
4: /// Question: When given unsorted array of integers sort the array so that in the beggining will be all
5: /// the negative numbers (unordered), then zeros and then all the positives (unordered)
6: /// </summary>
7: class Program
8: { 9: static void Main(string[] args)
10: { 11: //test the sorting using 10 random arrays
12: for (int i = 0; i < 10; i++)
13: { 14: //generate the random array and a copy (in order to test in the two methods)
15: int[] array = Generate(15);
16:
17: //print the original
18: Console.Write("\nOrigianl array: "); 19: PrintArray(array);
20:
21: SortUsingThreeWayPartition(array);
22: Console.Write("\nModified array: "); 23: PrintArray(array);
24: }
25:
26: Console.ReadLine();
27: }
28:
29: /// <summary>
30: /// Random array generator (range is [-3,3])
31: /// </summary>
32: /// <param name="length">size of array</param>
33: /// <returns>the array</returns>
34: private static int[] Generate(int length)
35: { 36: int[] array = new int[length];
37: Random randomGenerator = new Random();
38: for (int i = 0; i < array.Length; i++)
39: { 40: array[i] = randomGenerator.Next(-3, 4); //between -3 and 3 in order to give enough chance for the zeros
41: }
42: return array;
43: }
44:
45: /// <summary>
46: /// Sorting method
47: /// </summary>
48: /// <param name="array"></param>
49: public static void SortUsingThreeWayPartition(int[] array)
50: { 51: int firstPartition = 0, secondPartition = 0, thirdPartition = array.Length - 1;
52:
53: while (secondPartition <= thirdPartition)
54: { 55: if (array[secondPartition] > 0)
56: { 57: Swap(array, secondPartition, thirdPartition--); //move to the third partition
58: }
59: else if (array[secondPartition] < 0)
60: { 61: Swap(array, firstPartition++, secondPartition++); //move to the first partition
62: }
63: else
64: { 65: secondPartition++; // leave in the second partition
66: }
67: }
68: }
69:
70: /// <summary>
71: /// Swaps between two values in array
72: /// </summary>
73: /// <param name="array"></param>
74: /// <param name="i"></param>
75: /// <param name="j"></param>
76: private static void Swap(int[] array, int i, int j)
77: { 78: if (i == j)
79: return;
80:
81: int temp = array[i];
82: array[i] = array[j];
83: array[j] = temp;
84: }
85:
86: /// <summary>
87: /// Simple method that prints the array
88: /// </summary>
89: /// <param name="array"></param>
90: private static void PrintArray(int[] array)
91: { 92: foreach (int i in array)
93: { 94: Console.Write(i);
95: Console.Write(" "); 96: }
97: Console.WriteLine();
98: }
99: }
100: }