DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Aniruddha has posted 40 posts at DZone. View Full User Profile

QuickSort - C#

06.13.2012
| 5568 views |
  • submit to reddit
        public static int[] QuickSort(int[] arr)
        {
            if (arr.Length <= 1)
                return arr;

            int pivot = arr.Length - 1;

            int[] less = GetLessThanEqualToPivot(arr, pivot);
            int[] greater = GetGreaterThanPivot(arr, pivot);

            return Concatenate(QuickSort(less), arr[pivot], QuickSort(greater));
        }

        public static int[] Concatenate(int[] less, int pivotElement, int[] greater)
        {
            List<int> _result = new List<int>();
            _result.AddRange(less);
            _result.Add(pivotElement);
            _result.AddRange(greater);
            return _result.ToArray();
        }

        public static int[] GetLessThanEqualToPivot(int[] arr, int pivot)
        {
            List<int> _result = new List<int>();

            for (int i = 0; i < arr.Length - 1; i++)
            {
                if (arr[i] <= arr[pivot])
                {
                    _result.Add(arr[i]);
                }
            }

            return _result.ToArray();
        }

        public static int[] GetGreaterThanPivot(int[] arr, int pivot)
        {
            List<int> _result = new List<int>();
            for (int i = 0; i < arr.Length - 1; i++)
            {
                if (arr[i] > arr[pivot])
                {
                    _result.Add(arr[i]);
                }
            }
            return _result.ToArray();
        }

QuickSort - C#

 

Efficiency: O(nlog n)