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

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

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

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

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

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

Добавлено через 23 часа 53 минуты
огромное спасибо) блин) хоть бы идею подкинули
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.11.2010, 19:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка массива за один проход (C++):

Сортировка в один проход по нескольким полям - C++
Добрый вечер, #include <iostream> #include <ctime> #include <vector> #include <algorithm> using namespace std; class...

Функция которая переворачивает список за один проход - C++
Написала функцию. Эта функция переворачивает список за один проход. Создаю новый список и в него поочередно записываю элементы,но в другом...

Реверс элементов в односвязанном списке за один проход - C++
Добрый день! Есть структура, представляющая из себя односвязный список. Как можно изменить порядок элементов на обратный в этом списке за...

Метод поиска по массиву уникальных чисел за один проход - C++
Подскажите какой-нибудь интересный метод поиска по массиву для данного случая: Есть массив {1, 1, 2, 3, 3}; Надо найти неповторяющееся...

Как считывать только одно число типа double за один проход - C++
Теперь измените тело цикла так, чтобы он считывал только одно число типа double за один проход. Определите две переменные, чтобы...

Найти все бракованные изделия на конвейере за один проход робота-контролера - C++
Всем добрый вечер! Вот попалась такая задача: на конвейере по производству телефонов работает робот-контролер. Он идет вдоль конвейера...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 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;
 
}
1
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
19.11.2010, 19:55 #3
два указателя
один - слева массива
другой - справа массива
далее указатели бегут навстречу друг другу
задача - чтобы слева были все положительные, справа все отрицательные, нули пропускаем
потом в конце посчитаем столько нулей и запишем их в середину массива
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2010, 19:57 #4
isgat, В моем коде кстати один недостаток: при кол-ве 0 более 1 зависает.
Про нули лучше сделать как написал odip
0
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
19.11.2010, 20:03 #5
Мда - надо 4 указателя
Два бегут навстречу друг другу
А еще два слева и справа указывают куда нужно писать
Это нужно чтобы пропускать нули
Нули просто перезаписываем
Когда первые два указателя дойдут друг до друга
то все что будет между двумя другими указателями надо забить нулями
( тут может быть ситуация что эти два других уже встали рядом !
то есть нулей фактически нету )
1
valeriikozlov
Эксперт C++
4670 / 2496 / 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;
 
}
0
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
20.11.2010, 14:22 #7
А вот теперь я не уверен что этот код делает все за один проход !
В строках 28 и 35 идут некие вложенные циклы
Это про код выше
0
odip
Эксперт С++
7157 / 3297 / 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() */
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.11.2010, 16:41 #9
А вот теперь я не уверен что этот код делает все за один проход !
В строках 28 и 35 идут некие вложенные циклы
Это про код выше.

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

Добавлено через 12 минут
А вот теперь я не уверен что этот код делает все за один проход !
В строках 28 и 35 идут некие вложенные циклы
Это про код выше.
, е
Я уверен, что за один проход. На самом деле там (в коде) если встретился элемент равный 0, то ищется возможная замена в середине на элемент не равный 0.
Серединой называю еще не отсортированный интервал в середине массива.
0
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
20.11.2010, 21:15 #10
На самом деле там (в коде) если встретился элемент равный 0, то ищется возможная замена в середине на элемент не равный 0.
Ну я-то в своем коде так не делаю
В самом конец просто забиваю нулями середину массива ( где должны быть нули )
0
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;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2010, 21:59
Привет! Вот еще темы с ответами:

Алгоритм поиска неравного числа за один проход, в наборе из 4 чисел, где 3 равные между собой - C++
Дорогие мои земляки! Помогите зеленому. Подскажите как с использованием минимального количества условных операторов найти из 4 чисел,...

Проход массива с двух концов - C++
Подскажите, как пройтись с двух концов строки в двухмерном массиве: //Функция для первого задания, которая заполняет...

Если елементы массива соседние одинаковы то один из них заменяется на 0 а другой увеличиваетмя на один - C++
#include &quot;stdafx.h&quot; #include&lt;string&gt; #include &lt;cmath&gt; #include &lt;iostream&gt; #include&lt;locale&gt; using namespace std; const int...

Сортировка через один - C++
Напишите программу, которая сортирует по возрастанию все элементы массива с нечётными номерами. При этом все элементы с чётными номерами...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
20.11.2010, 21:59
Ответ Создать тему
Опции темы

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