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

Сортировка двумерного массива - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.62
Gabberr
 Аватар для Gabberr
101 / 101 / 17
Регистрация: 13.10.2009
Сообщений: 402
19.04.2010, 11:57     Сортировка двумерного массива #1
Задача такая:
Дано натуральное N (1<=N<=10), целочисленный квадратный массив-матрица (aij), 0<= i,j <N. Отсортировать элементы матрицы так, чтобы при прохождении по спирали они были бы упорядочены по не убыванию. Метод сортировки - сортировка вставками.
Важное ограничение. При сортировке элементов матрицы не разрешается использовать дополнительные структуры данных (массивы), то есть вся сортировка должна производиться «на месте» – в исходном массиве (ограничение не распространяется на сортировку подсчетом, в которой есть необходимость в дополнительных массивах). Кроме этого нужно сохранить временную сложность алгоритма сортировки: другими словами нельзя вводить дополнительных циклов (например, для вычисления координат) по сравнению с теми, что уже есть в сортировке.
Если была построена функция F в работе № 2, тогда решить задачу в указанном ограничении не составит труда. А именно: алгоритм сортировки сортирует «как бы обычный» виртуальный линейный массив из N^2 элементов, но для каждого элемента с помощью функции F находят его реальные координаты в матрице.

(функцию F в предедущей работе я построил
Дано натуральное N (1<=N<=10). Заполнить матрицу порядка N*N целыми числами 0, 1, 2, 3, …, N2–1 по спирали(по часовой стрелке).
Важное замечание. Заполнение матрицы можно организовать двумя способами. Первый (простой) – так организовать перебор индексов элементов матрицы, что будет получен нужный порядок прохода по матрице «змейкой». Второй (более сложный, но именно он может пригодиться в третьей работе): найти соотношение между значением элемента K и его индексами [i,j], то есть функцию вида F(K,N) = <i,j>, которая по номеру K элемента в змейке возвращает его координаты в матрице <i,j>; другими словами a[i,j]=K. При этом данная функция не должна использовать циклы – только элементарные арифметические действия и проверку различ-ных условий! Построив такую функцию можно простым перебором значений K от 0 до N^2–1 находить индексы для каждого K с помощью функции F и записывать в матрицу К по найденным индексам.)


Вот ф-я F
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
void f(int k, int n, int &i, int &j)
{
   if (n==1)
   {
      i=0;
      j=0;
      return;
   }
 
   if (k<(n*4-4))                       
   {
      if (k<n)                           
      {
         i=0;
         j=k;
      }
      else 
        if (k<(n*2-1))                    
        {
           i = k - n + 1;
           j = n-1;
        }
        else 
          if (k < (n*3-2))               
          {
             i = n - 1;
             j = n*3-3 - k;
          }
          else                            
          {
             i = n*4-4 - k;
             j = 0;
          }
   }
   else                                   
   {
      f(k-(n*4-4), n-2, i, j);
      i++;                          
      j++;
   }
}
вот сортировка вставками
C++
1
2
3
4
5
6
7
8
9
10
11
for (int i=1;i<n;i++)
    {
      int x=a[i];                           
      int j=i; 
      while ((j-1>=0)&&(x<a[j-1]))
      {
        a[j]=a[j-1];                 
        j--;
      }
      a[j]=x;
    }
Вроде бы все просто, но никак не могу додуматься как это сделать

Добавлено через 15 часов 25 минут
Вот сама программа
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
#include <iostream.h>
#include <conio.h>
#include <iomanip.h>
#include <stdlib.h>
#include <ctime>
//ÔóГ*êöèÿ Г°Г*ñ÷èòûâГ*ГҐГІ ïîçèöèþ ýëåìåГ*ГІГ* Гў Г¬Г*òðèöå ГЇГ® Г±ГЇГЁГ°Г*ëè
void f(int k, int n, int &i, int &j)
{
   if (n==1)
   {
      i=0;
      j=0;
      return;
   }
 
   if (k<(n*4-4))                       
   {
      if (k<n)                           
      {
         i=0;
         j=k;
      }
      else 
        if (k<(n*2-1))                    
        {
           i = k - n + 1;
           j = n-1;
        }
        else 
          if (k < (n*3-2))               
          {
             i = n - 1;
             j = n*3-3 - k;
          }
          else                            
          {
             i = n*4-4 - k;
             j = 0;
          }
   }
   else                                   
   {
      f(k-(n*4-4), n-2, i, j);
      i++;                          
      j++;
   }
}
//ô-ÿ ñîðòèðîâêè
int sort(int (*arr)[10],int &n)
{
    for (int k=1;k<n*n;k++)
    { 
      int i,j;
      f(k,n,i,j);  
      int x=arr[i][j];                           //ГўГ±ГІГ*ГўГЄГ* ýëåìåГ*ГІГ* 
      int p=k;
      f(k-1,n,i,j); 
      while ((p-1>=0)&&(x<arr[i][j]))
      { 
        f(k-1,n,i,j);
        int b=arr[i][j]; 
        f(k,n,i,j);    
        arr[i][j]=b;                     
        p--;
        f(k-1,n,i,j);                                    //ñäâèã ýëåìåГ*ГІГ* ГўГЇГ°Г*ГўГ®
      }
      arr[i][j]=x;
    } 
    
}
 
//ГґГіГ*êöèÿ Г§Г*ïîëГ*ГҐГ*ГЁГї Г¬Г*Г±Г±ГЁГўГ* ñëó÷Г*Г©Г*ûìè Г·ГЁГ±Г«Г*ìè
int scan(int (*arr)[10],int n)
{ 
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        arr[i][j]=rand()%100;                       
}
//ГґГіГ*êöìÿ âûâîäГ* Г¬Г*Г±Г±ГЁГўГ*
int print(int (*arr)[10],int n)
{
    for(int i=0;i<n;i++)                       
    {
       for(int j=0;j<n;j++)
         cout<<setw(5)<<arr[i][j];      
       cout<<endl; 
    }          
}
 
int main()
{   
    srand((unsigned)time(NULL));
    int n;
    cout<<"vvedite N (1 <= N <= 10): ";
    cin>>n;
    int arr[n][10];
    cout<<"isxodna9 matrica"<<endl;
    
    scan(arr,n);
    print(arr,n);
    
    cout<<"poluchenna9 matrica"<<endl;
    
    sort(arr,n);
    print(arr,n);
    
    getch();
}
нужно как-то исправить ф-ю sort, чтоб она сортировала по спирали.

Добавлено через 1 час 10 минут
Все я сам написал
кому интересно,вот!
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
#include <iostream.h>
#include <conio.h>
#include <iomanip.h>
#include <stdlib.h>
#include <ctime>
//ÔóГ*êöèÿ Г°Г*ñ÷èòûâГ*ГҐГІ ïîçèöèþ ýëåìåГ*ГІГ* Гў Г¬Г*òðèöå ГЇГ® Г±ГЇГЁГ°Г*ëè
void f(int k, int n, int &i, int &j)
{
   if (n==1)
   {
      i=0;
      j=0;
      return;
   }
 
   if (k<(n*4-4))                       
   {
      if (k<n)                           
      {
         i=0;
         j=k;
      }
      else 
        if (k<(n*2-1))                    
        {
           i = k - n + 1;
           j = n-1;
        }
        else 
          if (k < (n*3-2))               
          {
             i = n - 1;
             j = n*3-3 - k;
          }
          else                            
          {
             i = n*4-4 - k;
             j = 0;
          }
   }
   else                                   
   {
      f(k-(n*4-4), n-2, i, j);
      i++;                          
      j++;
   }
}
//ô-ÿ ñîðòèðîâêè
int sort(int (*arr)[10],int &n)
{
    for (int k=1;k<n*n;k++)
    { 
      int i,j;
      int r=k;
      f(k,n,i,j);  
      int x=arr[i][j];                           //ГўГ±ГІГ*ГўГЄГ* ýëåìåГ*ГІГ* 
      int p=i;
      int q=j;
      f(k-1,n,i,j); 
      while ((r-1>=0)&&(x<arr[i][j]))
      {     
        arr[p][q]=arr[i][j];                     //arr[p][q] = arr[j];arr[i][j] = arr[j-1]        
        r--;
        f(r,n,p,q);
        f(r-1,n,i,j);   
      }
      arr[p][q]=x;
    } 
    
}
 
//ГґГіГ*êöèÿ Г§Г*ïîëГ*ГҐГ*ГЁГї Г¬Г*Г±Г±ГЁГўГ* ñëó÷Г*Г©Г*ûìè Г·ГЁГ±Г«Г*ìè
int scan(int (*arr)[10],int n)
{ 
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        arr[i][j]=rand()%100;                       
}
//ГґГіГ*êöìÿ âûâîäГ* Г¬Г*Г±Г±ГЁГўГ*
int print(int (*arr)[10],int n)
{
    for(int i=0;i<n;i++)                       
    {
       for(int j=0;j<n;j++)
         cout<<setw(5)<<arr[i][j];      
       cout<<endl; 
    }          
}
 
int main()
{   
    srand((unsigned)time(NULL));
    int n;
    cout<<"vvedite N (1 <= N <= 10): ";
    cin>>n;
    int arr[n][10];
    cout<<"isxodna9 matrica"<<endl;
    
    scan(arr,n);
    print(arr,n);
    
    cout<<"poluchenna9 matrica"<<endl;
    
    sort(arr,n);
    print(arr,n);
    
    getch();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.04.2010, 11:57     Сортировка двумерного массива
Посмотрите здесь:

Сортировка двумерного массива C++
Сортировка Двумерного массива C++
Сортировка двумерного массива... C++
Сортировка двумерного массива C++
Сортировка двумерного массива C++
C++ Сортировка двумерного массива
Сортировка двумерного массива C++
сортировка двумерного массива C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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