Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
HITMAN
Absolution
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,779
1

DEV C++ 4.9.9.2 сортировка

15.04.2012, 17:31. Просмотров 1252. Ответов 13
Метки нет (Все метки)

Задание в исходнике!

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
 
using namespace std;
 
int no_sort[10][10] = {
        {50,15,33,32,23,29,34,98,22,98},
        {29,34,98,22,98,12,44,89,63,72},
        {12,44,89,63,72,48,54,63,71,82},
        {48,54,63,71,82,53,66,17,65,29},
        {53,66,17,65,29,50,15,33,32,23},
        {50,15,33,32,23,53,66,17,65,29},
        {29,34,98,22,98,50,15,33,32,23},
        {12,44,89,63,72,29,34,98,22,98},
        {48,54,63,71,82,12,44,89,63,72},
        {53,66,17,65,29,48,54,63,71,82}
    };
    
int yes_sort[10][10] = {
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
    };
    
int new_sort[10][10] = {
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
    };
 
void sort ()
{
//Алгоритм сортировки обязательно в подпрограмме, а вызов повторений в main
//Сортируем элементы строк справа налево по возрастанию
//Сортируем строки снизу вверх по сумме элементов по возрастанию
//Готовый массив разместить в yes_sort
//Массив new_sort получить из no_sort по алгоритму на картинке (по возрастанию) 
//no_sort не изменять   
}  
 
int main (int argc, char *argv[])
{ 
    char quit;
    quit = '\0';
    //timer start
    sort ();//repeat 0xFFFF
    //timer end
    cout << "array no sort." << endl;
    //out no_sort
    cout << "array yes sort." << endl;
    //out yes_sort
    cout << "array new sort." << endl;
    //out new_sort
    cout << "array time sort." << endl;
    //out time in ms
    while (quit != 'q')
    {
        cout << "Press q to quit " << endl;
        cin >> quit;
    }
    return 0;
}
0
Изображения
 
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.04.2012, 17:31
Ответы с готовыми решениями:

Dev C++
Помогите пожалуйста решить номера задач (2 и 3) в 7 варианте! в проге Dev C++...

Dev C++
Подскажите с советом. Если программа написанно на Visual Studio 2012, а нужно...

Dev C
как и где тут использовать &quot;malloc&quot; ??? #include &lt;stdio.h&gt; int...

Dev c++
помогите написать программу на dev c++ и построить блок схему к...

Dev-C++
Нажимаю &quot;скомпилировать&quot;, компиляция проходит успешно, но когда жму...

13
alex_x_x
бжни
2455 / 1661 / 134
Регистрация: 14.05.2009
Сообщений: 7,162
15.04.2012, 17:55 2
IOAN, можешь показать, что должно получиться в результате, а то читаю третий раз описание и все равно не могу понять, хотя ладно, вроде понял
и в чем смысл (сравнение с асм'ом?)
0
HITMAN
Absolution
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,779
15.04.2012, 18:00  [ТС] 3
Цитата Сообщение от alex_x_x Посмотреть сообщение
IOAN, можешь показать, что должно получиться в результате, а то читаю третий раз описание и все равно не могу понять, хотя ладно, вроде понял
и в чем смысл (сравнение с асм'ом?)
1) скорость выполнения, но не суть важно.
2) самое главное алгоритм сортировки подпрограммы sort что сгенерирует компилятор. Вариант C++ дизасемблируем и рассмотрим.
0
alex_x_x
бжни
2455 / 1661 / 134
Регистрация: 14.05.2009
Сообщений: 7,162
15.04.2012, 19:17 4
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <array>
 
const size_t X = 10, Y = 10;
typedef int vector[X];
typedef vector matrix[Y];
 
matrix no_sort = {
        {50,15,33,32,23,29,34,98,22,98},
        {29,34,98,22,98,12,44,89,63,72},
        {12,44,89,63,72,48,54,63,71,82},
        {48,54,63,71,82,53,66,17,65,29},
        {53,66,17,65,29,50,15,33,32,23},
        {50,15,33,32,23,53,66,17,65,29},
        {29,34,98,22,98,50,15,33,32,23},
        {12,44,89,63,72,29,34,98,22,98},
        {48,54,63,71,82,12,44,89,63,72},
        {53,66,17,65,29,48,54,63,71,82}
    };
    
matrix yes_sort = {
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
    };
    
matrix new_sort = {
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
    };
 
void sort (const matrix& in, matrix& out)
{
    static matrix temp;
    memcpy (temp, in, sizeof(matrix));
    size_t i;
    std::array<std::pair<int, unsigned>, Y> sum;
    for (i = 0 ; i < Y ; ++i)
    {
        vector& v = temp[i];
        std::sort(v, v + X);
        sum[i] = std::pair<int, unsigned> (std::accumulate(v, v + X, 0), i);
    }
    std::sort(sum.begin(), sum.end(), [](const std::pair<int, unsigned>& x,
                                         const std::pair<int, unsigned>& y
                                        ){
                                            return x.first < y.first;
                                        });
    for (i = 0 ; i < Y ; ++i) 
    {
        memcpy(out[i], temp[sum[i].second], sizeof(vector));
    }
}  
 
void fill (const matrix& in, matrix& out)
{   
    size_t index = 0;
    const int* input = &in[0][0];
    
    struct Point 
    {
        size_t x, y;
    };
        
    for (size_t p = 0 ; p < std::min(X, Y) ; ++p)
    {
        Point lt = { p, p },         rt = { X - p - 1, p },
              lb = { p, Y - p - 1 }, rb = { X - p - 1, Y - p - 1 };
              
        size_t i = lt.x, j = lt.y;
        
        for ( ; i < rt.x ; ++i) out[j][i] = input[index++];
        for ( ; j < rb.y ; ++j) out[j][i] = input[index++];
        for ( ; i > lb.x ; --i) out[j][i] = input[index++];
        for ( ; j > lt.y ; --j) out[j][i] = input[index++];
    }
}
 
void sort1 (const matrix& in, matrix& out)
{
    static matrix temp;
    memcpy (temp, in, sizeof(matrix));
    const size_t count = X * Y;
    int *it = &temp[0][0];
    size_t i, j;
    std::sort(it, it + count);
    fill(temp, new_sort);
}
 
void print (matrix& m, std::ostream& os)
{
    for (size_t i = 0 ; i < Y ; ++i)
    {
        for (size_t j = 0 ; j < X ; ++j)
        {
            os << m[i][j] << " ";
        }
        os << std::endl;
    }
}
 
int main (int argc, char *argv[])
{ 
    char quit;
    quit = '\0';
    //timer start
    sort (no_sort, yes_sort);//repeat 0xFFFF
    sort1(no_sort, new_sort);
    //timer end
    print(no_sort, std::cout);
    std::cout << std::endl;
    print(yes_sort, std::cout);
    std::cout << std::endl;
    print(new_sort, std::cout);
}
ну вот например такой код, что сравнивать?
0
Kuzia domovenok
2322 / 2070 / 481
Регистрация: 25.03.2012
Сообщений: 7,378
Записей в блоге: 1
15.04.2012, 19:23 5
Начни с функции получения координат следующего элемента, а там и пузырёк легко будет сделать.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void getnext(int* x, int* y){
  if (*x>=*y){
     if (*x<N-*y){
       (*x)++;
      }
      else{
       (*y)++;
      }
  }
  else{
     if (*x<=N-*y){
       if ((*x)==(*y-1))
              (*x)++;
          else
              (*y)--;
      }
      else{
       (*x)--;
      }
  
  }
}
0
HITMAN
Absolution
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,779
15.04.2012, 19:25  [ТС] 6
alex_x_x, при компиляции меня выдаёт кучу ошибок.
Первая: 6 C:\Dev-Cpp\Examples\Hello\Hello.cpp array: No such file or directory.

Добавлено через 1 минуту
alex_x_x, кинь ссылку на компилятор!
0
alex_x_x
бжни
2455 / 1661 / 134
Регистрация: 14.05.2009
Сообщений: 7,162
15.04.2012, 19:41 7
IOAN, это с++11, можно переписать на обычный

http://ideone.com/itkyA
0
HITMAN
Absolution
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,779
15.04.2012, 19:54  [ТС] 8
alex_x_x, заработало! Добавь таймер, сейчас допишу на асме и буду машинные коды сравнивать.
0
alex_x_x
бжни
2455 / 1661 / 134
Регистрация: 14.05.2009
Сообщений: 7,162
15.04.2012, 20:11 9
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
 
const size_t X = 10, Y = 10;
typedef int vector[X];
typedef vector matrix[Y];
 
matrix no_sort = {
        {50,15,33,32,23,29,34,98,22,98},
        {29,34,98,22,98,12,44,89,63,72},
        {12,44,89,63,72,48,54,63,71,82},
        {48,54,63,71,82,53,66,17,65,29},
        {53,66,17,65,29,50,15,33,32,23},
        {50,15,33,32,23,53,66,17,65,29},
        {29,34,98,22,98,50,15,33,32,23},
        {12,44,89,63,72,29,34,98,22,98},
        {48,54,63,71,82,12,44,89,63,72},
        {53,66,17,65,29,48,54,63,71,82}
    };
    
matrix yes_sort = {
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
    };
    
matrix new_sort = {
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
    };
 
struct cmp {
    bool operator()(const std::pair<int, unsigned>& x, const std::pair<int, unsigned>& y) {
        return x.first < y.first;
    }
};
    
void sort (const matrix& in, matrix& out)
{
    static matrix temp;
    memcpy (temp, in, sizeof(matrix));
    size_t i;
    std::pair<int, unsigned> sum[Y];
    for (i = 0 ; i < Y ; ++i)
    {
        vector& v = temp[i];
        std::sort(v, v + X);
        sum[i] = std::pair<int, unsigned> (std::accumulate(v, v + X, 0), i);
    }
    
    std::sort(&sum[0], &sum[0] + Y, cmp());
    
    for (i = 0 ; i < Y ; ++i) 
    {
        memcpy(out[i], temp[sum[i].second], sizeof(vector));
    }
}  
 
void fill (const matrix& in, matrix& out)
{   
    size_t index = 0;
    const int* input = &in[0][0];
    
    struct Point 
    {
        size_t x, y;
    };
        
    for (size_t p = 0 ; p < std::min(X, Y) ; ++p)
    {
        Point lt = { p, p },         rt = { X - p - 1, p },
              lb = { p, Y - p - 1 }, rb = { X - p - 1, Y - p - 1 };
              
        size_t i = lt.x, j = lt.y;
        
        for ( ; i < rt.x ; ++i) out[j][i] = input[index++];
        for ( ; j < rb.y ; ++j) out[j][i] = input[index++];
        for ( ; i > lb.x ; --i) out[j][i] = input[index++];
        for ( ; j > lt.y ; --j) out[j][i] = input[index++];
    }
}
 
void sort1 (const matrix& in, matrix& out)
{
    static matrix temp;
    memcpy (temp, in, sizeof(matrix));
    const size_t count = X * Y;
    int *it = &temp[0][0];
    size_t i, j;
    std::sort(it, it + count);
    fill(temp, new_sort);
}
 
void print (matrix& m, std::ostream& os)
{
    for (size_t i = 0 ; i < Y ; ++i)
    {
        for (size_t j = 0 ; j < X ; ++j)
        {
            os << m[i][j] << " ";
        }
        os << std::endl;
    }
}
 
int main (int argc, char *argv[])
{ 
    char quit;
    quit = '\0';
    
    const unsigned count = 100000;
    clock_t start, end;
    double dif;
    
    //timer start
    start = clock();
    
    for (unsigned i=0;i<count;++i) 
    {
        sort (no_sort, yes_sort);
        sort1(no_sort, new_sort);
    }
    //timer end
    end = clock();
    dif = 1.0 * (end - start) / CLOCKS_PER_SEC;
    
    print(no_sort, std::cout);
    std::cout << std::endl;
    print(yes_sort, std::cout);
    std::cout << std::endl;
    print(new_sort, std::cout);
    std::cout << std::endl << dif << " seconds" << std::endl;
}
както так
0
Buckstabue
25.04.2012, 21:57
  #10

Не по теме:

Простите, что вмешиваюсь, так каков результат?
П.с. очень удивился насколько быстр C++, если вышеуказанный метод c флагом -O3 на моём не самом мощном компе выполняется за 0.26 сек

0
HITMAN
Absolution
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,779
26.04.2012, 16:29  [ТС] 11
Buckstabue, первоначальные варианты.
--- asm c++
size 5Кб 460Кб
speed ~900ms ~1100ms

С оптимизирующими опциями.
--- asm c++
size 8Кб 1.2Мб
speed ~700ms ~200ms
Дальше честно говоря

Не по теме:

зад:smoke:лбался

, но скоро подумываю продолжить.
0
Troll_Face
603 / 403 / 8
Регистрация: 26.04.2012
Сообщений: 2,070
08.06.2012, 11:05 12
Цитата Сообщение от Buckstabue Посмотреть сообщение
очень удивился насколько быстр C++
представь за сколько выполнится этот код на асме...
0
alex_x_x
бжни
2455 / 1661 / 134
Регистрация: 14.05.2009
Сообщений: 7,162
08.06.2012, 12:08 13
Fatal Error, код на с++ оказался в разы быстрее асмовского
0
Troll_Face
603 / 403 / 8
Регистрация: 26.04.2012
Сообщений: 2,070
08.06.2012, 12:11 14
alex_x_x, не может быть
0
08.06.2012, 12:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2012, 12:11

Dev-C++5.6.3
Здравствуйте, помогите разобраться в проблеме. Давно мечтал заняться...

Dev-C++
подскажите чайнику нашел нете книжку обучение С++ для чайников и как понял она...

Dev C
Пришу помощи от экспертов, ерунду прошу не писать! Недавно пришёл в недоумение...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru