Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted
m ({{out}})
Line 773: Line 773:
}</lang>
}</lang>
=={{header|C sharp|C#}}==
=={{header|C sharp|C#}}==
Note that actually Array.Sort and ArrayList.Sort both use an unstable implementation of the quicksort algorithm.
Note that Array.Sort and ArrayList.Sort both use an unstable implementation of the quicksort algorithm.
<lang csharp>using System;
<lang csharp>namespace Sort {
using System.Collections.Generic;
using System;


static class QuickSort<T> where T : IComparable {
namespace QuickSort
#region Constants
{
private const Int32 insertionLimitDefault = 32;
class Program
private const Int32 pivotSamples = 5;
{
#endregion
static void Main(string[] args)
{
List<int> unsorted = new List<int> { 1, 3, 5, 7, 9, 8, 6, 4, 2 };
List<int> sorted = quicksort(unsorted);


#region Properties
Console.WriteLine(string.Join(",", sorted));
public static Int32 InsertionLimit { get; set; }
Console.ReadKey();
private static Random Random { get; set; }
#endregion

#region Constructors
static QuickSort() {
InsertionLimit = insertionLimitDefault;
Random = new Random();
}
#endregion

#region Sort Methods
public static void Sort(T[] entries) {
Sort(entries, 0, entries.Length - 1);
}

public static void Sort(T[] entries, Int32 first, Int32 last) {
var length = last + 1 - first;
while (length > 1) { // Tail recurse over longer partition
if (length < InsertionLimit) {
InsertionSort<T>.Sort(entries, first, last);
return;
}
}


private static List<int> quicksort(List<int> arr)
var median = pivot(entries, first, last);

{
var left = first;
List<int> loe = new List<int>(), gt = new List<int>();
if (arr.Count < 2)
var right = last;
return arr;
partition(entries, median, ref left, ref right);

int pivot = arr.Count / 2;
int pivot_val = arr[pivot];
var leftLength = right + 1 - first;
arr.RemoveAt(pivot);
var rightLength = last + 1 - left;

foreach (int i in arr)
{
if (leftLength < rightLength) {
if (i <= pivot_val)
Sort(entries, first, right);
loe.Add(i);
first = left;
else if (i > pivot_val)
length = rightLength;
}
gt.Add(i);
}
else {
Sort(entries, left, last);
List<int> resultSet = new List<int>();
last = right;
resultSet.AddRange(quicksort(loe));
length = leftLength;
if (loe.Count == 0){
}
}
loe.Add(pivot_val);
}else{
}

gt.Add(pivot_val);
private static T pivot(T[] entries, Int32 first, Int32 last) {
}
resultSet.AddRange(quicksort(gt));
var length = last + 1 - first;
var sampleSize = Math.Min(pivotSamples, length);
return resultSet;
var right = first + sampleSize - 1;
for (var left = first; left <= right; left++) {
// Random sampling avoids pathological cases
var random = Random.Next(left, last + 1);
// Sample without replacement
if (left != random)
Swap(entries, left, random);
}

InsertionSort<T>.Sort(entries, first, right);
return entries[first + sampleSize / 2];
}

private static void partition(T[] entries, T pivot, ref Int32 left, ref Int32 right) {
while (left <= right) {
while (pivot.CompareTo(entries[left]) > 0)
left++; // pivot follows entry
while (pivot.CompareTo(entries[right]) < 0)
right--; // pivot precedes entry

if (left < right) // Move entries to their correct partition
Swap(entries, left++, right--);
else if (left == right) { // No swap needed
left++;
right--;
}
}
}

internal static void Swap(T[] entries, Int32 index1, Int32 index2) {
var entry = entries[index1];
entries[index1] = entries[index2];
entries[index2] = entry;
}
#endregion

#region Insertion Sort
static class InsertionSort<T> where T : IComparable {
public static void Sort(T[] entries, Int32 first, Int32 last) {
for (var i = first + 1; i <= last; i++) {
var insert = entries[i];
var j = i;
while (j > first && entries[j - 1].CompareTo(insert) > 0)
entries[j] = entries[--j];
entries[j] = insert;
}
}
}
}
}
#endregion
}
}</lang>
}</lang>


Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Quicksort"