Thuật toán sắp xếp nhanh (Quicksort-Demo Code)

1. using System;
3. namespace P04_QuickSort
4. {
5. class Program
6. {
7. static void Main(string[] args)
8. {
9. Console.Title = "Quick Sort";
11. var numbers = new[] { -11, 12, -42, 0, 1, 90, 68, 6, -9 };
12. Console.WriteLine("Original");
13. Print(numbers);
15. Sort(numbers);
17. Console.WriteLine("Sorted:");
18. Print(numbers);
20. Console.ReadKey();
21. }
23. static void Swap<T>(T[] array, int i, int m)
24. {
25. T temp = array[i];
26. array[i] = array[m];
27. array[m] = temp;
28. }
30. static void Print<T>(T[] array)
31. {
32. Console.WriteLine(string.Join("\t", array));
33. }
35. static int Partition<T>(T[] array, int lower, int upper) where T : IComparable
36. {
37. var i = lower;
38. var j = upper;
39. T pivot = array[lower];
40. do
41. {
42. while (array[i].CompareTo(pivot) < 0) i++;
43. while (array[j].CompareTo(pivot) > 0) j--;
44. if (i >= j) break;
45. Swap(array, i, j);
46. } while (i <= j);
47. return j;
48. }
50. static void SubSort<T>(T[] array, int lower, int upper) where T : IComparable
51. {
52. if (lower < upper)
53. {
54. var p = Partition(array, lower, upper);
55. SubSort(array, lower, p);
56. SubSort(array, p + 1, upper);
57. }
58. }
60. static void Sort<T>(T[] array) where T : IComparable
61. {
62. SubSort(array, 0, array.Length - 1);
63. }
64. }
65. }