3 way radix quick sort code example

Example 1: 3-way radix quicksort java

static void StrSort(String a[], int l, int r, int d)  {    if (r <= l) return;    String v = a[r];    int i = l-1, j = r, p = l-1, q = r, k;    while (i < j)      {        while (less(a[++i], v, d)) ;        while (less(v, a[--j], d)) if (j == l) break;        if (i > j) break;        exch(a, i, j);        if (equal(a[i], v, d)) exch(a, ++p, i);        if (equal(v, a[j], d)) exch(a, --q, j);      }    if (p == q)  // first d+1 chars of all keys equal      if (v.length() > d) StrSort(a, l, r, d+1);    if (p == q) return;    if (less(a[i], v, d)) i++;    for (k = l; k <= p; k++, j--) exch(a, k, j);    for (k = r; k >= q; k--, i++) exch(a, k, i);    StrSort(a, l, j, d);    if ((i == r) && (equal(a[i], v, d))) i++;    if (v.length() >= d) StrSort(a, j+1, i-1, d+1);    StrSort(a, i, r, d);  }

Example 2: 3-way radix quicksort java

static boolean less(String s, String t, int d)    {      if (t.length() <= d) return false;      if (s.length() <= d) return true;      return s.charAt(d) < t.charAt(d);    }  static boolean equal(String s, String t, int d)    { return !less(s, t, d) && !less(t, s, d); }

Tags:

Java Example