Лексикографическая сортировка числовых векторов, BC++ Опции

[KerK]

Вектор А=(А1,А2,…,Аn) считается лексикографически большим вектора В=(В1,В2,…,Вn), если существует k>=0 такое что Аi=Вi(i<=k),Ak+1>Bk+1. Составить программу лексикографической сортировки числовых векторов. При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.

Давал пост в разделе задачи Лексикографическая сортировка числовых векторов., мне помогли с заданием но реализация была на паскале... вот попробовал перевести в сишку... возникли вопросы.... в сишке ни разу не пробовал процедуры... правильно ли я написал? и нет под рукой книги или хелпа, хотелось бы узнать что дает в паскале команда inc, и как она должна выглядеть в С. Потом не совсем понял какая структура должна быть у программы на С. НАпример на паскале

...
...
procedure
main();
end;
Begin
End.

а как на си?

И посмотрите пожалуйста мой код.... где какие ошибки? и как продолжить главный модуль программы?

#include <conio.h>
#include <iostream.h>
#include <math.h>


void SortAt(int low_bound,int up_bound,int sort_by)
main()
{
 int i,j,t;

 if (sort_by=len+1) exit; 

 for (i=1;i=up_bound-low_bound+1;i++)
 for (j=low_bound;j=up_bound-1;j++)
  if (vv[sorted[j]][sort_by]>vv[sorted[j+1]][sort_by])
  {
  t=sorted[j];
  sorted[j]=sorted[j+1];
  sorted[j+1]=t;
  }

  i=low_bound;
  while (i<=up_bound)
  {
   j=i;
   while (i<up_bound)&&(vv[sorted[j+1]][sort_by]=vv[sorted[j]][sort_by])
   inc(j); //???????????????????
   SortAt(i,j,sort_by+1);
   i=i+1;
  }
}

 int vv[3][3];
 int sorted[3]; 

[KerK]

Код

Вектор А=(А1,А2,…,Аn) считается лексикографически большим вектора В=(В1,В2,…,Вn), если существует k>=0 такое что Аi=Вi(i<=k),Ak+1>Bk+1. Составить программу лексикографической сортировки числовых векторов. При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.

Перечитал задание... i - это порядковый номер элемента, k - это элемент?
т.е. например
A) 1 2 3
B) 4 2 1

у А2 k=2, оно больше 0... и такое что A2=B2 и порядковый номер =2 (i<=k), а А3>B3... следовательно Вектор А считается лексиграфически большим вектора B.... так?

Т.е. цель задачи в том чтобы отсортировать вектор, так, чтобы он подходил к вышесказанному условию?

[Michael_Rybak]

Представь себе, что векторы - это слова, а элементы в векторах - буквы в словах. Твоя задача - отсортировать слова по алфавиту.

[KerK]

Представь себе, что векторы - это слова, а элементы в векторах - буквы в словах. Твоя задача - отсортировать слова по алфавиту.

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

Только остается вопрос:

Код

При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.

Каким макаром добиться этого условия?

[Michael_Rybak]

сортировка идет по первым элементам вектора, если они равны, то по второму элементу...

Код

При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.

Каким макаром добиться этого условия?

Честно говоря, я тебе уже ответил на этот вопрос в самом начале. Но давай ты все-таки сделаешь, чтоб работало, а потом уж возмешься за оптимизацию. Доделай мой шаблон, убедись, что всё "сходится", и вектора действительно сортируются, выложи результат сюда, и потом попробуй разобраться в том, что я тебе ответил в той теме. Там - и память минимальная, и время.

[KerK]

Честно говоря, я тебе уже ответил на этот вопрос в самом начале. Но давай ты все-таки сделаешь, чтоб работало, а потом уж возмешься за оптимизацию. Доделай мой шаблон, убедись, что всё "сходится", и вектора действительно сортируются, выложи результат сюда, и потом попробуй разобраться в том, что я тебе ответил в той теме. Там - и память минимальная, и время.

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <math.h>

const int MAX_N = 100;
const int MAX_LEN = 100;

int vv[MAX_N][MAX_LEN];
int n;
int len;
int temp;

int LexSmaller(int x, int y)
  //вернуть 1, если vv[x] лексикографичекси меньше, чем vv[y], и 0 в противном случае
{
  for (int i = 0; i < len; ++i)
  {
    if (vv[x][i]<vv[y][i])
      return 1; //лексикографически меньше
    else if (vv[x][i]>vv[y][i])
      return 0;   //если отличий не нашли, значит вектора равны или ; возвращаем 0
   cout<<i;
  }
	 return 0;
}

void Swap(int x, int y)
  //поменять местами векторы vv[x] и vv[y]
{
  //проходим по векторам и меняем попарно все элементы
  for (int i = 0; i < len; ++i)
  {
    //меняем местами vv[x][i] и vv[y][i]
    temp=vv[x][i];
    vv[x][i]=vv[y][i];
    vv[y][i]=temp;
  }
}

void ReadVectors()
{
  printf("Введите количество векторов: ");
  scanf("%d", &n);
  printf("Введите размерность (длину) векторов: ");
  scanf("%d", &len);

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < len; ++j)
    {
      printf("vv[%d][%d] = ", i, j);
      scanf("%d", &vv[i][j]);
    }
}

void BubbleSort()
  //сортировка пузырьком
{
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n - 1; ++j)
      if (LexSmaller(j + 1, j) == 1) //следующий вектор лекс. меньше текущего
        //меняем их местами
        Swap(j, j + 1);
}

void PrintResult()
{
  printf("Результат сортировки:");
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < len; ++j)
    {
      printf("vv[%d][%d] = ", i,j);
      cout<<vv[i][j]<<"\n";
    }

}


int main()
{
  ReadVectors();
  BubbleSort();
  PrintResult();
  return 0;
}

Например
9 5
1 1
2 3
9 1
6 5

результат:
1 1
2 3
6 5
9 1
9 5

[Michael_Rybak]

Молодец.

и потом попробуй разобраться в том, что я тебе ответил в той теме

Жду вопросов ;)

На всякий случай, на пальцах тот алгоритм. Переходим к аналогии сортировки слов. Что я делаю. Сначала сортирую слова по первой букве. Потом *отдельно* сортирую все слова, начинающиеся на А. Потом - на Б, на В и т.д. Как я *отдельно* сортирую все слова, начинающиеса на А? Я их сортирую по второй букве. Потом *отдельно* сортирую все слова, начинающиеся на АА, АБ, АВ и т.д. рекурсивно.

[KerK]

Молодец.
Жду вопросов ;)

На всякий случай, на пальцах тот алгоритм. Переходим к аналогии сортировки слов. Что я делаю. Сначала сортирую слова по первой букве. Потом *отдельно* сортирую все слова, начинающиеся на А. Потом - на Б, на В и т.д. Как я *отдельно* сортирую все слова, начинающиеса на А? Я их сортирую по второй букве. Потом *отдельно* сортирую все слова, начинающиеся на АА, АБ, АВ и т.д. рекурсивно.

#include <conio.h>
#include <iostream.h>
#include <math.h>
#include <stdio.h>

const int MAX_N = 100;
const int MAX_LEN = 100;
 int n,len;
 int vv[MAX_N][MAX_LEN];
 int sorted[MAX_N]; //сортируемый массив номеров векторов

//отсортировать группу от sorted[low_bound] до sorted[up_bound] по элементу sort_by
void SortAt(int low_bound,int up_bound,int sort_by)
{
 int i,j,t;

 if (sort_by==len+1) return; //сортировка по (len+1)му элементу -> процесс окончен
 //сортируем пузырьком

 for (i=0;i<=up_bound-low_bound+1;i++)
 for (j=low_bound;j<=up_bound-1;j++)
  if (vv[sorted[j]][sort_by]>vv[sorted[j+1]][sort_by])
  {
  //меняем вектора местами
  t=sorted[j];
  sorted[j]=sorted[j+1];
  sorted[j+1]=t;
  }

  //теперь выделяем группы и рекурсивно их сортируем
  i=low_bound;
  while (i<=up_bound)
  {
   j=i;
   while ((j<up_bound)&&(vv[sorted[j+1]][sort_by]==vv[sorted[j]][sort_by]))
   j=j+1;
  //у векторов от sorted[i] до sorted[j] совпадает элемент sort_by
   SortAt(i,j,sort_by+1);
   i = j + 1;
  }
}

void ReadVectors()
{
  printf("Введите количество векторов: ");
  scanf("%d", &n);
  printf("Введите размерность (длину) векторов: ");
  scanf("%d", &len);

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < len; ++j)
    {
      printf("vv[%d][%d] = ", i, j);
      scanf("%d", &vv[i][j]);
    }
}

void PrintResult()
{
  printf("Результат сортировки:");
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < len; ++j)
    {
      printf("vv[%d][%d] = ", i,j);
      cout<<vv[i][j]<<"\n";
    }
}

void main()
{
 ReadVectors();
  //изначальный порядок
 for (int i = 0; i < n; ++i)
 sorted[i] = i;
 SortAt(0, n, 0);
 PrintResult();
}

Проблема.... бесконечная процедура получается, потому что ретурн не срабатывает if (sort_by==len+1) return...когда выполняется это условие... он не может выйти с процедуры...

Может ретурн с каким-то параметром должен быть указан?

Сообщение отредактировано: KerK - 19.11.2006 23:59

[Michael_Rybak]

бесконечная процедура получается, потому что ретурн не срабатывает if (sort_by==len+1)

В паскале нумерация была с нуля, поэтому я написал "if sort_by = len + 1 then". В си нумерация с 0, поэтому замени на "if (sort_by==len)".

Кроме этого, посмотри на процедуру PrintResult. В ней ты выводишь вектора в том порядке, в котором они записаны в vv. А мы их в vv то не меняли местами, мы индексы перемещали в sorted[]. Поэтому теперь надо переделать PrintResult так, чтобы она выводила не сверху вниз, а по порядку, записанному в sorted. Давай.

Вроде будет работать нормально. Не забудь еще, что у нас внутри пузырек, который надо заменить быстрой сортировкой, так что возвращайся ;)

[KerK]

В паскале нумерация была с нуля, поэтому я написал "if sort_by = len + 1 then". В си нумерация с 0, поэтому замени на "if (sort_by==len)".

Кроме этого, посмотри на процедуру PrintResult. В ней ты выводишь вектора в том порядке, в котором они записаны в vv. А мы их в vv то не меняли местами, мы индексы перемещали в sorted[]. Поэтому теперь надо переделать PrintResult так, чтобы она выводила не сверху вниз, а по порядку, записанному в sorted. Давай.

Вроде будет работать нормально. Не забудь еще, что у нас внутри пузырек, который надо заменить быстрой сортировкой, так что возвращайся ;)

Все заработало как надо, Принтрезульт исправил. Чем заменить пузырек? Вставкой?

[Michael_Rybak]

Чем заменить пузырек? Вставкой?

Лучше std::sort'ом просто. Надо объявить компаратор, и передать его третьим параметром. Сможешь?

[KerK]

Лучше std::sort'ом просто. Надо объявить компаратор, и передать его третьим параметром. Сможешь?

неа ))) Первый раз слышу про компаратор )) ... да и помоему лучше не использовать STL... В задаче ничего не сказано... да и препод ничего такого не давал на лекциях...

[Michael_Rybak]

А помоему лучше использовать stl - это стандартная (уже) библиотека, не понимаю, зачем самому писать сортировку.

Показать как?

[Гость]

А помоему лучше использовать stl - это стандартная (уже) библиотека, не понимаю, зачем самому писать сортировку.

Показать как?

Конечно, если не использую, так хоть буду знать как использовать STL

[Michael_Rybak]

Сверху (перед функцией) объявляешь такой класс

struct CVectorComparator
{
  CVectorComparator(int i_sort_by)
    : sort_by(i_sort_by)
  {    
  }

  bool operator () (int i, int j)
  {
    return vv[i][sort_by] < vv[j][sort_by];
  }

  private: 
    int sort_by;  
};

Это класс-компаратор. Его единственный оператор () возвращает true, когда сортируемые объекты находятся в правильном порядке (т.е. когда i меньше j в нашем понимании). В нашей ситуации сортируемые объекты - это значения массива sorted, а условие, по которому мы определяем, в правильном ли порядке расположены два таких значения, получается точно таким же, как было в пузырьке: сравнение vv[i] и vv[j] по элементу sort_by.

Теперь вместо

 for (i=0;i<=up_bound-low_bound+1;i++)
 for (j=low_bound;j<=up_bound-1;j++)
  if (vv[sorted[j]][sort_by]>vv[sorted[j+1]][sort_by])
  {
  //меняем вектора местами
  t=sorted[j];
  sorted[j]=sorted[j+1];
  sorted[j+1]=t;
  }

Напиши

 std::sort(sorted + low_bound, sorted + up_bound + 1, CVectorComparator(sort_by));

sorted - массив, и одновременно sorted - это указатель на первый элемент массива. Поэтому sorted + low_bound - указатель на начало нашего отрезка, а sorted + up_bound + 1 - на следующий за концом (правый конец в stl обычно "не включительно", поэтому добавляем единицу). Если третьим параметром ничего не передать, sort отсортирует указанный кусок массива просто по возрастанию (используя обычный оператор <). А когда мы указываем ему компаратор, он выполняет сравнения не оператором <, а оператором () этого компаратора, т.е. делает то, что нам нужно.

Проверил, вроде работает.