I'm currently learning programming for the first time and I've created the following implementation of quick sort in C#. I basically read a very basic overview of how quick sort works recursively and implemented it without looking at any concrete examples of its implementation so that I could learn the most from it.
Could you let me know what you think and where it could be optimized?
class Program
{
static void Main(string[] args)
{
var input = new int[] { 10, 3, 20, 5, 200 };
QuickSort(0, 0, input.Length-1, input);
Console.WriteLine("Sorted output: :");
new List<int>(input).ForEach(x => Console.Write(x + ","));
Console.ReadLine();
}
/// <summary>
/// sample input: 5 7 3 9 2
/// same output: 2 3 5 7 9
/// </summary>
/// <param name="numbers"></param>
public static void QuickSort(int pivotIndex, int startIndex, int endIndex, int[] numbers)
{
if (startIndex == endIndex) return;
int pivotNumber = numbers[pivotIndex];
var lowerThanPivot = new List<int>();
var higherThanPivot = new List<int>();
for(int i = startIndex; i <= endIndex; i++)
{
if(i != pivotIndex)
{
if( numbers[i] <= pivotNumber )
lowerThanPivot.Add(numbers[i]);
else
higherThanPivot.Add(numbers[i]);
}
}
// now lets put the pivot number in the correct place
numbers[startIndex + lowerThanPivot.Count] = pivotNumber;
// reinsert the numbers lower than pivot in the right place
int z = startIndex;
lowerThanPivot.ForEach(x => numbers[z++] = x);
z++; // *** skip over the new pivot index ***
// reinsert the numbers higher than pivot in the right place
higherThanPivot.ForEach(x => numbers[z++] = x);
// recursively call to sort each remaining elements
int newLeftPivot = startIndex;
int newEndLeftIndex = newLeftPivot + lowerThanPivot.Count - 1 ;
int newRightPivot = lowerThanPivot.Count + 1;
int newEndRightIndex = newRightPivot + higherThanPivot.Count - 1;
if(lowerThanPivot.Count> 0)
QuickSort(newLeftPivot, newLeftPivot, newEndLeftIndex, numbers);
if(higherThanPivot.Count > 0)
QuickSort(newRightPivot, newRightPivot, newEndRightIndex, numbers);
}
}