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

Cортировка массива - C++

Восстановить пароль Регистрация
 
ProRocker
 Аватар для ProRocker
1 / 1 / 0
Регистрация: 20.03.2011
Сообщений: 12
28.11.2011, 22:48     Cортировка массива #1
Здравствуйте! Существует задание:
Дан массив n действительных чисел. Если исходный массив имеет равное количество положительных и отрицательных чисел, создать новый массив, упорядочив исходный массив следующим образом. Первыми идут два максимальных элемента, затем два минимальных; далее два максимальных и два минимальных из оставшихся и т.д..
Преподаватель сказал, что исходный массив трогать запрещает, работать можно только с новым.
Я перенес значения из 1 массива в новый, отсортировал его по убыванию.
Дальше сколько я ни мучаюсь, вывести алгоритм сортировки не выходит никак.
Подскажите пожалуйста этот самый алгоритм.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.11.2011, 22:48     Cортировка массива
Посмотрите здесь:

C++ Cортировка цифр
Cортировка массива. C++
Cортировка символьного двумерного массива по алфавиту C++
Cортировка в файле C++
C++ Cортировка матриц
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alenka-46
16 / 16 / 2
Регистрация: 28.04.2011
Сообщений: 38
28.11.2011, 23:55     Cортировка массива #2
Есть у меня одна идея. Если массив упорядочен, например так
8 8 7 6 5 5 4 4 3 3 2 1
то можно менять местами элементы по четвёркам , например запомнить элементы a[i] и a[i+1] во вспомогательных переменных r1 и r2, потом записать на их месте элементы a[i+2] a[i+3], и потом записать переменные a[i] a[i+1] в конец, делать всё это в цикле for c шагом в 4. Сейчас попробую написать кусочек программы

Добавлено через 21 минуту
Хотя нет, немного не тот случай.
Если массив не упорядочен, например так 8 9 5 9 4 7 8 1, то можно
проверять массив с конца, и затем поменять местами предпредпоследний и предпоследний 7 и 8, потом предпоследний и последний 7 и 1, потом изменить переключатель с минус единицы на единицу и потом переставлять элементы снова, только уже минимальные. Сейчас попробую написать кусочек программы

Добавлено через 8 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for(j=n-1; j>0; j-=2)
{
   if(flag==1)
     {
         if(a[j-1] > a[j-2] ) 
            меняем местами
         if(a[j] > a[j-1] ) 
            меняем местами
         if(a[j-1] > a[j-2] ) 
            меняем местами
     }
   else
     {
         if(a[j-1] < a[j-2] ) 
            меняем местами
         if(a[j] < a[j-1] ) 
            меняем местами
         if(a[j-1] < a[j-2] ) 
            меняем местами
     }
 
    flag*= (-1);
}
ProRocker
 Аватар для ProRocker
1 / 1 / 0
Регистрация: 20.03.2011
Сообщений: 12
29.11.2011, 09:55  [ТС]     Cортировка массива #3
alenka-46, к сожалению, работает неправильно.
Я все-таки считал что после сортировке оно легче должно делаться то... Только не могу понять как.
shtefeek
5 / 5 / 0
Регистрация: 30.10.2010
Сообщений: 22
29.11.2011, 18:23     Cортировка массива #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
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
int main(int argc, char *argv[])
{   int n;
    printf("Enter n - ");
    scanf("%d",&n);
    int a[n],s,b[n],swap,i,c=0,tmp,otr=0,pol=0,l,k;
    l=0;
    s=n;
    k=n/2;
    for (i=0;i<n;i++)
    {
        printf("a[%d]=",i);
        scanf("%d",&a[i]);
    }
    for (i=0;i<n;i++)
    {
        if(a[i]<0)
        otr++;
        if(a[i]>0)
        pol++;
    }
    if(otr==pol)
    {
                 do
      {
       swap=0;
              for (i=0;i<n-1;i++) 
             {
                 if (a[i]>a[i+1])
                 {
                                 tmp=a[i];      
                                 a[i]=a[i+1];   
                                 a[i+1]=tmp;    
                                 swap++;       
                    }
             }           
        
    }
    while(swap!=0);
    }
    else
    {
        printf("Error!\n");
        system("PAUSE");
    return EXIT_SUCCESS;
    }           
    printf("\n");
    while (k!=0)
    {
    b[c]=a[n-1];
    b[c+1]=a[n-2];
    b[c+2]=a[c];
    b[c+3]=a[c+1];
    c+=4;
    n-=2;
    k--;
    }
    for (i=0;i<s;i++)
    {
        printf("%d ",b[i]);
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}
alenka-46
16 / 16 / 2
Регистрация: 28.04.2011
Сообщений: 38
29.11.2011, 18:34     Cортировка массива #5
Попробуйте проверить такую программу, я её немножко доработала
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
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
 
void main()
{
   clrscr();
   int i, j, k,   // счётчики для циклов
       r,         // дополнительная переменная для перестановки элементов массива
       n,         // длина массива
       flag=-1; // переменная для смены минимума на максимум
 
// просим пользователя ввести размер массива
   cout <<"\n \n   Введите количество элементов массива : ";
   cin >> n;
 
// создаём динамический массив нужной длины 
   int *a=new int [n];
 
//просим пользователя ввести элементы массива
   for(i=0; i<n; i++)
   {
      cout <<"\n Введите " <<i+1 <<" элемент массива : ";
      cin >> a[i];
   }
 
   clrscr(); // очистка экрана
 
// печать начального массива   
   cout << "\n Начальный массив : ";
   for(i=0; i<n; i++)
      cout <<a[i] << " ";
 
// сам алгоритм перестановки  
   for(i=0; i<n-1; i+=2) // переставляем пару минимумов или максимумов в начало в цикле
  {
   if( flag == 1)                 //  если нужно переместить в начало максимумы 
   for( j = n-1; j > i+1; j--) // проверяем все элементы левее i до конца массива
   {
       if( a[j-1] > a[j-2] )    // сравниваем первый и второй элемент в тройке чисел
         {
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=a[j-1];
         }
         if( a[j] > a[j-1] ) // сравниваем второй и третий элемент в тройке чисел
         {
           r=a[j];
           a[j]=a[j-1];
           a[j-1]=a[j];
         }
         if( a[j-1] > a[j-2] ) // снова сравниваем первый и второй элемент в тройке чисел,
         {                         // так как второй и третий могли быть переставлены
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=a[j-1];
         }
   }
   else                            // если нужно перенести в начало цикла пару минимумов,
   for( j = n-1; j > i+1; j--)// то делаем почти тоже самое (только в циклах if поменялся знак) 
  {
      if( a[j-1] < a[j-2] )
         {
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=a[j-1];
         }
         if( a[j] < a[j-1] )
         {
           r=a[j];
           a[j]=a[j-1];
           a[j-1]=a[j];
         }
         if( a[j-1] < a[j-2] )
         {
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=a[j-1];
         } 
   }
   // печатаем получившийся результат после одной перестановки
   cout << " \n  i= " <<i  <<" flag=" <<flag <<"\t  ";
   for(k=0; k<n; k++)
      cout <<a[k] <<" ";
 
   flag*=(-1); // меняем знак flag , чтобы потом вместо максимума искать минимум и наоборот
   }
 
// печатаем изменённый массив
   cout << "\n\n  Преобразованный массив: ";
   for(i=0; i<n; i++)
      cout <<" " <<a[i];
 
   cout <<"\n\n   Программа завершила свою работу нажмите <Enter>";
   getchar();
}
ProRocker
 Аватар для ProRocker
1 / 1 / 0
Регистрация: 20.03.2011
Сообщений: 12
29.11.2011, 19:43  [ТС]     Cортировка массива #6
Цитата Сообщение от alenka-46 Посмотреть сообщение
Попробуйте проверить такую программу, я её немножко доработала
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
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
 
void main()
{
   clrscr();
   int i, j, k,   // счётчики для циклов
       r,         // дополнительная переменная для перестановки элементов массива
       n,         // длина массива
       flag=-1; // переменная для смены минимума на максимум
 
// просим пользователя ввести размер массива
   cout <<"\n \n   Введите количество элементов массива : ";
   cin >> n;
 
// создаём динамический массив нужной длины 
   int *a=new int [n];
 
//просим пользователя ввести элементы массива
   for(i=0; i<n; i++)
   {
      cout <<"\n Введите " <<i+1 <<" элемент массива : ";
      cin >> a[i];
   }
 
   clrscr(); // очистка экрана
 
// печать начального массива   
   cout << "\n Начальный массив : ";
   for(i=0; i<n; i++)
      cout <<a[i] << " ";
 
// сам алгоритм перестановки  
   for(i=0; i<n-1; i+=2) // переставляем пару минимумов или максимумов в начало в цикле
  {
   if( flag == 1)                 //  если нужно переместить в начало максимумы 
   for( j = n-1; j > i+1; j--) // проверяем все элементы левее i до конца массива
   {
       if( a[j-1] > a[j-2] )    // сравниваем первый и второй элемент в тройке чисел
         {
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=a[j-1];
         }
         if( a[j] > a[j-1] ) // сравниваем второй и третий элемент в тройке чисел
         {
           r=a[j];
           a[j]=a[j-1];
           a[j-1]=a[j];
         }
         if( a[j-1] > a[j-2] ) // снова сравниваем первый и второй элемент в тройке чисел,
         {                         // так как второй и третий могли быть переставлены
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=a[j-1];
         }
   }
   else                            // если нужно перенести в начало цикла пару минимумов,
   for( j = n-1; j > i+1; j--)// то делаем почти тоже самое (только в циклах if поменялся знак) 
  {
      if( a[j-1] < a[j-2] )
         {
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=a[j-1];
         }
         if( a[j] < a[j-1] )
         {
           r=a[j];
           a[j]=a[j-1];
           a[j-1]=a[j];
         }
         if( a[j-1] < a[j-2] )
         {
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=a[j-1];
         } 
   }
   // печатаем получившийся результат после одной перестановки
   cout << " \n  i= " <<i  <<" flag=" <<flag <<"\t  ";
   for(k=0; k<n; k++)
      cout <<a[k] <<" ";
 
   flag*=(-1); // меняем знак flag , чтобы потом вместо максимума искать минимум и наоборот
   }
 
// печатаем изменённый массив
   cout << "\n\n  Преобразованный массив: ";
   for(i=0; i<n; i++)
      cout <<" " <<a[i];
 
   cout <<"\n\n   Программа завершила свою работу нажмите <Enter>";
   getchar();
}
Я, к сожалению, не очень вникал в Ваш код. Решил сначала проверить его работу.
По-моему ни на каких исходных данных он верно не работает. Прилагаю изображение консоли.

Ответьте пожалуйста, Вы сами-то его проверяли? На Ваших данных он работал?
Миниатюры
Cортировка массива  
alenka-46
16 / 16 / 2
Регистрация: 28.04.2011
Сообщений: 38
29.11.2011, 20:31     Cортировка массива #7
В циклах if опечатка, нужно было приравнивать к переменной r
Миниатюры
Cортировка массива  
alenka-46
16 / 16 / 2
Регистрация: 28.04.2011
Сообщений: 38
29.11.2011, 20:34     Cортировка массива #8
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
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
 
void main()
{
   clrscr();
   int i, j, k,   // счётчики для циклов
       r,         // дополнительная переменная для перестановки элементов массива
       n,         // длина массива
       flag=-1; // переменная для смены минимума на максимум
 
// просим пользователя ввести размер массива
   cout <<"\n \n   Введите количество элементов массива : ";
   cin >> n;
 
// создаём динамический массив нужной длины 
   int *a=new int [n];
 
//просим пользователя ввести элементы массива
   for(i=0; i<n; i++)
   {
      cout <<"\n Введите " <<i+1 <<" элемент массива : ";
      cin >> a[i];
   }
 
   clrscr(); // очистка экрана
 
// печать начального массива   
   cout << "\n Начальный массив : ";
   for(i=0; i<n; i++)
      cout <<a[i] << " ";
 
// сам алгоритм перестановки  
   for(i=0; i<n-1; i+=2) // переставляем пару минимумов или максимумов в начало в цикле
  {
   if( flag == 1)                 //  если нужно переместить в начало максимумы 
   for( j = n-1; j > i+1; j--) // проверяем все элементы левее i до конца массива
   {
       if( a[j-1] > a[j-2] )    // сравниваем первый и второй элемент в тройке чисел
         {
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=r;
         }
         if( a[j] > a[j-1] ) // сравниваем второй и третий элемент в тройке чисел
         {
           r=a[j];
           a[j]=a[j-1];
           a[j-1]=r;
         }
         if( a[j-1] > a[j-2] ) // снова сравниваем первый и второй элемент в тройке чисел,
         {                         // так как второй и третий могли быть переставлены
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=r;
         }
   }
   else                            // если нужно перенести в начало цикла пару минимумов,
   for( j = n-1; j > i+1; j--)// то делаем почти тоже самое (только в циклах if поменялся знак) 
  {
      if( a[j-1] < a[j-2] )
         {
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=r;
         }
         if( a[j] < a[j-1] )
         {
           r=a[j];
           a[j]=a[j-1];
           a[j-1]=r;
         }
         if( a[j-1] < a[j-2] )
         {
           r=a[j-1];
           a[j-1]=a[j-2];
           a[j-2]=r;
         } 
   }
   // печатаем получившийся результат после одной перестановки
   cout << " \n  i= " <<i  <<" flag=" <<flag <<"\t  ";
   for(k=0; k<n; k++)
      cout <<a[k] <<" ";
 
   flag*=(-1); // меняем знак flag , чтобы потом вместо максимума искать минимум и наоборот
   }
 
// печатаем изменённый массив
   cout << "\n\n  Преобразованный массив: ";
   for(i=0; i<n; i++)
      cout <<" " <<a[i];
 
   cout <<"\n\n   Программа завершила свою работу нажмите <Enter>";
   getchar();
}
ProRocker
 Аватар для ProRocker
1 / 1 / 0
Регистрация: 20.03.2011
Сообщений: 12
29.11.2011, 20:43  [ТС]     Cортировка массива #9
В 11 строке я полагаю, флаг равен -1?

Добавлено через 29 секунд
То есть он должен быть равен 1.
alenka-46
16 / 16 / 2
Регистрация: 28.04.2011
Сообщений: 38
29.11.2011, 20:43     Cортировка массива #10
Можно поставить 1 - тогда первым выводится максимум, или -1 - тогда первым выводится минимум
ProRocker
 Аватар для ProRocker
1 / 1 / 0
Регистрация: 20.03.2011
Сообщений: 12
29.11.2011, 20:46  [ТС]     Cортировка массива #11
Действительно работает, с инициализацией flag единицей. Спасибо за труды!
shtefeek
5 / 5 / 0
Регистрация: 30.10.2010
Сообщений: 22
29.11.2011, 21:06     Cортировка массива #12
Зачем делать так сложно?
Или я не правильно понял суть задачи?
Миниатюры
Cортировка массива  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.11.2011, 21:18     Cортировка массива
Еще ссылки по теме:

C++ Cортировка динамической матрицы
Cортировка массива. C++
C++ Cортировка записей в массиве

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

Или воспользуйтесь поиском по форуму:
ProRocker
 Аватар для ProRocker
1 / 1 / 0
Регистрация: 20.03.2011
Сообщений: 12
29.11.2011, 21:18  [ТС]     Cортировка массива #13
Цитата Сообщение от shtefeek Посмотреть сообщение
Зачем делать так сложно?
Или я не правильно понял суть задачи?
Правильно понял, сделано очень толсто.
Я сделал путем создания нового массива, посчитал что так меньше всего затрат ресурсов.
А твой вариант я скомпилировать не смог, т.к. работаю в консоли используя cin и cout с отладчиком Visual Studio, не знаком с тем синтаксисом, который ты тут используешь.

Добавлено через 37 секунд
И количество членов в массиве, как я понимаю, должно быть кратно 4.

Добавлено через 6 минут
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
int massl(int n, float* mass, float* newMass)
{
        int answ;
        answ= analyze(n,mass);
        if (answ==0) return 0;
        else
        {
        int i,j;
        float vMass[100];
 
        for (i=0;i<n;i++) 
        {
            newMass[i]=mass[i];
            vMass[i]=mass[i];
        }
        for (i=0;i<n;i++)
            {
                for (j=0;j<n;j++)
                {
                    if (vMass[i]>=vMass[j]) swap(vMass[i],vMass[j]);    
                }
            }
 
    for (i=0;i<n-3;i+=2)
        {
            newMass[i+i]=vMass[i];
            newMass[i+i+1]=vMass[i+1];
            newMass[i+i+2]=vMass[n-i-1];
            newMass[i+i+3]=vMass[n-i-2];
        }
        
        return 1;
    }
}
shtefeek как я вижу тоже использовал 2 массива.
Я думаю, что использую их экономней.

Функция с динамическим распределением памяти:

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
float* massl(int n, float* mass, int& tr)
{
        int answ;
        
        answ = analyze(n,mass);
 
        if (answ==0) 
        {
            tr=0;
            return 0;
        }
        else
        {
        float* newMass;
        float* vMass;
        newMass= new float [n];
        vMass= new float [n];
        int i,j;
 
        for (i=0;i<n;i++) 
        {
            newMass[i]=mass[i];
            vMass[i]=mass[i];
        }
        for (i=0;i<n;i++)
            {
                for (j=0;j<n;j++)
                {
                    if (vMass[i]>=vMass[j]) swap(vMass[i],vMass[j]);    
                }
            }
 
        for (i=0;i<n-3;i+=2)
        {
            newMass[i+i]=vMass[i];
            newMass[i+i+1]=vMass[i+1];
            newMass[i+i+2]=vMass[n-i-1];
            newMass[i+i+3]=vMass[n-i-2];
        }
        tr=1;
        return newMass;
        }
}
Yandex
Объявления
29.11.2011, 21:18     Cортировка массива
Ответ Создать тему
Опции темы

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