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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
HITMAN
Absolution
 Аватар для HITMAN
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,768
15.04.2012, 17:31     DEV C++ 4.9.9.2 сортировка #1
Задание в исходнике!

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;
}
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.04.2012, 17:31     DEV C++ 4.9.9.2 сортировка
Посмотрите здесь:

Dev C C++
C++ Dev-C++
C++ dev c++
C++ Dev C++
Dev-C++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
15.04.2012, 17:55     DEV C++ 4.9.9.2 сортировка #2
IOAN, можешь показать, что должно получиться в результате, а то читаю третий раз описание и все равно не могу понять, хотя ладно, вроде понял
и в чем смысл (сравнение с асм'ом?)
HITMAN
Absolution
 Аватар для HITMAN
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,768
15.04.2012, 18:00  [ТС]     DEV C++ 4.9.9.2 сортировка #3
Цитата Сообщение от alex_x_x Посмотреть сообщение
IOAN, можешь показать, что должно получиться в результате, а то читаю третий раз описание и все равно не могу понять, хотя ладно, вроде понял
и в чем смысл (сравнение с асм'ом?)
1) скорость выполнения, но не суть важно.
2) самое главное алгоритм сортировки подпрограммы sort что сгенерирует компилятор. Вариант C++ дизасемблируем и рассмотрим.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
15.04.2012, 19:17     DEV C++ 4.9.9.2 сортировка #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);
}
ну вот например такой код, что сравнивать?
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
15.04.2012, 19:23     DEV C++ 4.9.9.2 сортировка #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)--;
      }
  
  }
}
HITMAN
Absolution
 Аватар для HITMAN
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,768
15.04.2012, 19:25  [ТС]     DEV C++ 4.9.9.2 сортировка #6
alex_x_x, при компиляции меня выдаёт кучу ошибок.
Первая: 6 C:\Dev-Cpp\Examples\Hello\Hello.cpp array: No such file or directory.

Добавлено через 1 минуту
alex_x_x, кинь ссылку на компилятор!
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
15.04.2012, 19:41     DEV C++ 4.9.9.2 сортировка #7
IOAN, это с++11, можно переписать на обычный

http://ideone.com/itkyA
HITMAN
Absolution
 Аватар для HITMAN
155 / 125 / 3
Регистрация: 22.06.2011
Сообщений: 1,768
15.04.2012, 19:54  [ТС]     DEV C++ 4.9.9.2 сортировка #8
alex_x_x, заработало! Добавь таймер, сейчас допишу на асме и буду машинные коды сравнивать.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
15.04.2012, 20:11     DEV C++ 4.9.9.2 сортировка #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;
}
както так
Buckstabue
25.04.2012, 21:57
  #10

Не по теме:

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

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

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

Не по теме:

задлбался

, но скоро подумываю продолжить.
Troll_Face
 Аватар для Troll_Face
599 / 399 / 4
Регистрация: 26.04.2012
Сообщений: 2,070
08.06.2012, 11:05     DEV C++ 4.9.9.2 сортировка #12
Цитата Сообщение от Buckstabue Посмотреть сообщение
очень удивился насколько быстр C++
представь за сколько выполнится этот код на асме...
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
08.06.2012, 12:08     DEV C++ 4.9.9.2 сортировка #13
Fatal Error, код на с++ оказался в разы быстрее асмовского
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2012, 12:11     DEV C++ 4.9.9.2 сортировка
Еще ссылки по теме:

C++ Dev C++
C++ dev-c++

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

Или воспользуйтесь поиском по форуму:
Troll_Face
 Аватар для Troll_Face
599 / 399 / 4
Регистрация: 26.04.2012
Сообщений: 2,070
08.06.2012, 12:11     DEV C++ 4.9.9.2 сортировка #14
alex_x_x, не может быть
Yandex
Объявления
08.06.2012, 12:11     DEV C++ 4.9.9.2 сортировка
Ответ Создать тему
Опции темы

Текущее время: 16:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru