Алгоритм сортировки С++

Спасибо, что рассмотрели этот вопрос заранее.

Я пытаюсь заказать следующий список предметов:

Bpgvjdfj,Bvfbyfzc
Zjmvxouu,Fsmotsaa
Xocbwmnd,Fcdlnmhb
Fsmotsaa,Zexyegma
Bvfbyfzc,Qkignteu
Uysmwjdb,Wzujllbk
Fwhbryyz,Byoifnrp
Klqljfrk,Bpgvjdfj
Qkignteu,Wgqtalnh
Wgqtalnh,Coyuhnbx
Sgtgyldw,Fwhbryyz
Coyuhnbx,Zjmvxouu
Zvjxfwkx,Sgtgyldw
Czeagvnj,Uysmwjdb
Oljgjisa,Dffkuztu
Zexyegma,Zvjxfwkx
Fcdlnmhb,Klqljfrk
Wzujllbk,Oljgjisa
Byoifnrp,Czeagvnj

В следующем порядке:

Bpgvjdfj
Bvfbyfzc
Qkignteu
Wgqtalnh
Coyuhnbx
Zjmvxouu
Fsmotsaa
Zexyegma
Zvjxfwkx
Sgtgyldw
Fwhbryyz
Byoifnrp
Czeagvnj
Uysmwjdb
Wzujllbk
Oljgjisa
Dffkuztu

Это делается:

  1. Берем первую пару и помещаем имена в список
  2. Используя второе имя пары, найдите пару, в которой оно используется в качестве первого имени.
  3. Добавьте второе имя этой пары в список
  4. Повторите 2 и 3

Я заполняю unordered_map парами, затем сортирую и добавляю каждое имя в список. Это можно увидеть в следующем коде:

westIter = westMap.begin();
std::string westCurrent = westIter->second;
westList.push_front(westCurrent);

for(int i = 0; i < 30; i++)
{
    if(westMap.find(westCurrent) != westMap.end())
    {
        //find pair in map where first iterator is equal to "westCurrent"
        //append second iterator of pair to list
    }
    westIter++;
}

Примечание. Я не уверен, что «push_front» правильный в данный момент времени, так как я вставил только первое значение.

Мой вопрос: может ли кто-нибудь дать мне некоторое представление о том, как я могу это сделать? Поскольку я не уверен, как лучше и правильно ли мое мышление. Любое понимание будет оценено.


person wilcode    schedule 29.01.2013    source источник
comment
Три миллиона мужчин с разными именами были проложены встык, простираясь от Нью-Йорка до Калифорнии. Каждому участнику давали листок бумаги, на котором он записывал свое имя и имя человека, стоявшего в очереди непосредственно к западу от него. Человек на крайнем западном конце линии не понял, что делать, поэтому выбросил газету; остальные 2 999 999 листков бумаги были сложены в огромную корзину и доставлены в Национальный архив в Вашингтоне, округ Колумбия. Здесь содержимое корзины было полностью перемешано и перенесено на магнитные ленты. unordered_map перемешивает пары.   -  person wilcode    schedule 29.01.2013
comment
Вы пытаетесь отсортировать unordered_map???   -  person Karthik T    schedule 29.01.2013
comment
@KarthikT Имена вставляются из файла в unordered_map для их перемешивания, а затем упорядочиваются в список.   -  person wilcode    schedule 29.01.2013
comment
Вам нужно восстановить порядок 2 999 999 имен? Сортировка - плохое имя для этого, но я думаю, что понимаю   -  person Karthik T    schedule 29.01.2013
comment
@KarthikT Да, другой раздел моего кода делает обратное.   -  person wilcode    schedule 29.01.2013
comment
Относительно тегов: почему «knuth»?   -  person jogojapan    schedule 29.01.2013
comment
@jogojapan Со ссылкой на его описание проблема сортировки при упорядочении ключей не очевидна. Комментарий, который я разместил выше, является его воспроизведением.   -  person wilcode    schedule 29.01.2013
comment
Ой. Дональд Кнут описал эту проблему. Хм. Я думаю, что лучше поставить цитату и его имя в самом вопросе, чем использовать тег. Не уверен, для чего этот тег должен использоваться в любом случае (возможно, алгоритм Кнута?)   -  person jogojapan    schedule 29.01.2013
comment
ИМО, думать об этом как о сортировке - ошибка. На самом деле у вас есть реляционный связанный список, то есть связанный список, но вместо каждого узла, содержащего указатель на следующий узел, поле указателя содержит значение следующего узла. В качестве альтернативы вы можете думать об этом как о (своего рода) топологическом виде.   -  person Jerry Coffin    schedule 29.01.2013


Ответы (2)


В вашем плане есть только один недостаток. Сначала вам нужно найти первого человека в цепочке, мистера Нью-Йорка.

Ваш алгоритм предполагает, что очередь начинается с первого парня. Чтобы это сработало, вы должны сначала просмотреть всю карту, чтобы найти одно имя, которое не отображается как второй элемент. Это мистер Нью-Йорк, и вы можете продолжить оттуда. push_back это то, что вам нужно использовать здесь.

person Karthik T    schedule 29.01.2013
comment
Отредактировал комментарий сейчас, но да, я сделал это неправильно! Ну это пролило свет на ситуацию.. - person wilcode; 29.01.2013
comment
Да, это тот. Итак, одно сканирование, чтобы найти первое, и второе, чтобы создать список - person Karthik T; 29.01.2013
comment
Вы хотите сказать, что первым должен быть Xocbwmnd, потом от его второго имени, ищите оттуда. Вот почему мой отсортированный список получился короче, чем должен был. - person wilcode; 29.01.2013
comment
@ lauw0203 да, именно то, что я имею в виду. - person Karthik T; 29.01.2013
comment
Я только что разговаривал с кем-то, кто тоже этим занимается, и они сказали, что, поскольку вы идете на восток и на запад, все значения будут собраны в списке, так что вы можете начать с самого начала. - person wilcode; 29.01.2013
comment
@lauw0203 начало карты? Я не понимаю, как это будет работать, если вы 1) не сделаете несколько проходов, 2) не соедините несколько списков вместе или 3) не пойдете назад. - person Karthik T; 29.01.2013
comment
Вы просматриваете западную карту и добавляете в список, а затем восточную карту и добавляете недостающие значения, по-видимому. - person wilcode; 29.01.2013
comment
давайте продолжим это обсуждение в чате - person Karthik T; 29.01.2013

  1. Создайте структуру данных, которая хранит цепочку, ее начало и конец. Хранить в хеш-таблице с ключом «назад».
  2. Создайте кучу одноэлементных цепочек (по одной на каждый элемент)
  3. Итеративно выберите цепочку, найдите ее «переднюю часть» в хеш-таблице (т.е. найдите другую цепочку, которая имеет тот же элемент, что и «задняя часть»), и объедините их.
  4. Делайте это, пока у вас не останется только одна цепь
person ElKamina    schedule 29.01.2013