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

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

Войти
Регистрация
Восстановить пароль
 
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
#1

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

26.09.2012, 02:18. Просмотров 717. Ответов 4
Метки нет (Все метки)

Здорова господа!
Есть задачка: дан алгоритм быстрой сортировки.
ну вообщем я ее 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;
        
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.09.2012, 02:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрая сортировка (C++):

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) - C++
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий...

Быстрая сортировка (сортировка методом Хоара) - C++
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные элементы в порядке убывания. Вывести массивы до и после...

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

Сортировка расчёской и быстрая сортировка - C++
В файле in.txt записана последовательность целых чисел. Заданными методами отсортировать числа и записать в файлы out1.txt и out2.txt....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
26.09.2012, 02:47  [ТС] #3
передавать только два параметра - указатель на начало и на конец.
т.е. вместо
int array[], int nachZnachIndex, int conechZnachIndex
будет
int* nachZnachIndex, int* conechZnachIndex
А как массив попадет в функцию если я два параметра тока передам?
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
26.09.2012, 02:56 #4
int* nachZnachIndex - это указатель на какой-то элемент в массиве.
nachZnachIndex+1 - это указатель на следующий элемент
и тд.
1
ninja2
231 / 187 / 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;
           
    }       
}
С указателями вроде более менее разобрался
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.09.2012, 00:39
Привет! Вот еще темы с ответами:

Быстрая сортировка - C++
Читал о быстрой сортировки смысл понятен но не могу понять некоторые моменты. Каким образом работают два последних условия? Они работают...

Быстрая сортировка - C++
Помогите пожалуйста, при использовании алгоритма быстрой сортировки, конечный массив получается не отсортированным, хотя все операции...

Быстрая сортировка - C++
Задача: пользователь задает количество элементов массива (макс. - 500 000), вводит их, затем задает количество запросов (макс. - 10000) и...

Быстрая сортировка - C++
Дошёл до темы быстрой сортировки, набрал код, начал компилировать. Что-то странно, всё написано правильно, уже проверял, 8 раз, программа...


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

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

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