w3resource

C#: Quick sort

C# Sharp Searching and Sorting Algorithm: Exercise-9 with Solution

Write a C# Sharp program to sort a list of elements using Quick sort.

Quick sort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined.

Pictorial presentation - Quick Sort algorithm :

c # Quick sort part-1
c # Quick sort part-2
Quick sort animation
Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.

Animation credits : RolandH

Sample Solution:-

C# Sharp Code:

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

namespace Quick_Sort
{
    class Program
    {
        // Method to perform Quick Sort on an array
        private static void Quick_Sort(int[] arr, int left, int right) 
        {
            // Check if there are elements to sort
            if (left < right)
            {
                // Find the pivot index
                int pivot = Partition(arr, left, right);

                // Recursively sort elements on the left and right of the pivot
                if (pivot > 1) {
                    Quick_Sort(arr, left, pivot - 1);
                }
                if (pivot + 1 < right) {
                    Quick_Sort(arr, pivot + 1, right);
                }
            }
        }

        // Method to partition the array
        private static int Partition(int[] arr, int left, int right)
        {
            // Select the pivot element
            int pivot = arr[left];

            // Continue until left and right pointers meet
            while (true) 
            {
                // Move left pointer until a value greater than or equal to pivot is found
                while (arr[left] < pivot) 
                {
                    left++;
                }

                // Move right pointer until a value less than or equal to pivot is found
                while (arr[right] > pivot)
                {
                    right--;
                }

                // If left pointer is still smaller than right pointer, swap elements
                if (left < right)
                {
                    if (arr[left] == arr[right]) return right;

                    int temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
                else 
                {
                    // Return the right pointer indicating the partitioning position
                    return right;
                }
            }
        }

        static void Main(string[] args)
        {
            int[] arr = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };

            Console.WriteLine("Original array : ");
            foreach (var item in arr)
            {
                Console.Write(" " + item);    
            }
            Console.WriteLine();

            // Call Quick Sort to sort the array
            Quick_Sort(arr, 0, arr.Length-1);

            Console.WriteLine();
            Console.WriteLine("Sorted array : ");

            foreach (var item in arr)
            {
                Console.Write(" " + item);
            }
            Console.WriteLine();
        }
    }
}

Sample Output:

Original array :                                                                                              
 2 5 -4 11 0 18 22 67 51 6                                                                                    
                                                                                                              
Sorted array :                                                                                                
 -4 0 2 5 6 11 18 22 51 67 
 

Flowchart:

C# Sharp Searching and Sorting Algorithm Exercises: Quick sort - Part-1

C# Sharp Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C# Sharp program to sort a list of elements using Permutation sort.
Next: Write a C# Sharp program to sort a list of elements using Radix sort algorithm.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.