IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Лексикографическая сортировка числовых векторов, BC++
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Вектор А=(А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];








 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Если тебе на сях надо было, ты б так и говорил, я б на сях и пример приводил.

Ну че, давай по порядку. main() - это стандартное для си название главной функции программы. Такая функция всегда есть, и всегда одна. Например:

На паскале

program a_plus_b;

var a, b: integer;
z: array [1..5, 1..10] of integer; //просто для примера

function CalculateSum(a, b: integer): integer;
var s: integer;
begin
s := a + b;
CalculateSum := s;
end;

procedure PrintResult(a, b, s: integer);
begin
Writeln(a, ' + ', b, ' = ', s);
end;

begin
Readln(a, b);
PrintResult(a, b, CalculateSum(a, b));
end.



На си:


#include "stdio.h"

int a, b;
int z[5][10]; //просто для примера

int CalculateSum(int a, int b) //тип возвращаемого значения указываем *перед* именем функции
{
int s;
s = a + b;
return s; //вместо CalculateSum := s просто делаем return s
}

void PrintResult(int a, int b, int s) //процедуры объявляются с ключевым словом void вместо типа
{
printf("%d + %d = %d\n", a, b, s);
}

int main() //вместо главной пары begin-end объявляем функцию main
{
scanf("%d %d", &a, &b);
PrintResult(a, b, CalculateSum(a, b));
return 0;//возвращаем 0, означающий, что программа нормально завершила работу
}



Очень внимательно изучи это код на предмет оформления и вызова процедур, да и общей структуры программы.

Теперь, что касается перевода.

1. Перенеси объявление массивов vv и sorted наверх, иначе из тела функции их не будет видно

2. Строку main() убери, и объяви функцию main отдельно, как я показал в примере выше.

3. Во всех проверках "=" записывается в си как "==". Здесь:

if (sort_by=len+1) exit;  


и здесь:

vv[sorted[j+1]][sort_by]=vv[sorted[j]][sort_by]


4. exit, означающий преждевременный выход из процедуры, в си записывается как return;

5. Вот такой цикл

for i := 1 to up_bound - low_bound + 1 do


Записывается так

for (i=1;i<=up_bound-low_bound+1;i++)


У тебя все правильно, но стоит "=" вместо "<=".

6. То же самое:

for j := low_bound to up_bound - 1 do


Записывается так:

for (j=low_bound;j<=up_bound-1;j++)


Тоже было "=", надо "<=".

7. Вот здесь:

while (j < up_bound) and (vv[sorted[j + 1], sort_by] = vv[sorted[j], sort_by]) do


Ты заменил случайно j на i. Верни smile.gif И не забудь про "==" вместо "="

8. Inc(j); - это просто j++.

9. Вот здесь:

i := j + 1;


Ты тоже случайно заменил j на i. Верни.


Давай, заменяй и приходи обратно. Какой у тебя си? Может си++? И ты уверен, что ты должен осилить именно "минимальную необходимую память и эффективные структуры данных"? Намучаешься немеряно, обещаю ;)

Может давай для начала напишем такую простую сортировку пузырьком? Вот тебе шаблон, попробуй дописать:


#include <stdio.h>

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

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

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

//отличий не нашли, значит вектора равны; возвращаем 0
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]
...
...
...
}
}

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("Результат сортировки:");
...
...
...
}


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


Не заметил в названии темы ВС++. Тогда вообще хорошо, можно std::sort юзать. Там ведь есть stl (последний раз, когда я видел BC++, я не знал, что такое stl smile.gif )? Впрочем, это уже другая история. Давай пока пузырьком.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +



#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 return 0; //если отличий не нашли, значит вектора равны или ; возвращаем 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;

}


Что-то вот такое вышло ... но не рабочее ))) Щас вот разбираться буду в чем дело... не сортирует помоему ничего... А чем отличается лексикографическая сортировка от просто сортировки? Я думал лексикографическая, касается сортировок алфавита (вобщем от слова лексико) ...

Я тут еще подправил.... помоему незачем писать лишний код...

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 return 0; //если отличий не нашли, значит вектора равны или ; возвращаем 0
}



твой был такой


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

//отличий не нашли, значит вектора равны; возвращаем 0
return 0;
}

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
Я тут еще подправил.... помоему незачем писать лишний код...
А по-моему, ты ошибаешься.. Это совершенно не эквивалентные коды...

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 return 0; //если отличий не нашли, значит вектора равны или ; возвращаем 0
}

Что произойдет, если vv[x][0] = vv[y][0]? Безо всяких сомнений функция вернет тебе 0, т.к. else относится только к результату сравнения if (vv[x][i]<vv[y][i])... Элементы равны, следовательно условие НЕ выполнилось, возвращен 0... Всё. Результат неверный... До второй итерации дело вообще не дойдет, хотя по идее если
vv[x][0] = vv[y][0], но vv[x][1] < vv[y][1] функция должна вернуть 1...

Тебе, кстати, компилятор должен давать Warning... Ты почему его игнорируешь?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Код
Вектор А=(А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.... так?

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Представь себе, что векторы - это слова, а элементы в векторах - буквы в словах. Твоя задача - отсортировать слова по алфавиту.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 19.11.2006 2:40) *

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


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

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

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


Каким макаром добиться этого условия?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

yes2.gif

Цитата

Код

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


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


Честно говоря, я тебе уже ответил на этот вопрос в самом начале. Но давай ты все-таки сделаешь, чтоб работало, а потом уж возмешься за оптимизацию. Доделай мой шаблон, убедись, что всё "сходится", и вектора действительно сортируются, выложи результат сюда, и потом попробуй разобраться в том, что я тебе ответил в той теме. Там - и память минимальная, и время.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 19.11.2006 13:06) *

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



#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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Молодец.

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


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

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


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 19.11.2006 14:45) *

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

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



#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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

Вроде будет работать нормально. Не забудь еще, что у нас внутри пузырек, который надо заменить быстрой сортировкой, так что возвращайся ;)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 20.11.2006 2:46) *

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

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

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


Все заработало как надо, Принтрезульт исправил. Чем заменить пузырек? Вставкой?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(KerK @ 20.11.2006 18:48) *

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


Лучше std::sort'ом просто. Надо объявить компаратор, и передать его третьим параметром. Сможешь?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 20.11.2006 21:54) *

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


неа ))) Первый раз слышу про компаратор )) ... да и помоему лучше не использовать STL... В задаче ничего не сказано... да и препод ничего такого не давал на лекциях...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

Показать как?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гость






Цитата(Michael_Rybak @ 20.11.2006 22:47) *

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

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


Конечно, если не использую, так хоть буду знать как использовать STL
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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 отсортирует указанный кусок массива просто по возрастанию (используя обычный оператор <). А когда мы указываем ему компаратор, он выполняет сравнения не оператором <, а оператором () этого компаратора, т.е. делает то, что нам нужно.

Проверил, вроде работает.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






Цитата(KerK @ 19.11.2006 13:00) *

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


А если лексикографически больше или меньше?
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.09.2020 17:54
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name