Radix Sort in File C#

Viewed 209

This is an assignment from university. I have to do a Radix sort on car registration plates (ABC 123) in two ways 1) array 2) linked list. The most interesting thing is that sorting MUST BE done in the file. For example, from now on we will talk only about array. I generate car numbers and put them in array, then with binary write I write all generated car reg plates to the file. After that I give the newly generated file to Radix Sort and he need to do the magic. I will show you the code that I have at the moment, but it's not actually a 'real' radix sort, because my mind cannot understand how would I implement radix sort in file. ( I have implemented radix sort for normal array and linked list, but when it is done INSIDE a file it is mind blowing). I just wanted to ask if any of you would have any tips or ideas on how I could improve the sorting algorithm, because it is hella slow. Thank you.

PROGRAM.CS

public static void CountingSort(DataArray items, int exp)
{
    UTF8Encoding encoder = new UTF8Encoding();
    Byte[] forChange = new byte[16];
    double first, second;
    int i, j;
    NumberPlate plate1;
    NumberPlate plate2;
    for (int z = 0; z < items.Length; z++)
    {
        i = 0;
        j = 1;
        while (j < items.Length)
        {
            BitConverter.GetBytes(items[i]).CopyTo(forChange, 0);
            BitConverter.GetBytes(items[j]).CopyTo(forChange, 8);
            string firstPlate = encoder.GetString(forChange, 1, 7);
            string[] partsFirst = firstPlate.Split(' ');
            plate1 = new NumberPlate(partsFirst[0], partsFirst[1]);

            string secondPlate = encoder.GetString(forChange, 9, 7);
            string[] partsSecond = secondPlate.Split(' ');
            plate2 = new NumberPlate(partsSecond[0], partsSecond[1]);

            first = plate1.GetPlateCode() / exp % 10;
            second = plate2.GetPlateCode() / exp % 10;
            if (first > second)
            {
                items.Swap(j, BitConverter.ToDouble(forChange, 0), BitConverter.ToDouble(forChange, 8));
            }
            i++;
            j++;
        }
    }
}

public static void Radix_Sort(DataArray items)
{
    for (int exp = 1; exp < Math.Pow(10, 9); exp *= 10)
    {
        CountingSort(items, exp);
    }
}

public static void Test_File_Array_List(int seed)
{
    int n = 5;
    string filename;
    filename = @"mydataarray.txt";
    //filename = @"mydataarray.dat";
    MyFileArray myfilearray = new MyFileArray(filename, n);
    using (myfilearray.fs = new FileStream(filename, FileMode.Open, FileAccess.ReadWrite))
    {
        Console.WriteLine("\n FILE ARRAY \n");
        myfilearray.Print(n);
        Radix_Sort(myfilearray);
        myfilearray.Print(n);
    }
}

ARRAY.CS

public override double this[int index]
{
    get
    {
        Byte[] data = new Byte[8];
        fs.Seek(8 * index, SeekOrigin.Begin);
        fs.Read(data, 0, 8);
        double result = BitConverter.ToDouble(data, 0);
        return result;
    }
}
public override void Swap(int j, double a, double b)
{
    Byte[] data = new Byte[16];
    BitConverter.GetBytes(b).CopyTo(data, 0);
    BitConverter.GetBytes(a).CopyTo(data, 8);
    fs.Seek(8 * (j - 1), SeekOrigin.Begin);
    fs.Write(data, 0, 16);
}
1 Answers

If the assignment mentions array and linked list, then it would seem that the file is only used to read the data into the array or linked list, then then sort is done, and the result is written to a file.

For a file based radix sort, for each digit (right to left), 10 temp files are created, the data is read and appended to file "digit" based on the digit, then the 10 temp files are closed, then concatenated into a single working file for the next radix sort step. For each letter, 26 temp files would be used.

Related