12,691,051 members (32,643 online)

47.4K views
46 bookmarked
Posted

# Fast List<String> Sort in C#

, 23 Aug 2012 CPOL
How to get faster sorting in List(T) string collections
 SortTests Properties Sorting SortTests.csproj.user SortTests.xls ```﻿namespace Sorting.SedgewickSort { public static class Sedgewick { static char CharOrNull(string s, int pos) { if (pos >= s.Length) return (char)0; return s[pos]; } static int medianOf3(string[] x, int a, int b, int c, int depth) { char va, vb, vc; if ((va = CharOrNull(x[a], depth)) == (vb = CharOrNull(x[b], depth))) return a; if ((vc = CharOrNull(x[c], depth)) == va || vc == vb) return c; return va < vb ? (vb < vc ? b : (va < vc ? c : a)) : (vb > vc ? b : (va < vc ? a : c)); } //Pathological case is: strings with long common prefixes will // cause long running times public static void InsertionSort(string[] x, int a, int n, int depth) { int pi; int pj; for (pi = a + 1; --n > 0; pi++) { for (pj = pi; pj > a; pj--) { string s = x[pj - 1]; string t = x[pj]; int d = depth; int s_len = s.Length; int t_len = t.Length; while (d < s_len && d < t_len && s[d] == t[d]) { d++; }; if (d == s_len || (d < t_len && s[d] <= t[d])) break; int pj1 = pj - 1; string tmp = x[pj]; x[pj] = x[pj1]; x[pj1] = tmp; } } } static void vecswap(string[] x, int a, int b, long n) { while (n-- > 0) { string t = x[a]; x[a++] = x[b]; x[b++] = t; } } public static string[] Sort(string[] input) { string[] copy = new string[input.Length]; input.CopyTo(copy, 0); InPlaceSort(copy, 0, copy.Length, 0); return copy; } public static void Sort(ref string[] inout) { InPlaceSort(inout, 0, inout.Length, 0); } static void InPlaceSort(string[] x, int a, int n, int depth) { char partval; int d, r; int pa; int pb; int pc; int pd; int pl; int pm; int pn; string t; if (n < 10) { InsertionSort(x, a, n, depth); return; } pl = a; //pm = a + (n / 2); pm = a + (n >> 1); pn = a + (n - 1); if (n > 30) { // On big arrays, pseudomedian of 9 //d = (n / 8); d = (n >> 3); pl = medianOf3(x, pl, pl + d, pl + 2 * d, depth); pm = medianOf3(x, pm - d, pm, pm + d, depth); pn = medianOf3(x, pn - 2 * d, pn - d, pn, depth); } pm = medianOf3(x, pl, pm, pn, depth); { t = x[a]; x[a] = x[pm]; x[pm] = t; } pa = pb = a + 1; pc = pd = a + n - 1; partval = CharOrNull(x[a], depth); int len = x[a].Length; bool empty = (len == depth); for (; ; ) { while (pb <= pc && (r = (empty ? (x[pb].Length - depth) : ((depth == x[pb].Length) ? -1 : (x[pb][depth] - partval)))) <= 0) { if (r == 0) { //swap(pa, pb); { t = x[pa]; x[pa] = x[pb]; x[pb] = t; } pa++; } pb++; } while (pb <= pc && (r = (empty ? (x[pc].Length - depth) : ((depth == x[pc].Length) ? -1 : (x[pc][depth] - partval)))) >= 0) { if (r == 0) { //swap(pc, pd); { t = x[pc]; x[pc] = x[pd]; x[pd] = t; } pd--; } pc--; } if (pb > pc) break; //swap(pb, pc); { t = x[pb]; x[pb] = x[pc]; x[pc] = t; } pb++; pc--; } pn = a + n; if (pa - a < pb - pa) { r = (pa - a); } else { r = (pb - pa); } //swapping pointers to strings vecswap(x, a, pb - r, r); if (pd - pc < pn - pd - 1) { r = pd - pc; } else { r = pn - pd - 1; } vecswap(x, pb, pn - r, r); r = pb - pa; if (pa - a + pn - pd - 1 > 1 && x[a + r].Length > depth) //by definition x[a + r] has at least one element InPlaceSort(x, a + r, pa - a + pn - pd - 1, depth + 1); if (r > 1) InPlaceSort(x, a, r, depth); if ((r = pd - pc) > 1) InPlaceSort(x, a + n - r, r, depth); } } } ```

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.