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

Быстрая сортировка - C++

Восстановить пароль Регистрация
 
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
26.09.2012, 02:18     Быстрая сортировка #1
Здорова господа!
Есть задачка: дан алгоритм быстрой сортировки.
ну вообщем я ее cделал но ток без указателей.
А задачка находиться в разделе упражнения с указателями.
Наверно нужно использовать в решении указатели, но я чото никак нипайму куда их прилепить
Указатели как то для меня тема новая.
Может кто подскажет куда тут можно влепить указатели.....?

//Задача с книги "Как программировать на с++" Дейтела 8.24//
//Я как бы новичок в с++ недавно учю тока до указателей дошол как то тяжеловато //

Вот код решения без указателей по предложенному алгоритму:
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//Быстрая сортировка
#include <iostream>
using std::cout;
using std::endl;
 
int quicksort(int array[], int nachZnachIndex, int conechZnachIndex);
int partition(int array[],int,int);//вызывается quicksort 
//функция выполняет разбиение массива
 
int main()
{
    int const n=10;
    int array[n]={37,2,6,4,89,8,10,12,68,45};
//  int nachZnachIndex=0;
//  int conechZnachIndex=9;
    
//  cout <<endl<<"***********"<<endl<<partition(array,0,9)<<endl<<"************"<<endl;
    quicksort(array,0,9);
    
    return 0;   
};
 
int quicksort(int array[], int nachZnachIndex, int conechZnachIndex)//сортирует одномерный целочисленный массив
{
    int index=0;
    int nachZnachIndex_P=0,conechZnachIndex_L=0;
    cout <<"It works"<<endl;    
    for(int i=0;i<10;i++)
        cout <<array[i]<<" ";
    cout <<endl;
    cout <<"************************"<<endl;
    index=partition(array,nachZnachIndex,conechZnachIndex);
    nachZnachIndex_P=index+1;
    conechZnachIndex_L=index-1;
    cout <<endl<<"index= "<<index<<endl;
    cout <<"nachZnachIndex_P= "<<nachZnachIndex_P<<endl;
    cout <<"conechZnachIndex_L= "<<conechZnachIndex_L<<endl;
    //шаг рекурсии
    if(conechZnachIndex_L-nachZnachIndex<0)
    {
        cout <<"CONEC"<<endl;
    }
    else
    {
        return quicksort( array,nachZnachIndex,conechZnachIndex_L); 
    }
    
    if(conechZnachIndex-nachZnachIndex_P<0)
    {
        cout <<"CONEC"<<endl;   
    }
    else
    {
        return quicksort(array,nachZnachIndex_P,conechZnachIndex);  
    }
    
    
    /*if(0==conechZnachIndex_L)
    {
        cout <<"konec"<<endl;
        //return array;
    }
    else 
    {
        cout <<"kkkkk"<<endl;
        return quicksort( array,nachZnachIndex,conechZnachIndex_L);
    }
    
    if(nachZnachIndex_P=conechZnachIndex)
    {
        cout <<"konec"<<endl;   
    }
    else
    {
        return quicksort(array,nachZnachIndex_P,conechZnachIndex);  
    }*/
    cout <<endl<<endl<<endl<<"***********************************"
    <<endl<<"**********************************"<<endl;
    for(int i=0;i<10;i++)
        cout <<array[i]<<" ";
    cout <<endl;
}
 
 
int partition(int array[],int nach, int conec)//выполняет разбиение массива (скорее всего на 2массива) и возвращает индек массива где установлен элемент
{
    int ind=nach;//индекс первого элемента вначале равен 0
    int k=1;//флаг выхода из цикла
    int l=0,r=0;//индексы справа слева
    cout <<"nach= "<<nach<<endl<<"conec= "<<conec<<endl<<"ind= "<<ind<<endl;
    while(k!=3)
    {
        for(int i=conec;(i>=nach)and(k==1);i--)
        {
            cout <<"array["<<ind<<"]= "<<array[ind]<<endl<<"array["<<i<<"]= "<<array[i]<<endl<<endl;
            if(array[ind]>array[i])
            {
                cout <<"fkjasldfjsa;l************";
                int b=array[i];
                array[i]=array[ind];
                array[ind]=b;
                ind=i;
                conec=i;
                k=2;
                break;
            }
            else if(array[ind]==array[i])
            {
            //  cout <<"1Элемент на своем месте"<<endl;
                k=3;
                break;
            }
        }
        
        for(int i=nach;(i<=conec)and(k==2);i++)
        {
            if(array[ind]<array[i])
            {
                int b=array[i];
                array[i]=array[ind];
                array[ind]=b;
                ind=i;
                nach=i;
                k=1;
                break;
            }
            else if(array[ind]==array[i])
            {
            //  cout <<"2Элемент на своем месте"<<endl;
                k=3;
                break;
            }
        }
    //  k=3;
    }
    for(int i=0;i<10;i++)
        cout <<array[i]<<" ";
    cout <<endl;
    
//  cout <<"nach= "<<nach<<endl<<"conec= "<<conec<<endl;
    return ind;
        
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
26.09.2012, 02:30     Быстрая сортировка #2
int array[] - это и есть указатель.
т.е. можно было записать int* array
делайте следующее задание)

хотя наверное требуется следующее:
передавать только два параметра - указатель на начало и на конец.
т.е. вместо
int array[], int nachZnachIndex, int conechZnachIndex
будет
int* nachZnachIndex, int* conechZnachIndex
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
26.09.2012, 02:47  [ТС]     Быстрая сортировка #3
передавать только два параметра - указатель на начало и на конец.
т.е. вместо
int array[], int nachZnachIndex, int conechZnachIndex
будет
int* nachZnachIndex, int* conechZnachIndex
А как массив попадет в функцию если я два параметра тока передам?
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
26.09.2012, 02:56     Быстрая сортировка #4
int* nachZnachIndex - это указатель на какой-то элемент в массиве.
nachZnachIndex+1 - это указатель на следующий элемент
и тд.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
29.09.2012, 00:39  [ТС]     Быстрая сортировка #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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//Быстрая сортировка
#include <iostream>
using std::cout;
using std::endl;
 
//int quicksort(int array[], int nachZnachIndex, int conechZnachIndex);
int quicksort(int[],int,int);
int *partition(int*,int*);//вызывается quicksort 
//функция выполняет разбиение массива
 
int main()
{
    int const n=10;
    int array[n]={37,2,6,4,89,8,10,12,68,45};
//  int array[n]={8, 2 ,6, 4, 10, 12, 37, 89, 68, 45 };
    int *pArray;
    pArray=array;
//  int nachZnachIndex=0;
//  int conechZnachIndex=9;
//  cout <<"pArray= "<<pArray<<endl<<"array= "<<array<<endl;
    
//  cout <<"*(pArray+1)= "<<*pArray<<endl<<"array[1]= "<<array[0]<<endl;
    
//  cout <<endl<<"***********"<<endl<<*partition(pArray,(pArray+9))<<endl<<"************"<<endl;
    quicksort(pArray,0,9);
//cout <<endl<<endl<<*(pArray+9-3)<<endl<<endl;
    for(int i=0;i<10;i++)
        cout <<array[i]<<" ";
    cout <<endl;     
    return 0;   
};                                                               
                            
int quicksort(int pArray[],int nachZnachIndex, int conechZnachIndex)//сортирует одномерный целочисленный массив
{                 
    int* pNachZnachIndex;
    int* pConechZnachIndex;
    int* index;
    int nachZnachIndex_R;
    int conechZnachIndex_L;
    int adrIndex;
    pNachZnachIndex=pArray+nachZnachIndex;
    pConechZnachIndex=pArray+conechZnachIndex;
//  cout <<endl<<*pNachZnachIndex<<"  "<<*pConechZnachIndex<<endl;
 
    index=partition(pNachZnachIndex,pConechZnachIndex);
    cout <<endl<<"***"<<endl<<"*index= "<<*index<<endl<<"***"<<endl;
    //cout <<*pArray<<endl;
    for(int i=nachZnachIndex;i<=conechZnachIndex;i++)
    {
        if(pArray+i==index)
            adrIndex=i;
    }
    cout <<"adrIndex= "<<adrIndex<<endl;
    cout <<endl<<"pArray[adrIndex]= "<<pArray[adrIndex]<<endl;
    //условие
    nachZnachIndex_R=adrIndex+1;
    conechZnachIndex_L=adrIndex-1;
    cout <<endl<<"nachZnachIndex_R= "<<nachZnachIndex_R<<endl
    <<"nachZnachIndex_L= "<<conechZnachIndex_L<<endl;
    if(nachZnachIndex-conechZnachIndex_L<0)
        quicksort(pArray,nachZnachIndex,conechZnachIndex_L);
    if(nachZnachIndex_R-conechZnachIndex<0)
        quicksort(pArray,nachZnachIndex_R,conechZnachIndex);
    
/*  int *index;        
    int *index1;              
    index1=index=partition(nachZnachIndex,conechZnachIndex);//vozvrachaet adres delitel9 masiva
cout <<" *conechZnachIndex= "<<*conechZnachIndex<<" *index= "<<*index<<endl;
    
                  
    if(nachZnachIndex!=index-1&&nachZnachIndex!=index)
        return quicksort(nachZnachIndex,index-1);
 
cout <<" *conechZnachIndex= "<<*conechZnachIndex<<" *index= "<<*index<<" *index1= "<<*index1<<endl; 
    if(conechZnachIndex!=index+1&&conechZnachIndex!=index)
        return quicksort(index+1,conechZnachIndex);
    */
 
}
 
 
int *partition(int *nach, int *conec)//выполняет разбиение массива (скорее всего на 2массива) и возвращает индек массива где установлен элемент
{
    cout <<"*nach= "<<*nach<<"  *conec= "<<*conec<<endl;
    int k=1;
    while(k!=3)
    { 
        for(;(k==1);conec--)
        { 
            if(*nach>*conec)
            {
                int b=*nach;
                *nach=*conec;
                *conec=b;
                k=2; 
                break;
            }    
            else if(nach==conec)
            {
            //  cout <<"1Элемент на своем месте"<<endl;
                k=3;   
            //  cout <<endl<<"kk= "<<kk<<endl;
                //return kk;
                return nach;
                break;
            }
        }
        cout <<"*conec= "<<*conec<<"  *nach= "<<*nach<<endl;
        for(;(k==2);nach++)    
        {
            if(*nach>*conec)
            {            
                int b=*nach;
                *nach=*conec;
                *conec=b;
                k=1;
                break;
            }
            else if(nach==conec)
            {
            //  cout <<"2Элемент на своем месте"<<endl;
                k=3;  
                //return kk2;
                return nach;
                break;
            }
        }
        //k=3;
           
    }       
}
С указателями вроде более менее разобрался
Yandex
Объявления
29.09.2012, 00:39     Быстрая сортировка
Ответ Создать тему
Опции темы

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