c#でquicksort(クイックソート)
c#では初めて書いた。
quicksortをやるのは言語について調べるのにちょうどいい。
|
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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
using System; public class Hello { public static Random random = new System.Random (); public static void Main () { int[] a = new int[20]; dispArrayLine (a); setRandomForArray (a); dispArrayLine (a); quicksort (a); dispArrayLine (a); } public static void p (object o) { System.Console.WriteLine (o); } public static void p () { System.Console.WriteLine (); } public static void dispArrayList (int[] a) { foreach (int e in a) { p (e); } } public static void dispArrayLine (int[] a) { int len = a.Length; string s = ""; for (int i = 0; i < len; i++) { s += a[i]; if (i < len - 1) { s += " "; } } p (s); } public static int getRandomInt (int min = 0, int max = 10) { return random.Next (min, max); } public static void setRandomForArray (int[] a, int min = 0, int max = 10) { int len = a.Length; for (int i = 0; i < len; i++) { a[i] = getRandomInt (min, max); } } public static int getPivot (int a, int b, int c) { if (a > b) { if (b > c) { return b; } else { return a > c ? c : a; } } else { if (a > c) { return a; } else { return b > c ? c : b; } } } public static void swap (int[] a, int l, int r) { int t = a[l]; a[l] = a[r]; a[r] = t; } public static void quicksort (int[] a) { quicksortCore (a, 0, a.Length - 1); } public static void quicksortCore (int[] a, int left, int right) { if (left >= right) { return; } int l = left; int r = right; int p = getPivot (a[l], a[l + 1], a[r]); while (true) { while (a[l] < p) { l++; } while (p < a[r]) { r--; } if (l >= r) { break; } swap (a, l, r); l++; r--; } quicksortCore (a, left, l - 1); quicksortCore (a, r + 1, right); } } |
|
1 2 3 |
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 8 0 9 7 3 7 0 1 4 7 8 0 9 6 7 5 5 0 0 0 1 1 1 2 3 4 5 5 6 7 7 7 7 8 8 9 9 |
