﻿ C# - Quick sort

# 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 :

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 Code Editor: