C# Как отсортировать символы вставкой?

Question

[BugHunter]

Как сортировать цифры - это понятно.
Но вот как быть с символами?

Есть две строки:

string input = "AAAABBBCCDDDHH";
string willbe = "AABCHHDACBDDAB";

Нужно input превратить в willbe, методом сортировки вставками либо деревом, и чтобы при большой длине строк сортировка выполнялась быстрее 5 секунд.
Строки всегда имеют одинаковую длину и каждый символ повторяется одинаковое кол-во раз в каждой строке.

Прошу помощи.

Comments

[Александр]

Как сортировать цифры - это понятно.
Но вот как быть с символами?

Точно так же.
https://dotnetfiddle.net/dVnezT

[BugHunter]

Александр, это немного не то, мне нужно чтобы после сортировки символов в input получить в итоге input == willbe.

[pestunov]

По какому принципу должна выполняться сортировка?
string willbe = "AABCHHDACBDDAB"; - это же неотсортированный массив.
Как можно отсортировать, чтобы получить неотсортированный массив?
Сформулируй точную постановку задачи.

[Александр Ананьев]

Строка input отсортирована, willbe - нет. Может строки местами поменять?

[BugHunter]

pestunov, Александр Ананьев, вот именно, такая задача, чтобы все символы имели новые позиции. То есть это уже немного иное.
Например чтобы было так 1 2 3 4 5 1 6 2 3 3 3 7 0
Когда есть 0 1 1 2 2 3 3 3 3 4 5 6 7.

Понимаете? нужно из одного слова собрать другое, переставляя символы.

[pestunov]

Egolds, тогда возьми и циклически сдвинь все символы на 1 позицию, тогда все символы будут иметь новые позиции. Например, abc123 -> 3abc12.

Из твоих постов постановка задачи неясна, в том числе, в каком смысле употребляются термины "отсортировать" и "вставка".

Как точно формулируется задача? Как сравнивать символы (если в алфавитном, то откуда получается такой результат)?

[BugHunter]

pestunov, сравнивать нужно с willbe

[eRKa]

Как сортировать цифры - это понятно.

А в чем отличие символа от цифры? Берешь код символа и сортируй как числа.

Answer 1

[VoidVolker]

1. Сопоставляем каждому символу во второй строке число-индекс этого символа;
   
2. По каждому символу в первой строке ищем тот же символ во второй строке и сопоставляем текущему символу число индекс второго символа;
   
3. Удаляем из второй строки найденный символ — т.е. символы повторяются нужно сопоставить символы один к одному;
   
4. Сортируем первую строку по номерам символов — при условии совпадения числа одинаковых символов в строках, результат будет соответствовать второй строке.
   

Comments

[BugHunter]

Спасибо за наводку, как я не додумался..)
Только мне была важна именно перемещение символа по слову, до нужной его позиции.

[VoidVolker]

Код скришотом? Непроизносимые названия переменных? О_о

[BugHunter]

VoidVolker, скриншот - это зашквар, скину позже нормальным видом, просто пост делал с телефона, а когда бежал на работу сделал скрин и скинул в облако.
По поводу названий они легко произносятся, просто это на польском языке)

[VoidVolker]

Да, мне тут рядом уже подсказали, что это польские варианты фамилия один и фамилия два. И подсказали смысл названия счетчика:

IloscPrzesuniec - это кстати ilość przesunięć (илошьчь пшесуньеньч) - количество перемещений

Общая рекомендация при разработке ПО — использовать только английские названия, а не транслитерацию родного языка. Во-первых английский — язык международный, во-вторых — почти все языки программирования используют английский язык как основной. В-третьих — смешение языков приводит к ухудшению таких качеств кода как читабельность, простота, сопровождаемость, а так же затрудняет дальнейшее профессиональное развитие разработчика, т.к. в дальнейшем надо будет все равно привыкать к правильному именованию и затруднит взаимодействие с другими разработчиками (например в команде или при работе над OpenSource кодом). Ну и такой код в резюме однозначно будет работать в минус к профессиональной оценке разработчика со стороны. Даже если он работает и в целом логика правильная.

[BugHunter]

var nazwisko = new List<char>();
            for (int n = 0; n < Nazwisko_Jeden.Length; n++)
            {
                nazwisko.Add(Nazwisko_Jeden[n]);
            }

            for (int i = 0; i < Dlugosc; i++)
            {
                int Litera_Id = nazwisko.IndexOf(Nazwisko_Dwa[i], i);
                char Litera = nazwisko[Litera_Id];

                while(i != Litera_Id && Litera_Id >= 0)
                {
                    Litera_Id--;
                    nazwisko[Litera_Id + 1] = nazwisko[Litera_Id];

                    IloscPrzesuniec++;
                }

                nazwisko[i] = Litera;
            }
            
            Nazwisko_Jeden = string.Join("", nazwisko);

            nazwisko.Clear();

Кстати, не знаете как можно ускорить работу данного кода? Важно именно перемещение по массиву/листу.

[VoidVolker]

Переписать на ассемблер.