Algoritmy a dátové štruktúry II – Teoretická zápočtová práca

Súčasťou procesu získania zápočtu z Algoritmov a dátových štruktúr II (ADS) je aj teoretická zápočtová práca. A práve o tej pojednáva tento článok.

 

Teoretické zápočtové práce z ADS sa zväčša vyberajú zo zoznamu pána doktora Mareša. V ponuke sú približne tri desiatky rôznych algoritmických problémov rozdelené do niekoľkých kategórií podľa toho, do akých tematických celkov patria.

 

Ja som si vybral problém priehradkového triedenia reťazcov v lineárnom čase. Ide o relatívne jednoduchý problém, ktorého riešenie je vlastne postavené ešte na prednáške ADS I.

 

Samotný problém by sa dal formulovať asi takto: majme množinu reťazcov rôznej dĺžky. Úlohou je usporiadať tieto reťazce podľa abecedného poradia v čase lineárnom s dĺžkou vstupu (dĺžka vstupu = súčet dĺžok všetkých slov). Pri riešení tohto zadania vyvstáva niekoľko problémov, z ktorých asi najväčší je udržať zložitosť algoritmu na lineárnej úrovni. Ďalší problém predstavujú napríklad opakujúce sa slová a podobne.

 

No, stačilo už teórie, tu je samotné riešenie problému v jazyku C#:

using System;
using System.Collections.Generic;
using System.Text;

namespace BucketSort
{
    class Program
    {
        static void Main(string[] args)
        {
            string input = Console.In.ReadLine();
            string[] pole = input.Split(' ');
            List<String> strings = new List<string>();
            foreach (string s in pole)
                strings.Add(s);
            foreach (string s in BucketSort(strings))
            {
                Console.Write(s + " ");
            }
            Console.ReadLine();
        }

        static List<string> BucketSort(List<string> InputStringArray)
        {
            string[] result=new string[InputStringArray.Count];
            List<string> Dvojice = new List<string>();
            int CurLength = 0;
            foreach (string s in InputStringArray)
            {
                for (int j = 0; j <= s.Length-1; j++)
                {
                    Dvojice.Add(j.ToString() + s[j]);
                    if (j > CurLength) CurLength = j;
                }
            }
            int MaLength = CurLength;
            Dvojice = BSortStr(Dvojice);
            List<string>[] Chars = BSortI(Dvojice, CurLength);
            InputStringArray=BSortLength(InputStringArray, CurLength);

            while (CurLength >= 0)
            {
                int MovedToFront = 0;
                while ( MovedToFront<InputStringArray.Count  && InputStringArray[InputStringArray.Count - 1].Length - 1 == CurLength)
                {
                    InputStringArray.Insert(0, InputStringArray[InputStringArray.Count - 1]);
                    InputStringArray.RemoveAt(InputStringArray.Count - 1);
                    MovedToFront++;
                }

                List<string>[] vedra = new List<string>[256];
                int CurrentString = 0;

                while (CurrentString < InputStringArray.Count &&  InputStringArray[CurrentString].Length - 1 >= CurLength)
                {
                    if (vedra[(int)(InputStringArray[CurrentString][CurLength])] == null) vedra[(int)(InputStringArray[CurrentString][CurLength])] = new List<string>();
                    vedra[(int)(InputStringArray[CurrentString][CurLength])].Add(InputStringArray[CurrentString]);
                    CurrentString++;
                }

                int NewIndex = 0;

                foreach (string s in Chars[CurLength])
                {
                    string temp = vedra[s[0]][0];
                    int OldIndex = InputStringArray.LastIndexOf(vedra[s[0]][0]);
                    InputStringArray.RemoveAt(OldIndex);
                    InputStringArray.Insert(NewIndex, temp);
                    NewIndex++;
                    vedra[s[0]].RemoveAt(0);
                }

                CurLength--;
            }

            int MovedBlanks = 0;
            while (MovedBlanks < InputStringArray.Count && InputStringArray[InputStringArray.Count - 1].Length  == 0)
            {
                InputStringArray.Insert(0, InputStringArray[InputStringArray.Count - 1]);
                InputStringArray.RemoveAt(InputStringArray.Count - 1);
                MovedBlanks++;
            }
            return InputStringArray;
        }

        static List<string> BSortStr(List<String> vstup)
        {
            List<string>[] vedra = new List<string>[256];
            foreach (string s in vstup)
            {
                if (vedra[(int)s[1]] == null) vedra[(int)s[1]] = new List<string>();
                vedra[(int)s[1]].Add(s);
            }
            List<string> result = new List<string>();
            for (int i = 0; i <= 255; i++)
            {
                if (vedra[i] != null && vedra[i].Count > 0)
                {
                    foreach (string s in vedra[i])
                    {
                        result.Add(s);
                    }
                }
            }
            return result;
        }

        static List<string>[] BSortI(List<string> vstup, int max)
        {

            List<string>[] vedra = new List<string>[max+1];
            foreach (string s in vstup)
            {
                if (vedra[int.Parse(s.Substring(0, s.Length - 1))] == null) vedra[int.Parse(s.Substring(0, s.Length - 1))] = new List<string>();
                vedra[int.Parse(s.Substring(0, s.Length - 1))].Add(s.Substring(s.Length - 1));
            }

            return vedra;
        }

        static List<string> BSortLength(List<string> vstup,int max)
        {
            List<string>[] vedra = new List<string>[max+2];
            foreach (string s in vstup)
            {
                if (vedra[s.Length] == null) vedra[s.Length] = new List<string>();
                vedra[s.Length].Add(s);
            }
            List<string> result = new List<string>();
            for (int i = 0; i <= max +1; i++)
            {
                if (vedra[i] != null && vedra[i].Count > 0)
                {
                    foreach (string s in vedra[i])
                    {
                        result.Add(s);
                    }
                }
            }
            return result;
        }
    }
}

 

Celý projekt (vrátane dokumentácie, ktorá je nutnou súčasťou riešenia) si môžete stiahnuť na mojom Live SkyDrive.

 

Dúfam, že toto moje riešenie niekomu príde vhod. A keď nie, nuž, smola. 🙂

Reklamy

Pridaj komentár

Zadajte svoje údaje, alebo kliknite na ikonu pre prihlásenie:

WordPress.com Logo

Na komentovanie používate váš WordPress.com účet. Odhlásiť sa / Zmeniť )

Twitter picture

Na komentovanie používate váš Twitter účet. Odhlásiť sa / Zmeniť )

Facebook photo

Na komentovanie používate váš Facebook účet. Odhlásiť sa / Zmeniť )

Google+ photo

Na komentovanie používate váš Google+ účet. Odhlásiť sa / Zmeniť )

Connecting to %s