Быстрая сортировка по Сейджвику
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class QuickSort { public int Partition(ref int[] a, int lo, int hi) { int i = lo; int j = hi + 1; int v = a[lo]; // central element while (true) { while (a[++i] < v) if (i == hi) break; while (v <= a[--j] ) if (j == lo) break; if (i >= j) break; Exch(ref a, i, j); } Exch(ref a, lo, j); return j; } public void Sort(ref int[] a, int lo, int hi) { if (hi <= lo) return; int j = Partition(ref a, lo, hi); Sort(ref a, lo, j-1); Sort(ref a, j+1, hi); } public void Exch(ref int[] a,int i,int j) { int temp = a[j]; a[j] = a[i]; a[i] = temp; } public void Test() { int[] a = new int[5] { 3, 1, 2, 0, 1 }; Sort(ref a, 0, a.Length - 1); foreach (int i in a) Console.Write(i + " "); } } |
Hoar realization (What is Hoar?)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace QuickSortExample { class Program { static void Main(string[] args) { int[] a = { 3, 2, 5, 6 }; QuickSortHoar qsh = new QuickSortHoar(); qsh.Execute(ref a,0,a.Length-1); foreach (var val in a) Console.Write(val+" "); Console.Read(); } } class QuickSortHoar { void Swap(ref int i,ref int j) { int temp = i; i = j; j = temp; } public void Execute(ref int[] a, int lo, int hi) { int p = a[(hi - lo) / 2 + lo]; int i = lo, j = hi; while (i <= j) { while (a[i] < p && i <= hi) ++i; while (a[j] > p && j >= lo) --j; if (i <= j) { Swap(ref a[i],ref a[j]); ++i; --j; } } if (j > lo) Execute(ref a, lo, j); if (i < hi) Execute(ref a, i, hi); } } } |
Lomuto realization
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class QuickSort2 { void Swap(ref int i,ref int j) { int temp = i; i = j; j = temp; } // разделение массива по ключу key так, что левая часть - x <=key, правая часть - x > key private int Partition(int[] a, int lo, int hi) { int key = a[hi]; int i = lo - 1; for (int j = lo; j < hi; j++) { if (a[j] <= key) Swap(ref a[++i], ref a[j]); } Swap(ref a[++i], ref a[hi]); return i; } // сортировка public void Execute(int[] a, int lo, int hi) { if (lo < hi) { int key = Partition(a, lo, hi); Execute(a, lo, key - 1); Execute(a, key + 1, hi); } } } |
SomeNewRealization
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
static void QuickSort(int[] a, int lo, int hi) // Works! https://gist.github.com/lbsong/6833729 { if (lo >= hi) { return; } int num = a[lo]; /* Console.WriteLine("Before"); Console.WriteLine("pivot index = "+lo); Console.WriteLine("pivot value = " + a[lo]); foreach (int val in a) Console.Write(val+" "); Console.WriteLine(" "); */ int i = lo, j = hi; while (i < j) { while (i < j && a[j] >= num) { j--; } a[i] = a[j]; while (i < j && a[i] <= num) { i++; } a[j] = a[i]; } a[i] = num; /* Console.WriteLine("After"); Console.WriteLine("pivot index = " + lo); Console.WriteLine("pivot value = " + a[lo]); Console.WriteLine("i index = " + i); Console.WriteLine("j index = " + j); foreach (int val in a) Console.Write(val + " "); Console.WriteLine(" "); */ QuickSort(a, lo, i - 1); QuickSort(a, i + 1, hi); } |