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

Сортировка Шелла - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.66
LiLi R.
 Аватар для LiLi R.
0 / 0 / 0
Регистрация: 15.04.2010
Сообщений: 82
15.04.2010, 18:11     Сортировка Шелла #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
#include <fstream>
#include <iostream>
#include <iomanip>
using namespace std;
 
ifstream in("input.txt");
ofstream out("output.txt");
 
struct mas
{
    int ses[5];
    int key;
    void print();
};
void sort(mas *a, int n)
{
    mas temp;
    int i,j, incr=n/2;
    while (incr>0)
    {
        for (i=incr; i<n; i++)
        {
            j=i-incr;
            while (j>=0)
                if (a[j].key>a[j+incr].key)
                { temp=a[j]; a[j]=a[j+incr]; a[j+incr]=temp; j=j-incr;}
                else j=-1;
        }
        incr=incr/2;
    }
}
int main()
{
    int n,m,i,j;
    int a[10][10];
    in>>n>>m;
    for (i=0; i<n; i++)
        for (j=0; j<m; j++)
            in>>a[i][j];
    int b[10];
    for (j=0; j<m; j++)
    {
        for (i=0; i<n; i++) b[i]=a[i][j];
        sort (b,n);
        for (i=0; i<n; i++) a[i][j]=b[i];
    }
    out<<n<<'t'<<m<<'\n';
    for (j=0; i<n; i++)
    {
        for (j=0; j<m; j++)
            out<<setw(5)<<a[i][j];
        out<<'\n';
    }
    in.close(); out.close();
    system("PAUSE");
return 0;
}
Не знаю как решить проблему. Хеееелп.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.04.2010, 18:11     Сортировка Шелла
Посмотрите здесь:

сортировка шелла C++
Сортировка Шелла C++
Сортировка Шелла C++
Пирамидальная сортировка и сортировка Шелла C++
C++ Сортировка Шелла
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Darky
Быдлокодер
 Аватар для Darky
507 / 294 / 45
Регистрация: 22.11.2009
Сообщений: 892
Завершенные тесты: 1
23.04.2010, 16:07     Сортировка Шелла #21
Vorona, Там ошибки нет.
LiLi R., Так и понятно. Посмотрите в тело функции - Вы оперируете переменными, которых даже не задали! И я об этом уже говорил.
Вот тоже самое - придумать свое слово и упорно использовать его, причем никто понимать тебя не будет. А вот если ты возьмешь словарь и впишешь его туда, то потом можешь тыкать незнающих носом, и они будут знать его значение. Объявите в теле функции или глобальные переменные, которых не хватает.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LiLi R.
 Аватар для LiLi R.
0 / 0 / 0
Регистрация: 15.04.2010
Сообщений: 82
23.04.2010, 19:56  [ТС]     Сортировка Шелла #22
Darky, обьявила. теперь 3 ошибки одного типа
error C2109: subscript requires array or pointer type 43 45 51 строка
Vorona
Peace 2 all shining faces
 Аватар для Vorona
660 / 522 / 44
Регистрация: 05.03.2010
Сообщений: 1,256
23.04.2010, 20:16     Сортировка Шелла #23
работу алгоритма не проверял и не компилировал, вместо a стоило написать matrix, или объявить a, как двумерный массив
еще нужно было динамически выделить вначале и удалить по окончанию работы программы память под matrix
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
#include <fstream>
#include <iostream>
#include <iomanip>
using namespace std;
 
ifstream in("input.txt");
ofstream out("output.txt");
 
void SortShell(int* arr, int size) {
        int step = size / 2, tmp, j;
        while (step != 0) {
                for (int i = step; i < size; ++i) {
                        tmp = arr[i];
                        for (j = i - step; j >= 0 && arr[j] > tmp; j -= step)
                                arr[j+step] = arr[j]; 
                        arr[j+step] = tmp;
                }    
                step /= 2;
        }
}
 
int main()
{
        int** matrix;  
    int   n, m, i, j;
        in>>n>>m;
    matrix = new int*[n];
    for(i = 0; i < n; i++)
        matrix[i] = new int[m];
        for (int i = 0; i<n; ++i)
                for (int j = 0; j<m; j++) 
                        SortShell(matrix[i], m);
        in>>matrix[i][0];
        int b[10];
        for (j=0; j<m; j++)
        {
                for (i=0; i<n; i++) b[i]=matrix[i][j];
                SortShell (b,n);
                for (i=0; i<n; i++) matrix[i][j]=b[i];
        }
        out<<n<<'t'<<m<<'\n';
        for (j=0; i<n; i++)
        {
                for (j=0; j<m; j++)
                        out<<setw(5)<<matrix[i][j];
                out<<'\n';
        }
        in.close(); out.close();
    for(i = 0; i < n; i++)
            delete []matrix[i];
    delete []matrix;
        system("PAUSE");
return 0;
}
и насчет чтения из файла неясно in>>n>>m;
LiLi R.
 Аватар для LiLi R.
0 / 0 / 0
Регистрация: 15.04.2010
Сообщений: 82
23.04.2010, 21:41  [ТС]     Сортировка Шелла #24
Vorona, программа компилется но при запуске ошибку выдает...
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2294 / 1664 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
23.04.2010, 21:50     Сортировка Шелла #25
LiLi R., еще бы, matrix используется без инициализации элементов.
Vorona
Peace 2 all shining faces
 Аватар для Vorona
660 / 522 / 44
Регистрация: 05.03.2010
Сообщений: 1,256
23.04.2010, 22:36     Сортировка Шелла #26
вставьте этот кусок после выделения памяти (после 29 строки)
здесь происходит присваивание значений, путем ввода их с клавиатуры, элементам матрицы
C++
1
2
3
4
5
for(i = 0; i < n; i++)
        for(j = 0; j < m; j++){
                cout << '[' << i << '][' << j << "]: ";
                cin >> matrix[i][j];
        }
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2294 / 1664 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
23.04.2010, 22:49     Сортировка Шелла #27
Vorona, сюда по коду приведенному в первом посте, матрицу необходимо читать из файла.
LiLi R.
 Аватар для LiLi R.
0 / 0 / 0
Регистрация: 15.04.2010
Сообщений: 82
23.04.2010, 23:39  [ТС]     Сортировка Шелла #28
Vorona, Да по задаче есть input.txt там матрица. как сделать так чтоб прога считала из файла?
Vorona
Peace 2 all shining faces
 Аватар для Vorona
660 / 522 / 44
Регистрация: 05.03.2010
Сообщений: 1,256
24.04.2010, 02:35     Сортировка Шелла #29
вот на си навоял минимально, видел, что вы и размеры матрицы из файла берете, так вот:
первые два числа в файле - размеры матрицы, остальные числа, каким бы образом ни были записаны они будут размещены относительно этих размеров...
никаких проверок на действительность кол-ва чисел относительно размеров матрицы не делал, просто посмотрите и разберитесь с этим:
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
#include <cstdio>
#include <conio.h>
#include <cstring>
#include <malloc.h>
 
#define size 3000
 
int main(){
    int i;
    char buf[size];
    for(i = 0; i < size; i++)
        buf[i] = 0;
 
    FILE* in;
    if(!(in = fopen("input.txt", "r")))
        printf("Reading error");
 
    for(i = 0; i < size; i++)
        fscanf(in, "%d", &buf[i]);
    
    for(i = 0; i < strlen(buf); i++)
        printf("%d ", buf[i]);
    printf("\n\n");
    
    int j, x;
    int n = buf[0];
    int m = buf[1];
    int **matrix = (int**)malloc(n*sizeof(int*));
    for(i = 0; i < n; i++)
        matrix[i] = (int*)malloc(m*sizeof(int));
 
    x = 2;
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            matrix[i][j] = buf[x++];
 
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++)
            printf("%d\t", matrix[i][j]);
        printf("\n");
    }
 
    for(i = 0; i < n; i++)
        free(matrix[i]);
    free(matrix);
 
    fclose(in);
    getch();
    return 0;
}
здесь:
выводим на экран все числа в файле
3 и 4 обозначили ее размерность и дальше числа выстраиваются в матрицу 3х4...
Миниатюры
Сортировка Шелла  
LiLi R.
 Аватар для LiLi R.
0 / 0 / 0
Регистрация: 15.04.2010
Сообщений: 82
25.04.2010, 20:22  [ТС]     Сортировка Шелла #30
Vorona, Все просто супер. Малюсенький вопрос и се - как результат вывести не в проге а в файл output.txt?
krolex
9 / 9 / 1
Регистрация: 27.01.2010
Сообщений: 63
25.04.2010, 23:05     Сортировка Шелла #31
все чем могу помочь....


3. Метод Шелла.
Метод состоит в том, что упорядочиваемый массив делится на ряд групп, каждая из которых упоря-дочивается методом вставки. Количество операций сравнений оценивается следующим образом: С  0,5 N3/2.
2. Метод вставки:
Элемент массива ai (начиная со второго) сравнивается последовательно с предшествующими aj, где j = i-1, i-2, … до тех пока не будет найден элемент с меньшим значением, чем ai. Пусть этот элемент с но-мером j, где j < i. Тогда все элементы с номерами j+1, …i-1 сдвигаются на одну позицию, а i-й элемент ставится на место (j+1)-го элемента. Если все впереди стоящие элементы больше i-го, то они сдвигаются на одну позицию, а i-й элемент ставится на первое место. Количество сравнений определяется по форму-ле: C = N(N-1)/4.
Vorona
Peace 2 all shining faces
 Аватар для Vorona
660 / 522 / 44
Регистрация: 05.03.2010
Сообщений: 1,256
26.04.2010, 00:15     Сортировка Шелла #32
откроем еще один поток out для записи в файл и везде, где выводим на экран, сразу же выводим и в файл функцией fprintf, аналогичной printf, просто принимает еще один аргумент - поток вывода информации)
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
#include <cstdio>
#include <conio.h>
#include <cstring>
#include <malloc.h>
 
#define size 3000
 
int main(){
    int i;
    char buf[size];
    for(i = 0; i < size; i++)
        buf[i] = 0;
 
    FILE *in, *out;
    if(!(in = fopen("input.txt", "r")))  //r для чтения (read)
        printf("Reading error");
    if(!(out = fopen("output.txt", "w"))) //w для записи (write)
        printf("Writing error");
 
    for(i = 0; i < size; i++)
        fscanf(in, "%d", &buf[i]);
        
    for(i = 0; i < strlen(buf); i++)
        printf("%d ", buf[i]);
    printf("\n\n");
        
    int j, x;
    int n = buf[0];
    int m = buf[1];
    int **matrix = (int**)malloc(n*sizeof(int*));
    for(i = 0; i < n; i++)
        matrix[i] = (int*)malloc(m*sizeof(int));
 
    x = 2;
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            matrix[i][j] = buf[x++];
 
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            printf("%d\t", matrix[i][j]);
            fprintf(out, "%d\t", matrix[i][j]);
        }
        printf("\n");
        fprintf(out, "\n");
    }
 
    for(i = 0; i < n; i++)
        free(matrix[i]);
    free(matrix);
 
    fclose(in);
        fclose(out);
    getch();
    return 0;
}
перед 39 строкой просто вставьте вашу сортировку, и на экран и в файл выведется нужная матрица
cyberobot
 Аватар для cyberobot
15 / 15 / 1
Регистрация: 01.09.2011
Сообщений: 66
05.01.2012, 09:27     Сортировка Шелла #33
вот моя функция сортировки шелла по возрастанию
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void shell_sort(T *a,int size)
{
     int b=0;
     int c=1;
     T promez;
     int op=0;
     while(op<size)
     {
                   if(a[b]<=a[c])
                   {
                   b++;
                   c++;
                   op++;
                   }
                   else
                   {
                   promez=a[b];
                   a[b]=a[c];
                   a[c]=promez;
                   op++;
                   };
     };
};
greeezz
272 / 165 / 4
Регистрация: 10.07.2011
Сообщений: 441
05.01.2012, 09:39     Сортировка Шелла #34
Цитата Сообщение от cyberobot Посмотреть сообщение
вот моя функция сортировки шелла по возрастанию
думается мне вы поторопились.
Вот я применил вашу функцию:
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
#include <iostream>
using std::cout;
using std::cin;
 
template <typename T>
void shell_sort(T *a, int size) {
    int b = 0;
    int c = 1;
    T promez;
    int op = 0;
    while (op < size) {
        if (a[b] <= a[c]) {
            b++;
            c++;
            op++;
        } else {
            promez = a[b];
            a[b] = a[c];
            a[c] = promez;
            op++;
        }
    }
}
 
 
int main() {
 
    const int size = 5;
    int a[size] = {1,4,3,5,3};
 
    cout << "before :: ";
    for(int i = 0; i < size; ++i){
        cout << a[i] << " ";
    }
 
 
    shell_sort(a,size);
 
    cout << "\n\nafter  :: ";
    for(int i = 0; i < size; ++i){
        cout << a[i] << " ";
    }
    cin.get();
    return 0;
}
РЕЗУЛЬТАТ

before :: 1 4 3 5 3

after :: 1 3 4 3 5
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2012, 15:28     Сортировка Шелла
Еще ссылки по теме:

C++ C++ Сортировка Шелла?
C++ Сортировка Шелла
C++ Сортировка Шелла

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

Или воспользуйтесь поиском по форуму:
cyberobot
 Аватар для cyberobot
15 / 15 / 1
Регистрация: 01.09.2011
Сообщений: 66
05.01.2012, 15:28     Сортировка Шелла #35
вот исправил
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
void shell_sort(T *a,int size)
{
     int b=0;
     int c=1;
     T promez;
     int op=0;
     while(op<size)
     {
                   if(a[b]<=a[c])
                   {
                   b++;
                   c++;
                   op++;
                   }
                   else
                   {
                   promez=a[b];
                   a[b]=a[c];
                   a[c]=promez;
                   b--;
                   c--; 
                   };
     };
};
Yandex
Объявления
05.01.2012, 15:28     Сортировка Шелла
Ответ Создать тему
Опции темы

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