8 replies to this topic

[Galvin]

Hi Guys !

Im trying to compare the 3-Way Radix Quicksort with Mergesort. With Mergesort there's no problem in C# but I'm not able to finish / solve the 3-Way RadixQuicksort Code. I found something in the Net, but it is just in Java, and i cant handle Java :( and there is also no other Sourceexample for the RadixQuicksort. Now my Question : Did anybody have the Radixquicksort Code for C# or is anybody able to help me with the Translation ?

Here's the Java Code :
=============================================
// 3-way string quicksort a[lo..hi] starting at dth character
private static void sort(String[] a, int lo, int hi, int d) {


int lt = lo, gt = hi;
int v = charAt(a[lo], d);
int i = lo + 1;
while (i <= gt) {
int t = charAt(a[i], d);
if (t < v) exch(a, lt++, i++);
else if (t > v) exch(a, i, gt--);
else i++;
}

// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt-1, d);
if (v >= 0) sort(a, lt, gt, d+1);
sort(a, gt+1, hi, d);
}

// sort from a[lo] to a[hi], starting at the dth character
private static void insertion(String[] a, int lo, int hi, int d) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
exch(a, j, j-1);
}

// exchange a[i] and a[j]
private static void exch(String[] a, int i, int j) {
String temp = a[i];
a[i] = a[j];
a[j] = temp;
}

// is v less than w, starting at character d
private static boolean less(String v, String w, int d) {
assert v.substring(0, d).equals(w.substring(0, d));
return v.substring(d).compareTo(w.substring(d)) < 0;
}


// is the array sorted
private static boolean isSorted(String[] a) {
for (int i = 1; i < a.length; i++)
if (a[i].compareTo(a[i-1]) < 0) return false;
return true;
}


public static void main(String[] args) {

// read in the strings from standard input
String[] a = StdIn.readAll().split("\\s+");
int N = a.length;

// sort the strings
sort(a);

// print the results
for (int i = 0; i < N; i++)
StdOut.println(a[i]);
}
}

============================================

By the Way, I'm just using Int Values, so the strings can be exchanged with INT's.

It starts with : CharAT .... CharAT isnt a C# variable and I also dont "need" CharAT ... How to solve ? the primitive things like StdOut or In are no problems, Console.Writeln(a[i]) but the static boolean for example is also a problem which I dont get rid off ....

Can anybody Help me ?

Greetz Galvin !

[sam_coder]

static boolean can be replaced with static bool

Sorry, id respond to more than this, but just on my way out the door. I'll take a stab at it shortly

[Galvin]

mhh... correct, this works / gives no error ... :)

[sam_coder]

here is somewhat translated:

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using System.Text;


namespace _3wayRadixQuicksort {

    class Program {


        private static void sort(String[] a, int lo, int hi, int d) {

            int lt = lo, gt = hi;

            int v = charAt(a[lo], d);

            int i = lo + 1;

            while (i <= gt) {

                int t = charAt(a[i], d);

                if (t < v) exch(a, lt++, i++);

                else if (t > v) exch(a, i, gt--);

                else i++;

            }


            // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 

            sort(a, lo, lt - 1, d);

            if (v >= 0) sort(a, lt, gt, d + 1);

            sort(a, gt + 1, hi, d);

        }


        // sort from a[lo] to a[hi], starting at the dth character

        private static void insertion(String[] a, int lo, int hi, int d) {

            for (int i = lo; i <= hi; i++)

                for (int j = i; j > lo && less(a[j], a[j - 1], d); j--)

                    exch(a, j, j - 1);

        }


        // exchange a[i] and a[j]

        private static void exch(String[] a, int i, int j) {

            String temp = a[i];

            a[i] = a[j];

            a[j] = temp;

        }


        // is v less than w, starting at character d

        private static bool less(String v, String w, int d) {

            Debug.Assert(v.Substring(0, d).Equals(w.Substring(0, d)));

            return v.Substring(d).CompareTo(w.Substring(d)) < 0; 

        }



        // is the array sorted

        private static bool isSorted(String[] a) {

            for (int i = 1; i < a.Length; i++)

                if (a[i].CompareTo(a[i - 1]) < 0) return false;

            return true;

        }


        static void main(String[] args) {


            // read in the strings from standard input

            String[] a = Console.ReadLine().Split(new string[] { "\\s+" }, StringSplitOptions.None);

            int N = a.Length;


            // sort the strings

            sort(a);


            // print the results

            for (int i = 0; i < N; i++)

                Console.WriteLine(a[i]);

        }


    }

}

Sorry, running in and out, the wife's headin' in for surgery. (nothing serious, but its hard to sit down for more than a few seconds) =)

so, if someone else want's to work on that, great, if not, I'll see what I can do in a bit

Edited by sam_coder, 04 January 2011 - 04:37 AM.
just updated a few things in code

[Galvin]

Jeah ! Thanks a lot ! there are just 3 errors left ^_^ the CharAT problem, and an overloading problem for the sort-method (line 71, but i think I know the problem). In this evening i've also no time for fixing that. Tomorrow i'll work on that !

still don't know how to solve the CharAT :/ if you find a solution by accident, let me know ;)

Thank you very much ! Best wishes for your wife for the surgery ! Quite cool that you are helping me in this situation :thumbup1:

[sam_coder]

ok, so presumably, charAt(string, int) would return a character function,
this could likely be replicated like this

int v = charAt(a[lo], d);

turns into

int v = (int)s[lo][d];

That would turn this into this:

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using System.Text;


namespace _3wayRadixQuicksort {

    class Program {


        private static void sort(String[] a, int lo, int hi, int d) {

            int lt = lo, gt = hi;

            int v = (int)a[lo][d];

            int i = lo + 1;

            while (i <= gt) {

                int t = (int)a[i][d];

                if (t < v) exch(a, lt++, i++);

                else if (t > v) exch(a, i, gt--);

                else i++;

            }


            // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 

            sort(a, lo, lt - 1, d);

            if (v >= 0) sort(a, lt, gt, d + 1);

            sort(a, gt + 1, hi, d);

        }


        // sort from a[lo] to a[hi], starting at the dth character

        private static void insertion(String[] a, int lo, int hi, int d) {

            for (int i = lo; i <= hi; i++)

                for (int j = i; j > lo && less(a[j], a[j - 1], d); j--)

                    exch(a, j, j - 1);

        }


        // exchange a[i] and a[j]

        private static void exch(String[] a, int i, int j) {

            String temp = a[i];

            a[i] = a[j];

            a[j] = temp;

        }


        // is v less than w, starting at character d

        private static bool less(String v, String w, int d) {

            Debug.Assert(v.Substring(0, d).Equals(w.Substring(0, d)));

            return v.Substring(d).CompareTo(w.Substring(d)) < 0; 

        }



        // is the array sorted

        private static bool isSorted(String[] a) {

            for (int i = 1; i < a.Length; i++)

                if (a[i].CompareTo(a[i - 1]) < 0) return false;

            return true;

        }


        static void main(String[] args) {


            // read in the strings from standard input

            String[] a = Console.ReadLine().Split(new string[] { "\\s+" }, StringSplitOptions.None);

            int N = a.Length;


            // sort the strings

            sort(a);


            // print the results

            for (int i = 0; i < N; i++)

                Console.WriteLine(a[i]);

        }


    }

}

all you have to do is worry about the overload, which is easy to fix, if you know what to default the other parameters into

[sam_coder]

oh, and rename main(String[] args) to
Main(String[] args)

[sam_coder]

So I was looking at this now, as I have a change, and the main function, not sure what the initial part us supposed to do, some java guy may be able to translate the split, it might be a regex expression, in which case, the syntax would be different, but not too bad
I'll play with it, and if it seems to be that, I'll post the update

[sam_coder]

ok, not sure what exactly what main is looking for, if it IS regex, I suspect you could accomplish a similar feat like this (Making sure you add a using System.Text.RegularExpressions; to the top)

            Regex regex = new Regex("\\s+");

            List<string> collection = new List<string>();

            foreach (Match match in regex.Matches(Console.ReadLine()))

                collection.Add(match.Value);

            String[] a = collection.ToArray();