Сортировка Шелла

@LiLi R. · Регистрация: 15.04.2010

Author24 — интернет-сервис помощи студентам

Ребят помогите. есть матрица нужно отсортировать каждую строчку матрицы по убыванию алгоритмом Шелла.

C++

#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;
}

Не знаю как решить проблему. Хеееелп.

@Darky · 23.04.2010, 16:07

Vorona, Там ошибки нет.
LiLi R., Так и понятно. Посмотрите в тело функции - Вы оперируете переменными, которых даже не задали! И я об этом уже говорил.
Вот тоже самое - придумать свое слово и упорно использовать его, причем никто понимать тебя не будет. А вот если ты возьмешь словарь и впишешь его туда, то потом можешь тыкать незнающих носом, и они будут знать его значение. Объявите в теле функции или глобальные переменные, которых не хватает.

@LiLi R. · 23.04.2010, 19:56 **[ТС]**

Darky, обьявила. теперь 3 ошибки одного типа
error C2109: subscript requires array or pointer type 43 45 51 строка

@Vorona · 23.04.2010, 20:16

работу алгоритма не проверял и не компилировал, вместо a стоило написать matrix, или объявить a, как двумерный массив
еще нужно было динамически выделить вначале и удалить по окончанию работы программы память под matrix

C++

#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. · 23.04.2010, 21:41 **[ТС]**

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

@CyBOSSeR · 23.04.2010, 21:50

LiLi R., еще бы, matrix используется без инициализации элементов.

@Vorona · 23.04.2010, 22:36

вставьте этот кусок после выделения памяти (после 29 строки)
здесь происходит присваивание значений, путем ввода их с клавиатуры, элементам матрицы

C++

for(i = 0; i < n; i++)
        for(j = 0; j < m; j++){
                cout << '[' << i << '][' << j << "]: ";
                cin >> matrix[i][j];
        }

@CyBOSSeR · 23.04.2010, 22:49

Vorona, сюда по коду приведенному в первом посте, матрицу необходимо читать из файла.

@LiLi R. · 23.04.2010, 23:39 **[ТС]**

Vorona, Да по задаче есть input.txt там матрица. как сделать так чтоб прога считала из файла?

@Vorona · 24.04.2010, 02:35

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

C

#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. · 25.04.2010, 20:22 **[ТС]**

Vorona, Все просто супер. Малюсенький вопрос и се - как результат вывести не в проге а в файл output.txt?

@krolex · 25.04.2010, 23:05

все чем могу помочь....

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 · 26.04.2010, 00:15

откроем еще один поток out для записи в файл и везде, где выводим на экран, сразу же выводим и в файл функцией fprintf, аналогичной printf, просто принимает еще один аргумент - поток вывода информации)

C

#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 · 05.01.2012, 09:27

вот моя функция сортировки шелла по возрастанию

C++

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 · 05.01.2012, 09:39

Сообщение от cyberobot

вот моя функция сортировки шелла по возрастанию

думается мне вы поторопились.
Вот я применил вашу функцию:

C++

#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

@cyberobot · 05.01.2012, 15:28

вот исправил

C++

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--; 
                   };
     };
};

@krolex 9 / 9 / 2 Регистрация: 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. 0

@Darky Быдлокодер 512 / 298 / 85 Регистрация: 22.11.2009 Сообщений: 892
	23.04.2010, 16:07	21
	Vorona, Там ошибки нет. LiLi R., Так и понятно. Посмотрите в тело функции - Вы оперируете переменными, которых даже не задали! И я об этом уже говорил. Вот тоже самое - придумать свое слово и упорно использовать его, причем никто понимать тебя не будет. А вот если ты возьмешь словарь и впишешь его туда, то потом можешь тыкать незнающих носом, и они будут знать его значение. Объявите в теле функции или глобальные переменные, которых не хватает. 0

@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 строка 0

@LiLi R. 0 / 0 / 0 Регистрация: 15.04.2010 Сообщений: 82
	23.04.2010, 21:41 [ТС]	24
	Vorona, программа компилется но при запуске ошибку выдает... 0

@CyBOSSeR 2347 / 1720 / 148 Регистрация: 06.03.2009 Сообщений: 3,675
	23.04.2010, 21:50	25
	LiLi R., еще бы, matrix используется без инициализации элементов. 0

@CyBOSSeR 2347 / 1720 / 148 Регистрация: 06.03.2009 Сообщений: 3,675
	23.04.2010, 22:49	27
	Vorona, сюда по коду приведенному в первом посте, матрицу необходимо читать из файла. 0

@LiLi R. 0 / 0 / 0 Регистрация: 15.04.2010 Сообщений: 82
	23.04.2010, 23:39 [ТС]	28
	Vorona, Да по задаче есть input.txt там матрица. как сделать так чтоб прога считала из файла? 0

@LiLi R. 0 / 0 / 0 Регистрация: 15.04.2010 Сообщений: 82
	25.04.2010, 20:22 [ТС]	30
	Vorona, Все просто супер. Малюсенький вопрос и се - как результат вывести не в проге а в файл output.txt? 0