Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
cz
0 / 0 / 0
Регистрация: 26.04.2016
Сообщений: 3
1

Задача по сортировке

26.04.2016, 10:24. Показов 2690. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте форумчане, перепала такая задача: Существует некоторый перечень карточек. Каждая карточка содержит в себе пункт отправления и пункт назначения. Гарантируется что если упорядочить эти карточки так чтобы для каждой карточки в упорядоченном списке пункт назначения на ней совпадал с пунктом отправления в следующей карточке в списке, получится один список карточек без циклов и пропусков. Необходимо написать функцию которая принимает набор неупорядоченных карточек и возвращает набор упорядоченных.
Накидал алгоритм, прошу ткнуть носом что и где криво, буду благодарен за ссылки, статьи, книги, названия алгоритмов итд.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Program
    {
 
        static void Main(string[] args)
        {
 
            var c1 = new Card() { From = "Moscow", To = "London" };
            var c2 = new Card() { From = "London", To = "Krakow" };
            var c3 = new Card() { From = "Krakow", To = "Vilnus" };
            var c4 = new Card() { From = "Vilnus", To = "Vankuver" };
 
            List<Card> list = new List<Card>() {c2, c3, c4, c1};
            Queue<Card> sorted = new Queue<Card>();
            
            foreach (var c in list)
            {
                if (String.IsInterned(c.From) == null) c.From = String.Intern(c.From);
                if (String.IsInterned(c.To) == null) c.To = String.Intern(c.To);
            }
 
            var toarr = list.Select(x => x.To);
            string start = list.Select(x => x.From).Except(toarr).Single();
 
            var firstCard = list.Single(x => String.ReferenceEquals(x.From, start));
            sorted.Enqueue(firstCard);
            
            string next = firstCard.To;
            list.Remove(firstCard);
 
            while (list.Count > 0)
            {
                var nextCard = list.Single(x => String.ReferenceEquals(x.From, next));
                sorted.Enqueue(nextCard);
                next = nextCard.To;
                list.Remove(nextCard);
            }
 
            Console.WriteLine("RESULT:");
            while (sorted.Count > 0)
            {
                var c = sorted.Dequeue();
                Console.WriteLine(String.Format("{0} -> {1}", c.From, c.To));
            }
                       
 
            Console.ReadKey();
        }
 
    }
 
 
    public class Card
    {
        public string From { get; set; }
        public string To { get; set; }
    }
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.04.2016, 10:24
Ответы с готовыми решениями:

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

Задача по быстрой сортировке
Здравствуйте, товарищи-программисты. Недавно столкнулся с задачей: Сортировка подсчетом ...

Задача по сортировке учащихся
Задача: Напишите функцию фильтрации студентов по средней оценке (так чтобы функция возвращала...

Задача по сортировке двумерного массива
Сортировка вставками. Дана последовательность чисел a1, a2, ..., an. Требуется переставить числа в...

6
1494 / 1209 / 821
Регистрация: 29.02.2016
Сообщений: 3,614
26.04.2016, 17:39 2
Задача о коммивояжере
Метод ветвей и границ: Нахождение минимального пути между городами
0
Эксперт .NET
17685 / 12871 / 3365
Регистрация: 17.09.2011
Сообщений: 21,136
26.04.2016, 18:50 3
Цитата Сообщение от afront Посмотреть сообщение
Задача о коммивояжере
Не, там просто топологическая сортировка.
0
1494 / 1209 / 821
Регистрация: 29.02.2016
Сообщений: 3,614
26.04.2016, 19:10 4
Ну тогда здесь можно найти рабочий пример
http://www.codeproject.com/Art... -Algorithm
1
cz
0 / 0 / 0
Регистрация: 26.04.2016
Сообщений: 3
27.04.2016, 09:29  [ТС] 5
Цитата Сообщение от afront Посмотреть сообщение
Ну тогда здесь можно найти рабочий пример
http://www.codeproject.com/Art... -Algorithm
интересное решение, но все же это не то. В моей задаче необходимно написать функцию сортировки которая отработает за конечное время, определить сложность алгоритма итд. В приведенной статье рассматривается алгоритм поиска оптимального пути, что по сути является вариацией решения задачи о коммивояжере с использованием генетического алгоритма.
0
Эксперт .NETАвтор FAQ
10410 / 5140 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
27.04.2016, 10:49 6
Лучший ответ Сообщение было отмечено cz как решение

Решение

Цитата Сообщение от cz Посмотреть сообщение
определить сложность алгоритма
Сложность у вас O(n^2).
Цитата Сообщение от cz Посмотреть сообщение
что и где криво
1) Вместо List<Card> list нужно использовать коллекцию другого типа, у которой удаление элемента проходит за O(1), например LinkedList или HashSet. У List<Card> удаление проходит за O(n), что существенно замедляет ваш алгоритм.
2) А вот вместо Queue<Card> sorted как раз нужно использовать List<Card>. Это не влияет на быстродействие, а просто семантически более верно, потому что вам очередь не нужна, вы просто формируете выходной список. А очередь нужна только тогда, когда вам нужно извлекать элементы из головы списка, но у вас этого нет.
3) Игр с интернацией строк я не очень понял. Вероятно вы так пытаетесь повысить быстродействие? Ну во-первых в вашем случае строки всегда и так будут интернированы, потому что они у вас вообще константы. Во-вторых, это как раз тот случай, когда преждевременная оптимизация вредна. На O() это не влияет, зато усложняет код.

Ну и в целом. Ваш алгоритм работает за O(n^2). Вы пробегаетесь по всему списку карточек (это O(n)) и затем для каджой ищите в списке следующую карточку (умножаем еще на O(n)).
Но можно же сделать и за O(n). Для этого сформируйте словарь вида Dictionary<string, Card>, который будет хранить карточки по начальному пункту (ключ в словаре). Тогда пробегаясь в цикле по карточкам, вы сразу найдете следующую карточку по словарю за O(1).
Формирование словаря занимает O(n), ваш цикл while займет O(n)*O(1). Т.о. общее быстродействие будет O(n) + O(n)*O(1) = O(n).
1
cz
0 / 0 / 0
Регистрация: 26.04.2016
Сообщений: 3
27.04.2016, 11:26  [ТС] 7
Цитата Сообщение от Storm23 Посмотреть сообщение
Сложность у вас O(n^2).

1) Вместо List<Card> list нужно использовать коллекцию другого типа, у которой удаление элемента проходит за O(1), например LinkedList или HashSet. У List<Card> удаление проходит за O(n), что существенно замедляет ваш алгоритм.
2) А вот вместо Queue<Card> sorted как раз нужно использовать List<Card>. Это не влияет на быстродействие, а просто семантически более верно, потому что вам очередь не нужна, вы просто формируете выходной список. А очередь нужна только тогда, когда вам нужно извлекать элементы из головы списка, но у вас этого нет.
3) Игр с интернацией строк я не очень понял. Вероятно вы так пытаетесь повысить быстродействие? Ну во-первых в вашем случае строки всегда и так будут интернированы, потому что они у вас вообще константы. Во-вторых, это как раз тот случай, когда преждевременная оптимизация вредна. На O() это не влияет, зато усложняет код.

Ну и в целом. Ваш алгоритм работает за O(n^2). Вы пробегаетесь по всему списку карточек (это O(n)) и затем для каджой ищите в списке следующую карточку (умножаем еще на O(n)).
Но можно же сделать и за O(n). Для этого сформируйте словарь вида Dictionary<string, Card>, который будет хранить карточки по начальному пункту (ключ в словаре). Тогда пробегаясь в цикле по карточкам, вы сразу найдете следующую карточку по словарю за O(1).
Формирование словаря занимает O(n), ваш цикл while займет O(n)*O(1). Т.о. общее быстродействие будет O(n) + O(n)*O(1) = O(n).


Добавлено через 9 минут
Цитата Сообщение от Storm23 Посмотреть сообщение
Сложность у вас O(n^2)........
огромное спасибо за коментарии.
не могли бы вы порекомендовать ресурс где можно почитать об оптимизации ? ну кроме МСДН)
Интренирование конечно в данном конкретном примере абсолютно бессмысленно.
еще раз спасибо
0
27.04.2016, 11:26
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.04.2016, 11:26
Помогаю со студенческими работами здесь

Задача по сортировке двумерного массива, найти ошибку
Задание: отсортировать двумерный массив порядка n на m Сортировка: Вставками. Пусть a1, a2, ...,...

Задача по сортировке диагоналей массивов методом вставок
Дана матрица n x n с целыми числами, отсортировать диагонали матрицы, расположенные выше главной,...

Ошибка в сортировке
Есть такая программа: using System; class Program { static void Main() { ...

Ошибки в сортировке
/*Èìååòñÿ òàáëèöà &quot;Àâòîìîáèëè&quot;. Êàæäàÿ ñòðîêà ñîäåðæèò ñëåäóþùåå ñâåäåíèÿ: ìàðêà, íîìåð, ôàìèëèÿ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru