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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.63
isgat
0 / 0 / 0
Регистрация: 18.11.2010
Сообщений: 17
19.11.2010, 19:04     Сортировка массива за один проход #1
Помогите. Нужно отсортировать массив так, чтобы справа были отрицательные, слева положительные и нули посередине. При этом (!) нужно сделать все за один проход по массиву. Вообще не могу додуматься.

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

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива C++
Дан массив A[20] и B[10] после каждой пары элемента массива A вставить один элемент массива B C++
C++ Если елементы массива соседние одинаковы то один из них заменяется на 0 а другой увеличиваетмя на один
Сортировка массива. Ошибка после ввода размерности массива C++
C++ Метод поиска по массиву уникальных чисел за один проход
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
19.11.2010, 19:55     Сортировка массива за один проход #3
два указателя
один - слева массива
другой - справа массива
далее указатели бегут навстречу друг другу
задача - чтобы слева были все положительные, справа все отрицательные, нули пропускаем
потом в конце посчитаем столько нулей и запишем их в середину массива
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2010, 19:57     Сортировка массива за один проход #4
isgat, В моем коде кстати один недостаток: при кол-ве 0 более 1 зависает.
Про нули лучше сделать как написал odip
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
19.11.2010, 20:03     Сортировка массива за один проход #5
Мда - надо 4 указателя
Два бегут навстречу друг другу
А еще два слева и справа указывают куда нужно писать
Это нужно чтобы пропускать нули
Нули просто перезаписываем
Когда первые два указателя дойдут друг до друга
то все что будет между двумя другими указателями надо забить нулями
( тут может быть ситуация что эти два других уже встали рядом !
то есть нулей фактически нету )
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
20.11.2010, 14:22     Сортировка массива за один проход #7
А вот теперь я не уверен что этот код делает все за один проход !
В строках 28 и 35 идут некие вложенные циклы
Это про код выше
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
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++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.11.2010, 16:41     Сортировка массива за один проход #9
А вот теперь я не уверен что этот код делает все за один проход !
В строках 28 и 35 идут некие вложенные циклы
Это про код выше.

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

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

Функция которая переворачивает список за один проход C++
Реверс элементов в односвязанном списке за один проход C++
C++ Как считывать только одно число типа double за один проход

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

Или воспользуйтесь поиском по форуму:
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     Сортировка массива за один проход
Ответ Создать тему
Опции темы

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