F#/Algorithm/XNA/OData/and more…

playing around with different sorting algorithms with closure (lawl…) (next stop: Burst Trie)

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             TestBenchLoader(bubble_sort);
  6:             TestBenchLoader(selection_sort);
  7:             TestBenchLoader(insertion_sort);
  8:             TestBenchLoader(binary_tree_sort);
  9:             TestBenchLoader(quick_sort);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         static void TestBenchLoader(Action<int[]> test_method)
 16:         {
 17:             var test = new int[] { 3, 7, 2, 1, 4, 1, 2, 5, 11, 90, 102, 77 };
 18:             var expected = test.OrderBy(l => l).ToArray();
 19: 
 20:             test_method(test);
 21: 
 22:             var correct = expected.SequenceEqual(test);
 23:             Console.WriteLine(string.Format("is {0, -18} implementation correct: {1}", test_method.Method.Name, correct));
 24:         }
 25: 
 26:         static void bubble_sort(int[] list)
 27:         {
 28:             var len = list.Length;
 29:             var temp = 0;
 30:             var swapped = false;
 31:             for (int i = 0; i < len; i++)
 32:             {
 33:                 swapped = false;
 34:                 for (int j = len - 1; j > i; j--)
 35:                 {
 36:                     if (list[j] < list[j - 1])
 37:                     {
 38:                         temp = list[j];
 39:                         list[j] = list[j - 1];
 40:                         list[j - 1] = temp;
 41:                         swapped = true;
 42:                     }
 43:                 }
 44:                 if (swapped == false)
 45:                     break;
 46:             }
 47:         }
 48: 
 49:         static void selection_sort(int[] list)
 50:         {
 51:             var len = list.Length;
 52:             var temp = 0;
 53:             var index = 0;
 54:             for (int i = 0; i < len; i++)
 55:             {
 56:                 index = i;
 57:                 for (int j = i + 1; j < len; j++)
 58:                 {
 59:                     if (list[j] < list[index])
 60:                         index = j;
 61:                 }
 62:                 if (index != i)
 63:                 {
 64:                     temp = list[i];
 65:                     list[i] = list[index];
 66:                     list[index] = temp;
 67:                 }
 68:             }
 69:         }
 70: 
 71:         static void insertion_sort(int[] list)
 72:         {
 73:             var len = list.Length;
 74:             var value = 0;
 75:             var j = 0;
 76:             for (int i = 0; i < len; i++)
 77:             {
 78:                 value = list[i];
 79:                 j = i;
 80:                 while (j > 0 && list[j - 1] > value)
 81:                 {
 82:                     list[j] = list[j - 1];
 83:                     j--;
 84:                 }
 85:                 list[j] = value;
 86:             }
 87:         }
 88: 
 89:         [DebuggerDisplay("{value}")]
 90:         class Node
 91:         {
 92:             public int value;
 93:             public Node left;
 94:             public Node right;
 95:             public Node() { }
 96:             public Node(int v) { value = v; }
 97:         }
 98: 
 99:         static void binary_tree_sort(int[] list)
100:         {
101:             Func<int[], Node> create_tree = null;
102:             create_tree = v =>
103:                 {
104:                     var root = new Node(v[0]);
105:                     Action<Node> insert_node = null;
106:                     insert_node = n =>
107:                         {
108:                             var cur = root;
109:                             while (true)
110:                             {
111:                                 if (n.value < cur.value)
112:                                 {
113:                                     if (cur.left == null)
114:                                     {
115:                                         cur.left = n;
116:                                         return;
117:                                     }
118:                                     cur = cur.left;
119:                                 }
120:                                 else
121:                                 {
122:                                     if (cur.right == null)
123:                                     {
124:                                         cur.right = n;
125:                                         return;
126:                                     }
127:                                     cur = cur.right;
128:                                 }
129:                             }
130:                         };
131:                     for (int i = 1; i < v.Length; i++)
132:                     {
133:                         insert_node(new Node(v[i]));
134:                     }
135:                     return root;
136:                 };
137: 
138:             Action<Node> traverse = null;
139:             var index = 0;
140:             traverse = n =>
141:                 {
142:                     if (n == null)
143:                         return;
144:                     traverse(n.left);
145:                     list[index++] = n.value;
146:                     traverse(n.right);
147:                 };
148:             var tree = create_tree(list);
149:             traverse(tree);
150:         }
151: 
152:         static void quick_sort(int[] list)
153:         {
154:             Action<int[], int, int> swap = null;
155:             swap = (v, a, b) =>
156:                 {
157:                     var tmp = v[a];
158:                     v[a] = v[b];
159:                     v[b] = tmp;
160:                 };
161: 
162:             Action<int[], int, int> qsort = null;
163:             qsort = (v, left, right) =>
164:                 {
165:                     int i, last;
166: 
167:                     if (left >= right)
168:                         return;
169:                     swap(v, left, left + (right - left) / 2);
170:                     last = left;
171:                     for (i = left + 1; i <= right; i++)
172:                     {
173:                         if (v[i] < v[left])
174:                             swap(v, ++last, i);
175:                     }
176: 
177:                     swap(v, left, last);
178:                     qsort(v, left, last - 1);
179:                     qsort(v, last + 1, right);
180:                 };
181:             qsort(list, 0, list.Length - 1);
182:         }
183:     }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s