Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
HITMAN
Absolution
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,780
#1

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

15.04.2012, 17:31. Просмотров 1196. Ответов 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++ 4.9.9.2 сортировка (C++):

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

Dev-c++ - C++
Так получилось, что должен некоторое время поработать в этом известном бесплатном компиляторе. В отличие от builder'а, где AnsiString...

dev c++ - C++
дан массив, состоящий из н элементов. Верно ли, что отрицательных членов в массиве больше чем положительных

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

Dev C++ - C++
Скачал Dev C++ и тут такая фигня: хочу запустить программу и пишет что проект не откомпилирован. Жму скомпилировать а потом выполнить и то...

Dev C - C++
как и где тут использовать &quot;malloc&quot; ??? #include &lt;stdio.h&gt; int main () { int n, a, i; scanf...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
15.04.2012, 17:55 #2
IOAN, можешь показать, что должно получиться в результате, а то читаю третий раз описание и все равно не могу понять, хотя ладно, вроде понял
и в чем смысл (сравнение с асм'ом?)
0
HITMAN
Absolution
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,780
15.04.2012, 18:00  [ТС] #3
Цитата Сообщение от alex_x_x Посмотреть сообщение
IOAN, можешь показать, что должно получиться в результате, а то читаю третий раз описание и все равно не могу понять, хотя ладно, вроде понял
и в чем смысл (сравнение с асм'ом?)
1) скорость выполнения, но не суть важно.
2) самое главное алгоритм сортировки подпрограммы sort что сгенерирует компилятор. Вариант C++ дизасемблируем и рассмотрим.
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 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
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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,780
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
бжни
2447 / 1652 / 84
Регистрация: 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,780
15.04.2012, 19:54  [ТС] #8
alex_x_x, заработало! Добавь таймер, сейчас допишу на асме и буду машинные коды сравнивать.
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 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,780
26.04.2012, 16:29  [ТС] #11
Buckstabue, первоначальные варианты.
--- asm c++
size 5Кб 460Кб
speed ~900ms ~1100ms

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

Не по теме:

задлбался

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

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

dev-c++ - C++
Использую компилятор Dev-c++ Вроде все хорошо, ошибку не выдает, компилирует, но при запуске только вот это

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.06.2012, 12:11
Ответ Создать тему
Опции темы

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