QuickSort, C# - rextester

QuickSort

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Microsoft (R) Visual C# Compiler version 2.9.0.63208 (958f2354)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int[] nums = {2, 8, 7, 3, 4, 5, 6};
            
            QuickSort(nums, 0, nums.Length-1); // initial call to QuickSort the entire nums array
            
            // Just printing out the array at the end to show the result
            foreach (int num in nums) {
                Console.Write(num + " ");
            }
        }
        
        // As you can see, the QuickSort method itself is very short; partitioning is the difficult part.
        public static void QuickSort(int[] arr, int start, int end) {
            if (start<end) {
                int pivot = Partition(arr, start, end); // partition the array
                
                QuickSort(arr, start, pivot-1); // repeat the process for the sub-array on the left
                
                QuickSort(arr, pivot+1, end); // repeat the process for the sub-array of the right
            }
        }
        
        /*
        The below method performs array partitioning, I programmed it in a way that replicates the animation in the slides, here: 
        https://docs.google.com/presentation/d/1-m9hAD7rDPXII6IIrhHc5YSGPAfLisVGz8DLL-ojJcI/edit#slide=id.g901da5fe9a_0_5
        
        A second way to program the partion method is shown below this one. That version is easier to program, but may be more difficult to explain.
        
        This method takes in the array it is partioning and two integers, defining the start and end of the sub-array it must partition.
        Consider the array: {2, 8, 7, 3, 4, 5, 6}
        Given start = 0 and end = 6, the method below will partition the entire array around 6 (like in the slides).
        However, given start = 0 and end = 3, the method will partition the subarray {2, 8, 7, 3} around 3.
        */
        public static int Partition(int[] arr, int start, int end) {
            int pivot = end; // Pivot index
            int pivotEl = arr[end]; // pivot element is the last item in the subarray
            
            // Creating indices for "itemFromLeft" and "itemFromRight"
            int left = -1;
            int right = -1;
            
            do {
                // find itemFromLeft, first item from the left greater than or equal to the pivot element
                for (int i=start; i<=end; i++) {
                    if (arr[i]>=pivotEl) {
                        left = i;
                        break;
                    }
                }

// find itemFromRight, first item from the right less than the pivot element
                for (int i=end; i>=start; i--) {
                    if (arr[i]<pivotEl) {
                        right = i;
                        break;
                    }
                }

// If left comes before right, swap them (swap is the same as BubbleSort)
                if (left < right) {
                    int temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
            } while (left<right); // Repeat until right comes before left
            
            // Once right comes before left, swap left with the pivot
            int temp2 = arr[left];
            arr[left] = arr[pivot];
            arr[pivot] = temp2;
            
            // Return left to show where the two arrays break apart (left would be 4 after we partition the array on 6 in the animation in the slides)
            return left;
        }
        
        /*
        The below method is another way to perform array partitioning, it achieves the same thing as the method above. Some people may find this approach easier than the one we learnt and it
        is no less correct.
        This method is explained quite clearly and visually in the following YouTube video:
        https://youtu.be/MZaf_9IZCrc
        
        As with the above, this method takes in the array it is partioning and two integers, defining the start and end of the sub-array it must partition (here called low and high).
        */
        static int partition(int []arr, int low, int high) 
        { 
            int pivot = arr[high];  // pivot is last element in subarray

// i starts just before the array currently being considered (explained in YT video linked above)
            int i = (low - 1);
            
            for (int j = low; j < high; j++) 
            { 
                // If jth element is smaller than the pivot, add 1 to i and the swap i and j (shown in video)
                if (arr[j] < pivot) 
                { 
                    i++;

// swap arr[i] and arr[j], same as BubbleSort
                    int temp = arr[i]; 
                    arr[i] = arr[j]; 
                    arr[j] = temp; 
                } 
            }

// At the end, swap the pivot element into its correct place in the subarray
            int temp1 = arr[i+1]; 
            arr[i+1] = arr[high]; 
            arr[high] = temp1;

// return the pivot element's position in the array once the partitioning is complete
            return i+1; 
        } 
    }
}


run \| edit \| history \| help	0