Работа с матрицами в С , Не работает сортировка для матрицы методом просеивания

[Andrey_2019]

Здравствуйте. Помогите, пожалуйста, с задачей: Проверить упорядочены ли элементы столбцов матрицы. Если нет, то упорядочить их в порядке возрастания методом просеивания.
Вот мой исходный код, но у меня там ничего не сортирует:

#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
int main ()
{
int a[10][10];
int i, j, n, m, r, k, p;
printf ("Vvedite razmer matrici n=");  
scanf ("%d", &n);
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
    printf("a[%d][%d]=", i, j);
    scanf("%d", &a[i][j]);
}
for (i = 0; i < n; i++)
{
    k = p = 0;  
    for (j = 0; j < n - 1; j++)
        if (a[i][j] <= a[i][j + 1])
    k++;
        else
            p++;
    if (k != n - 1 && p != n - 1)
    {
        for (i=0;i<=n-2;i++)
        if (a[i][j]>a[i+1][j])
        {
            r=a[i][j];
            a[i][j]=a[i+1][j];
            a[i+1][j]=r;
            j=i;
        while (a[i][j]<a[i][j-1]&&j>0)
        {
            r=a[i][j];
            a[i][j]=a[i][j-1];
            a[i][j-1]=r;
            j=j-1;
        }  
        }
    }
}
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
    printf("%2d", a[i][j]);
    printf("\n");
}              
}

[Славян]

1. Вначале бегут по строкам (i) и проверяют на упорядоченность... именно эту строку!
2. Поняв, что нет какого-либо порядка, предпринимается попытка упорядочить... столбец! При этом снова используется внешнецикловая переменная i!

[Andrey_2019]

Вот я поменял в циклах i на j, но всё равно ничего не сортирует:

#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
int main ()
{
int a[10][10];
int i, j, n, m, r, k, p;
printf ("Vvedite razmer matrici n=");  
scanf ("%d", &n);
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
    printf("a[%d][%d]=", i, j);
    scanf("%d", &a[i][j]);
}
for (j = 0; j < n; j++)
{
    k = p = 0;  
    for (j = 0; j < n - 1; j++)
        if (a[i][j] <= a[i][j + 1])
    k++;
        else
            p++;
    if (k != n - 1 && p != n - 1)
    {
        for (j=0;j<=n-2;j++)
        if (a[i][j]>a[i+1][j])
        {
            r=a[i][j];
            a[i][j]=a[i+1][j];
            a[i+1][j]=r;
            j=i;
        while (a[i][j]<a[i][j-1]&&j>0)
        {
            r=a[i][j];
            a[i][j]=a[i][j-1];
            a[i][j-1]=r;
            j=j-1;
        }  
        }
    }
}
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
    printf("%2d", a[i][j]);
    printf("\n");
}              
}

[Wound]

Цитата Andrey_2019 @ 22.11.19, 06:22

Вот я поменял в циклах i на j, но всё равно ничего не сортирует:

Не знаю что за метод просеивания, но пузырьком как пример вот налабал на коленке: https://ideone.com/cYqRpQ
Правда тут С++. Под С переписать будет плевое дело.

Скрытый текст

    #include <cmath>
    #include <ctime>
    #include <iostream>
    
    int** CreateMatrix(int x, int y)
    {
        int** matrix = new int *[x];
        for (int row = 0; row < x; ++row)
            matrix[row] = new int[y];
        return matrix;
    }
    
    void FillMatrix(int** mtx, int x, int y)
    {
        srand(time(nullptr));
        for (int row = 0; row < x; ++row)
        {
            for (int col = 0; col < y; ++col)
            {
                mtx[row][col] = 1 + rand() % 9;
            }
        }
    }
    
    void PrintMatrix(int** mtx, int x, int y)
    {
        for (int row = 0; row < x; ++row)
        {
            for (int col = 0; col < y; ++col)
            {
                std::cout << mtx[row][col] << " ";
            }
            std::cout << std::endl;
        }
    }
    
    void SortVector(int** vector, int y, int size)
    {
        int i = 0;
        int buf;
        char swap_cnt = 0;
        while (i < size)
        {
            if (i + 1 != size && vector[i][y] > vector[i + 1][y])
            {
                buf = vector[i][y];
                vector[i][y] = vector[i + 1][y];
                vector[i + 1][y] = buf;
                swap_cnt = 1;
            }
            i++;
            if (i == size && swap_cnt == 1)
            {
                swap_cnt = 0;
                i = 0;
            }
        }
    }
    
    void SortColsMatrix(int** mtx, int x, int y)
    {
        for (int col = 0; col < y; ++col)
        {
            SortVector(mtx, col, x);
        }
    }
    
    void FreeMatrix(int** &mtx, int x, int y)
    {
        for (int row = 0; row < x; ++row)
            delete[] mtx[row];
        delete[] mtx;
    }
    
    int main()
    {
        int x = 7;
        int y = 5;
        int** mtx = CreateMatrix(x,y);
        FillMatrix(mtx, x, y);
    
        std::cout << "Unsorted matrix: " << std::endl;
        PrintMatrix(mtx, x, y);
        std::cout << std::endl;
    
        SortColsMatrix(mtx, x, y);
    
        std::cout << "Sorted matrix: "<< std::endl;
        std::cout << std::endl;
        PrintMatrix(mtx, x, y);
    
        FreeMatrix(mtx, x, y);
    
        return 0;
    }

Сообщение отредактировано: Wound - 22.11.19, 08:14

[Andrey_2019]

Wound, спасибо, конечно, за решение, но мне нужно отсортировать матрицу именно методом просеивания. У меня есть код для сортировки массива, может попробуешь его переписать под матрицу? Вот он:

for (i=0;i<=n-2;i++)
 if (A[i]>A[i+1])
 {
  r=A[i];
  A[i]=A[i+1];
  A[i+1]=r;
  j=i;
  while (A[j]<A[j-1]&&j>0)
  {
    r=A[j];
    A[j]=A[j-1];
    A[j-1]=r;
    j=j-1;
  }
}

[Wound]

Цитата Andrey_2019 @ 22.11.19, 09:45

Wound, спасибо, конечно, за решение, но мне нужно отсортировать матрицу именно методом просеивания. У меня есть код для сортировки массива, может попробуешь его переписать под матрицу? Вот он:

Ну так там изменить нужно только функцию SortVector, которая сортирует по сути массив

Добавлено 22.11.19, 09:54
плюс твой алгоритм не правильный

 while (A[j]<A[j-1]&&j>0)

Что будет вот тут -> A[j-1], если j == 0? -1 ?

Добавлено 22.11.19, 09:57
И че за сортировка происеиванием? Впервые о такой слышу? Ссылку кинь? Может она по другому как то называется? Даже гугл не находит такой.

Добавлено 22.11.19, 10:07
Вообще, если есть алгоритм то там все просто переписывается. В твоем случае A меняется на vector, и добавляется второй индекс массива [y], аля:

void SortVector(int** vector, int y, int size)
{
 
    for (int i = 1; i <= size - 2; i++)
        if (vector[i][y] > vector[i + 1][y])
        {
            int r = vector[i][y];
            vector[i][y] = vector[i + 1][y];
            vector[i + 1][y] = r;
            int j = size-1;
            while (vector[j][y] < vector[j - 1][y] && j>0)
            {
                r = vector[j][y];
                vector[j][y] = vector[j - 1][y];
                vector[j - 1][y] = r;
                j = j - 1;
            }
        }
}

Но тут я исправил: int j = size-1;
Вместо твоего: j=i; сразу перед while.

Потому что у тебя там написан бред. И этот вариант тоже не работает, потому что твой алгоритм, не рабочий. Но так оно по крайней мере не падает на Access Violation, когда обращаешься к отрицательному индексу массива в твоем случае. Т.к. очевидно - j должно указывать на конец массива, т.к. используется декремент в цикле:
j = j - 1;

Так что переписать тут как два пальца, 2 минуты ровно. Пиши правильный алгоритм и заменяй по аналогии SortVector.

Добавлено 22.11.19, 10:27
С горем пополам нагуглил что за сортировка просеиванием, на держи: https://ideone.com/o1wfMK

// Matrix.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <cmath>
#include <ctime>
#include <iostream>
 
int** CreateMatrix(int x, int y)
{
    int** matrix = new int *[x];
    for (int row = 0; row < x; ++row)
        matrix[row] = new int[y];
    return matrix;
}
 
void FillMatrix(int** mtx, int x, int y)
{
    srand(time(nullptr));
    for (int row = 0; row < x; ++row)
    {
        for (int col = 0; col < y; ++col)
        {
            mtx[row][col] = 1 + rand() % 9;
        }
    }
}
 
void PrintMatrix(int** mtx, int x, int y)
{
    for (int row = 0; row < x; ++row)
    {
        for (int col = 0; col < y; ++col)
        {
            std::cout << mtx[row][col] << " ";
        }
        std::cout << std::endl;
    }
}
 
void SortVector(int** vector, int y, int size)
{
    bool flagsort = false;
    do
    {
        flagsort = true;
        for (int i = 0; i < size-1; ++i)
        {
            if (vector[i][y] > vector[i+1][y])
            {
                int t = vector[i][y];
 
                vector[i][y] = vector[i+1][y];
                vector[i+1][y] = t;
 
                int j = i;
                while (j > 0 && (vector[j-1][y]) > vector[j][y])
                {
                    t = vector[j][y];
                    vector[j][y] = vector[j-1][y];
                    vector[j-1][y] = t;
                    --j;
                }
                flagsort = false;
            }
        }
    }while(flagsort);
}
 
void SortColsMatrix(int** mtx, int x, int y)
{
    for (int col = 0; col < y; ++col)
    {
        SortVector(mtx, col, x);
    }
}
 
void FreeMatrix(int** &mtx, int x, int y)
{
    for (int row = 0; row < x; ++row)
        delete[] mtx[row];
    delete[] mtx;
}
 
int main()
{
    int x = 7;
    int y = 5;
    int** mtx = CreateMatrix(x,y);
    FillMatrix(mtx, x, y);
 
    std::cout << "Unsorted matrix: " << std::endl;
    PrintMatrix(mtx, x, y);
    std::cout << std::endl;
 
    SortColsMatrix(mtx, x, y);
 
    std::cout << "Sorted matrix: "<< std::endl;
    std::cout << std::endl;
    PrintMatrix(mtx, x, y);
 
    FreeMatrix(mtx, x, y);
 
    return 0;
}

Добавлено 22.11.19, 10:30
Алгоритм сортировки брал отсюда: https://studbooks.net/2273951/informatika/s...irovka_puzyrkom

Добавлено 22.11.19, 10:32
Только не показывай в таком виде. Учитель тебя сразу вскроет что писал не ты. Инфа 146%.

Сообщение отредактировано: Wound - 22.11.19, 10:32

[Qraizer]

Это т.н. "гномья сортировка".

[Andrey_2019]

Wound, если вам не сложно, можете, пожалуйста, переписать свой код с С++ на С? А то я не очень разбираюсь в этих языках. И без процедур и функций, если можно.

[Wound]

Цитата Andrey_2019 @ 01.12.19, 08:33

Wound, если вам не сложно, можете, пожалуйста, переписать свой код с С++ на С? А то я не очень разбираюсь в этих языках. И без процедур и функций, если можно.

Тут и так на Си написано, надо только убрать std::cout, заменив его на printf например, поправить заголовки, и new заменить на malloc(), а delete[] на free()

Добавлено 01.12.19, 13:56
А ну и nullptr изменить на 0 или NULL, и bool например на int

[Dushevny]

Цитата Andrey_2019 @ 01.12.19, 08:33

А то я не очень разбираюсь в этих языках

Если это курсовая, то вы за семестр должны были изучить хотя бы Си на уровне, достаточном для решения поставленой задачи. Если это прикладная задача, то непонятно требование обязательно применять какую-то экзотическую сортировку.

Сообщение отредактировано: Dushevny - 01.12.19, 15:25

[Andrey_2019]

Member, я учусь на заочке в универе. Последняя сессия была этим летом, на ней по С было 4 лабы, этого мало, чтобы разобраться в нём.

Добавлено 01.12.19, 16:00
Wound, окей. Вы можете переписать свой код на С++, чтобы в нём не было процедур и функций? Просто это требование преподавателя. Я его потом под С потом перепишу.

Сообщение отредактировано: Andrey_2019 - 01.12.19, 16:00

[Wound]

Цитата Andrey_2019 @ 01.12.19, 15:55

Wound, окей. Вы можете переписать свой код на С++, чтобы в нём не было процедур и функций? Просто это требование преподавателя. Я его потом под С потом перепишу.

Берешь тело функции, и подставляешь вместо вызова функции в main.
Например:

int main()
{
    int x = 7;
    int y = 5;
    int** mtx = CreateMatrix(x,y);
    FillMatrix(mtx, x, y);

Вот видим CreateMatrix(x,y)

Вместо него пишем:

int main()
{
    int x = 7;
    int y = 5;
    //////////////Create Matrix///////////////
    int** matrix = new int *[x];
    for (int row = 0; row < x; ++row)
        matrix[row] = new int[y];
    //////////////END OF Create Matrix///////////////
 
    FillMatrix(mtx, x, y);
...

Вот выше код принимает вот такой вот вид. Функцию CreateMatrix можно теперь удалить, т.к. ее тело мы перенесли в функцию main
Далее видим вызов FillMatrix, подставляем вместо него его тело, получаем:

int main()
{
    int x = 7;
    int y = 5;
    //////////////Тут был вызов int** mtx = CreateMatrix(x,y); теперь тут тело функции///////////////
    int** matrix = new int *[x];
    for (int row = 0; row < x; ++row)
        matrix[row] = new int[y];
    //////////////END OF CreateMatrix///////////////
 
    //////////////Тут был вызов FillMatrix(mtx, x, y); теперь тут тело функции///////////////
    srand(time(nullptr));
    for (int row = 0; row < x; ++row)
    {
        for (int col = 0; col < y; ++col)
        {
            matrix[row][col] = 1 + rand() % 9;
        }
    }
    //////////////END OF FillMatrix///////////////
...

Заметь что переменная называлась mtx, после копипасты начала называться matrix, соответственно я ее переименовал в коде, т.к. это уже код в функции main.
Ну и далее по аналогии переводи.

[Andrey_2019]

Всё,я сделал эту задачу. Wound, огромное вам спасибо за решение.