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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.63
isgat
0 / 0 / 0
Регистрация: 18.11.2010
Сообщений: 17
#1

Сортировка массива за один проход - C++

19.11.2010, 19:04. Просмотров 3087. Ответов 10
Метки нет (Все метки)

Помогите. Нужно отсортировать массив так, чтобы справа были отрицательные, слева положительные и нули посередине. При этом (!) нужно сделать все за один проход по массиву. Вообще не могу додуматься.

Добавлено через 23 часа 53 минуты
огромное спасибо) блин) хоть бы идею подкинули
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.11.2010, 19:04     Сортировка массива за один проход
Посмотрите здесь:
Сортировка в один проход по нескольким полям C++
Функция которая переворачивает список за один проход C++
Реверс элементов в односвязанном списке за один проход C++
C++ Метод поиска по массиву уникальных чисел за один проход
Найти все бракованные изделия на конвейере за один проход робота-контролера C++
C++ Как считывать только одно число типа double за один проход
C++ Алгоритм поиска неравного числа за один проход, в наборе из 4 чисел, где 3 равные между собой
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2010, 19:46     Сортировка массива за один проход #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
#include <iostream>
using namespace std;
void func(int *mas, int N)
{
        int l=0, r=N-1, i;
        while(l<r)
        {
                for(i=l; i<N; i++)
                        if(mas[i]<=0)
                                break;
                l=i;
                for(i=r; i>=0; i--)
                        if(mas[i]>=0)
                                break;
                r=i;
                if(l<r)
                {
                        int temp=mas[l]; mas[l]=mas[r]; mas[r]=temp;
                }
        }
}
 
int main()
{
        int *mas, N, i;
        cout<<"Razmer mas=";
        cin>>N;
        mas=new int[N];
        for(i=0;i<N;i++)
        {
            cout<<"["<<i<<"]= ";
            cin>>mas[i];
        }
        func(mas, N);
        cout<<endl<<"Res:"<<endl;
        for(i=0; i<N; i++)
            cout<<mas[i]<<" ";
        cout<<endl;
        return 0;
 
}
odip
Эксперт С++
7156 / 3296 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
19.11.2010, 19:55     Сортировка массива за один проход #3
два указателя
один - слева массива
другой - справа массива
далее указатели бегут навстречу друг другу
задача - чтобы слева были все положительные, справа все отрицательные, нули пропускаем
потом в конце посчитаем столько нулей и запишем их в середину массива
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2010, 19:57     Сортировка массива за один проход #4
isgat, В моем коде кстати один недостаток: при кол-ве 0 более 1 зависает.
Про нули лучше сделать как написал odip
odip
Эксперт С++
7156 / 3296 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
19.11.2010, 20:03     Сортировка массива за один проход #5
Мда - надо 4 указателя
Два бегут навстречу друг другу
А еще два слева и справа указывают куда нужно писать
Это нужно чтобы пропускать нули
Нули просто перезаписываем
Когда первые два указателя дойдут друг до друга
то все что будет между двумя другими указателями надо забить нулями
( тут может быть ситуация что эти два других уже встали рядом !
то есть нулей фактически нету )
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2010, 20:22     Сортировка массива за один проход #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
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
#include <iostream>
using namespace std;
void func(int *mas, int N)
{
        int l=0, r=N-1, i, temp;
        bool fl=true;
        while(l<r && fl)
        {
            fl=false;
                for(i=l; i<N; i++)
                        if(mas[i]<=0)
                        {
                            if(mas[i]<0)
                                fl=true;
                                break;
                        }
                l=i;
                for(i=r; i>=0; i--)
                        if(mas[i]>=0)
                        {
                            if(mas[i]>0)
                                fl=true;
                                break;
                        }
                r=i;
                if(mas[l]==0 && mas[r]==0)
                {
                    for(i=l+1; mas[l]==0 && i<r; i++)
                        if(mas[i]<0)
                        {
                            temp=mas[l]; mas[l]=mas[i]; mas[i]=temp; fl=true;
                        }
                    if(mas[l]==0)
                    {
                        for(i=l+1; mas[r]==0 && i<r; i++)
                            if(mas>0)
                            {temp=mas[r]; mas[r]=mas[i]; mas[i]=temp; fl=true;
                            }
                    }
                }
                for(i=l; i<=r; i++)
                    if(mas[i]!=0)
                        fl=true;
                if(l<r)
                {
                        temp=mas[l]; mas[l]=mas[r]; mas[r]=temp;
                }
        }
}
 
int main()
{
        int *mas, N, i;
        cout<<"Razmer mas=";
        cin>>N;
        mas=new int[N];
        for(i=0;i<N;i++)
        {
            cout<<"["<<i<<"]= ";
            cin>>mas[i];
        }
        func(mas, N);
        cout<<endl<<"Res:"<<endl;
        for(i=0; i<N; i++)
            cout<<mas[i]<<" ";
        cout<<endl;
        return 0;
 
}
odip
Эксперт С++
7156 / 3296 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
20.11.2010, 14:22     Сортировка массива за один проход #7
А вот теперь я не уверен что этот код делает все за один проход !
В строках 28 и 35 идут некие вложенные циклы
Это про код выше
odip
Эксперт С++
7156 / 3296 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
20.11.2010, 14:46     Сортировка массива за один проход #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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
 
void sort( int n, int *parr );
 
#define N 10
 
#define random( arg_a, arg_b )  ( (arg_a)+rand()%((arg_b)-(arg_a)+1) )
 
int main( void ) {
    
int i;
int arr[N];
 
srand( time( NULL ) );
for ( i= 0; i<N; i++ ) { arr[i]= random( -5, +5 ); }
 
for ( i= 0; i<N; i++ ) { printf( " %d", arr[i] ); }
printf( "\n" );
 
sort( N, arr );
 
for ( i= 0; i<N; i++ ) { printf( " %d", arr[i] ); }
printf( "\n" );
 
return 0;
 
} /* main() */
 
 
void sort( int n, int *parr ) {
 
int p1, s1, p2, s2;
int val;
 
 
p1= s1= 0;
p2= s2= n-1;
 
for ( ; ; ) {
 
    for ( ; ; ) {
        if ( p1>p2 ) { goto ret_all; }
        if ( parr[p1]>0 ) {
            parr[s1]= parr[p1];
            s1++; p1++;
        } else if ( parr[p1] == 0 ) {
            p1++;
        } else { /* parr[p1]<0 */
            break;
        }
    }
 
    for ( ; ; ) {
        if ( p1>p2 ) { goto ret_all; }
        if ( parr[p2]<0 ) {
            parr[s2]= parr[p2];
            s2--; p2--;
        } else if ( parr[p2] == 0 ) {
            p2--;
        } else { /* parr[p2]>0 */
            break;
        }
    } 
 
    val= parr[p1]; parr[s1]= parr[p2]; parr[s2]= val;
    s1++; p1++;
    s2--; p2--;
    
}
 
ret_all:
for ( ; s1<=s2; s1++ ) { parr[s1]= 0; }
 
} /* sort() */
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.11.2010, 16:41     Сортировка массива за один проход #9
А вот теперь я не уверен что этот код делает все за один проход !
В строках 28 и 35 идут некие вложенные циклы
Это про код выше.

odip, Один в один как и у Вас код, ни больше ни меньше.

Добавлено через 12 минут
А вот теперь я не уверен что этот код делает все за один проход !
В строках 28 и 35 идут некие вложенные циклы
Это про код выше.
, е
Я уверен, что за один проход. На самом деле там (в коде) если встретился элемент равный 0, то ищется возможная замена в середине на элемент не равный 0.
Серединой называю еще не отсортированный интервал в середине массива.
odip
Эксперт С++
7156 / 3296 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
20.11.2010, 21:15     Сортировка массива за один проход #10
На самом деле там (в коде) если встретился элемент равный 0, то ищется возможная замена в середине на элемент не равный 0.
Ну я-то в своем коде так не делаю
В самом конец просто забиваю нулями середину массива ( где должны быть нули )
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2010, 21:59     Сортировка массива за один проход
Еще ссылки по теме:
Проход массива с двух концов C++
C++ Если елементы массива соседние одинаковы то один из них заменяется на 0 а другой увеличиваетмя на один
Создать 2 массива и функцию, соединяющую эти два массива в один C++
C++ Из одного массива сделать два массива, в один перенести четные элементы, в другой нечетные
Дан массив A[20] и B[10] после каждой пары элемента массива A вставить один элемент массива B C++

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

Или воспользуйтесь поиском по форуму:
isgat
0 / 0 / 0
Регистрация: 18.11.2010
Сообщений: 17
20.11.2010, 21:59  [ТС]     Сортировка массива за один проход #11
Всем спасибо, программу сдал, в итоге все что вы написали я не использовал, точнее похожее есть, но написал раньше чем вы опубликовали. (Кстати нужно было на Си, но не принципиально)
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
//Программа генерирует массив случайного размера из диапазона [40,80], и заполняет числами из диапазона [-5,8],
//при этом положительные расположены в правой части массива, отрицательные слева.
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
//Главная функция
int main(){ 
    srand ((unsigned)time(NULL));
    int *a,  //Динамический массив
        k,   //Индекс элемента с которого должны стоять нули 
        size,//Размер массива
        j,i, // Счетчики
        tmp, //Временная переменная для сортировки
        n=0; //Кол-во положительных элементов
 
printf("Programma generiryet massiv sluchainogo razmera [40,80],\ni zapolnyaet chislami [-5,8].\n\n\n");
 
//Генерация размера массива
    size= 40 + rand() % 40;
    a=(int*)malloc(size*sizeof(int));
 
//Заполнение массива случайными числами
    printf ("Ishodnyi massiv");
 
    for (i=0; i < size; i++){
        a[i]= -5 + rand() % 13;
        printf ("\nA[%d] =\t %2.1d", i, a[i]);
        if (a[i]>0) n+=1;
    }
 
//Сортировка массива
    i=0;
    j=size-1;
    k=n;
    while (i!=n) { 
           if (a[i]==0) 
                { 
                a[i]=a[k];
                a[k]=0;
                k+=1;
                }
           if (a[i] < 0) {
                if (a[j]==0) 
                { 
                    a[j]=a[k];
                    a[k]=0;
                    k+=1;
                }
                if (a[j]>0) 
                {
                    tmp=a[i];
                    a[i]=a[j];
                    a[j]=tmp;
                    j-=1;
                    i+=1;
                }
                if (a[j]<0) j-=1;
           }
           if (a[i]>0) i+=1;
 
    }
 
printf ("\n\n______________________\n");
 
//Вывод отсортированного массива
        printf ("Otsortirovannyi massiv\n");
        for (i=0; i < size; i++){
            printf ("\nA[%d] =\t %2.1d", i, a[i]);
        }
printf ("\n\n\n");
    return 0;
}
Yandex
Объявления
20.11.2010, 21:59     Сортировка массива за один проход
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru