Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: [Pascal] задача на строки(быстрая сортировка массива строк)  (Прочитано 46586 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Саша Бух
Гость
« : 11-12-2008 21:17 » 

С этой задачей в паскале я мурыжусь уже третий день Жаль вот, я как бы уже всё попробовал(или почти всё... Раньше она не проходила разные тесты, сейчас она не проходит по времени... я думаю, что это из-за неудобной медленной сортировки... Посмотрите и помогите мне плиззз Улыбаюсь

условие:

Одна из новых возможностей текстового редактора «World ХР» — это сортировка слов в предложении. Выход новой бета-версии редактора должен состоятся не позднее, чем через пять часов, а заявленная функция еще не реализована.
Требуется написать программу, осуществляющую сортировку слов в предложении. При этом все символы, отличные от букв, должны сохранится и не поменять своего положения относительно вхождений слов. Для упрощения при подаче входных данных на вход вашей программы все такие символы будут заменены на символ «.» (точка). Таким образом символ «.» имеет смысл разделителя между словами. Например, строка « . . aba. а. . Ьа» после сортировки пример вид « . . а. aba. . ba», а строка «с. . bb. а» примет вид «а. . bb. с». Слова следует сортировать лексикографически, как в словаре.

Формат ввода:

Входной файл содержит единственную строку, содержащую только прописные латинские буквы и символ «.». Слова могут разделяться любым количеством символов «.», строка может как начинаться так и заканчиваться последовательностью точек. Длина заданной строки не менее 1 символа и не превосходит 10^5 символов.
Формат вывода:

В выходной файл выведите строку после сортировки слов в ней.


Пример ввода:    Пример вывода:   

..aba.а..ba

..a.aba..ba


с.bb.а

a.bb.с

Моё решение:



Код:
var
  s,s1 : ansistring;
  t,buff,min: string;
  a,b,c      : array[1..100000] of string;
  i,j,d,n,k  : longint;
begin
  assign(input,'d.in'); reset(input);
  assign(output,'d.out'); rewrite(output);
  readln(s);
  d:=length(s);
  if s[1] = '.' then
  k:= 0
  else k:= 1;
      i:=1;k:=1;
for i:=1 to length(s) do begin
  if s[i]<>'.' then
  a[k]:=a[k]+s[i]
   else                      begin
   if i=length(s) then break;
   if (s[i]<>'.') and (s[i+1]='.') then break else
   if (s[i]='.') and (s[i+1]<>'.')then
   begin  inc(k);  end;           end;
            end;
    if (k = 0) or (k = 2) then writeln(s) else
  begin
 b:= a;
   for i:= 1 to k-1 do
    begin
      min:= a[i];
      n:= i;
      for j:= i+1 to k do
        if min > a[j] then
         begin
           min:= a[j];
           n:= j;
         end;
      buff:= a[i];
      a[i]:= a[n];
      a[n]:= buff;
    end;
     n:= 0;
  i:= 0;
   repeat
  inc(i);
  if s[i] = '.' then s1:=s1+s[i] else
   begin
     inc(n);
     s1:=s1+a[n];
     i:= i + length(b[n])-1;
   end;
  until  i >= length(s);
  end;
  d:=1;
  write(s1);
  Close(input);
  Close(output);
end.
Записан
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 11-12-2008 22:31 » new

Если побыстрее, то код какой-то трудночитаемый (да ещё и без комментов).
Поэтому - как бы стал делать я (не факт, что оптимальнее всего):
1. завёл бы массив счётчиков для точек: в i-том элементе - число точек перед i-тым словом (ну или саму строку с точками - как больше нравится).
2. прошёл бы строку, переписав счётчики в массив, а слова - в массив слов.
3. отсортировал массив слов быстрой сортировкой Хоара
4. вывел всё вместе (точки-слово-точки-слово), зная, сколько точек выводить перед каждым словом.
Записан
Саша Бух
Гость
« Ответ #2 : 11-12-2008 22:46 » 

ну по поводу кода-это да, наверное...
я делал почти также:
1)завёл массив исключительно для слов(без точек)
2)отсортировал этот массив
3)вывел точки на нужных позициях и слова также на соответственно нужных
но проблема, повторюсь, в сортировке-моя сортировка
 
Код:
for i:= 1 to k-1 do
    begin
      min:= a[i];
      n:= i;
      for j:= i+1 to k do
        if min > a[j] then
         begin
           min:= a[j];
           n:= j;
         end;
      buff:= a[i];
      a[i]:= a[n];
      a[n]:= buff;
    end;
слишком долгая и задача не проходит по времени....
подскажите быструю сортировку для массива слов(п.1)
Записан
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 11-12-2008 22:53 » 

да, это в общем случае будет медленно. Попробуй быструю сортировку Хоара - для паскаля там есть пример. Разница между целых чисел и для строк - только в реализации сравнения.

P.S. В TurboPascal, насколько мне помнится, в примерах есть её реализация - кажется, qsort.pas
« Последнее редактирование: 11-12-2008 22:57 от Вад » Записан
Саша Бух
Гость
« Ответ #4 : 11-12-2008 23:10 » 

спасибо за ссылку! честно говоря, я там чё-то пока не во всём разобрался, но буду думать....
а нельзя ли массив строк отсортировать подсчётом(черпаком)? эта ж сортировка тоже довольно быстрая и гораздо понятнее))) просто я не знаю, как и её сделать для строк в массиве....
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines