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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
#1

Прокоментировать 2 строки по сортировке - C++

22.09.2009, 19:05. Просмотров 1711. Ответов 31
Метки нет (Все метки)

Разбираю код быстрой сортировки, вот исходник
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
#include <iostream>
using namespace std;
 
//создается шаблнная функция
template<class T> 
// функция принимает аргументы: 
// массив (так как функция шаблонная, то любого типа массив), и кол-во элементов массива.
void quickSortR(T* a, long N) 
{
    long i = 0, j = N;
    // T - это тип передаваемого массива
    // создаем две перменных этого типа
    T temp, p;
 
     // т.е. фактически мы присвоили перменной значение центрального элемента массива
    p = a[ N>>1 ];
 
    // процедура разделения (разделяет массив на подмассивы)
 
    do {
         // Положить p равным числу, которое находится посередине массива
        while ( a[i] < p ) i++;  
        while ( a[j] > p ) j--;  
 
        if (i <= j) 
        {
            // обмен местами элементов a[i] с a[j] 
            // то есть, то что было в a[i] станет в a[j]
            // а то, что было в a[j] станет в a[i]
            temp = a[i]; a[i] = a[j]; a[j] = temp; 
            i++; j--;
        }
    } while ( i<=j );
 
    if ( j > 0 ) quickSortR(a, j); 
    if ( N > i ) quickSortR(a+i, N-i); 
   
    
}
// ------------------------------------------------------------------------------
int main()
  setlocale(LC_ALL, "Russian");   // создаем массив символов
    char str[] = "бвгда";
    // сортируем массив символов
    quickSortR(str, strlen(str));
    // выводим на экран отсортированный массив симовлов
    cout << str <<  endl;
    // создаем целочисленный массив
    int a[] = { 2, 5, 1, 20, 8, 0, 9 };
    // сортируем целочисленный массив
    quickSortR(a, 6);
    // выводим на экран отсортированный целочисленный массив
    for(int i = 0; i < 7; i++)
        cout << a[i] << " ";
    cout <<  endl;
    
    system("pause"); 
    return 0; // функция main ДОЛЖНА возвращать число
}

Не ясно вот это:

Вот смотрите,строка:
C++
1
while ( a[i] < p ) i++;
Этим мы производим сравнение каждого элемента масива с серединой масива, выполняя замену,тоесть числа,меньшие середины масива, переходят в левую сторону. Но вот эта строка:

C++
1
while ( a[j] > p ) j--;
Происходит сравнение общего количества элементов масива с серединой масива. Тоесть если масив сосстоит из 6 элементов,тогда будет каждый элемент с 6, с конца, спускаясь в низ, сравниваться с серединой масива?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.09.2009, 19:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Прокоментировать 2 строки по сортировке (C++):

Нужно прокоментировать программу - C++
#include &lt;iostream.h&gt; #include &lt;stdlib.h&gt; class Matrix{ int m; public: Matrix(int=0); void display(); Matrix...

Как прокоментировать программу - C++
// Подключение заголовочных файлов языка C++ #include&lt;iostream&gt; #include &lt;cstdlib&gt; // Использование стандартного пространства имен...

прокоментировать функцию "ввод из типизированного файла" - C++
Всем здрасте. Помогите плих нужно прокоментировать в тех местах где поставил пустые &quot;//&quot; и там где в них вопросы поставил, заранее спасибо,...

Ошибка в сортировке - C++
#include &lt;iostream&gt; #include &lt;string&gt; #include &lt;algorithm&gt; int const N = 5; using namespace std; class book{ ...

Помощь в сортировке - C++
Здравствуйте, товарищи программисты. Знаю, что вам уже всем надоело натыкаться на подобные темы со структурой ZNAK, но все же! Написал...

Ошибка в сортировке - C++
Часть программы я сделал, но сортировка массива выходит кривой, та строка, которая после сортировки должна быть первой, внезапно...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
24.09.2009, 15:27 #16
Syltan, Получили в первом цикле
-5, 7, 3, 9, 25, 33, 50
i=3, j=3.
Но массив еще не отсортирован, "отсортированы" 2 его части. НО. любой элемент первой части меньше любого элемента правой. Значит, надо отсортировать каждую часть.
т.е. ( -5, 7, 3, 9 ) и (9, 25, 33, 50)

Код
if ( j > 0 ) quickSortR(a, j);
j=3. a - указывает на первый элемент массива -5, 7, 3, 9, 25, 33, 50 (индекс 0)
т.е. передаем в функцию указатель на начало и индекс 3. иными словами - сортируем подмассив
( -5, 7, 3, 9 )

Код
if ( N > i ) quickSortR(a+i, N-i);
N=6. i=3. a - указывает на первый элемент массива -5, 7, 3, 9, 25, 33, 50 (индекс 0)
т.е.
Код
quickSortR(УКАЗАТЕЛЬ_НА_3_ЭЛ-НТ, 3);
работаем с массивом (9, 25, 33, 50)
0
R0mm
Псевдо программист
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
24.09.2009, 15:30 #17
Syltan, я же написал. ты знаешь что такое трассировка? выводи на каждом шаге массив. если это сложно - значит программинг не твое..
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
24.09.2009, 23:53  [ТС] #18
Вроде уже уяснил. Ещё один момент. Смотрите вот эта строка:
C++
1
if ( j > 0 ) quickSortR(a, j);
сортирует левую часть масива,
эта строка:
C++
1
    if ( N > i ) quickSortR(a+i, N-i);
сортирует правую часть масива.
Скажите, при вызове функции, также выбирается опорный элемент p, для левой и правой части?

Добавлено через 43 минуты
Скажите,условие:

C++
1
2
3
4
5
if (i <= j) 
        {
            temp = a[i]; a[i] = a[j]; a[j] = temp; 
            i++; j--;
        }
Выполняется,только в случае,если нашлось одно из чисел которые не соответствуют условию вайл?
0
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
25.09.2009, 08:54 #19
Цитата Сообщение от Syltan Посмотреть сообщение
Скажите, при вызове функции, также выбирается опорный элемент p, для левой и правой части?
Почитай листинг функции - там всегда выбирается опорный элемент

Условие
C++
1
2
3
4
5
if (i <= j) 
        {
            temp = a[i]; a[i] = a[j]; a[j] = temp; 
            i++; j--;
        }
Выполняется когда индекс i меньше или равно индекса j Иными словами - если найденные a[i] и a[j] находятся в разных частях (соответственно слева и справа от p)
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
25.09.2009, 13:31  [ТС] #20
Тоесть вы хотите сказать,что условие:

C++
1
2
3
4
5
if (i <= j) 
        {
            temp = a[i]; a[i] = a[j]; a[j] = temp; 
            i++; j--;
        }
выполняется в любом случае,если i<=j, и никак не зависят от тех 2 вайлов выше.
0
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
25.09.2009, 13:41 #21
Естественно!
C++
1
2
3
4
5
6
7
8
9
10
11
        while ( a[i] < p ) i++;  // крутится несколько раз, пока не найдет элемент < p
//цикл while ( a[i] < p ) закончился
        while ( a[j] > p ) j--;  // крутится несколько раз, пока не найдет элемент > p
//цикл  while ( a[j] > p ) закончился
 
//Теперь проверяем, а вдруг до центрального элемента не было таких значений, что их надо перенести на другую сторону?
        if (i <= j) // т.е. i-й - левее j-го элементов, значит меняем
        {
            temp = a[i]; a[i] = a[j]; a[j] = temp; 
            i++; j--;
        }
Добавлено через 3 минуты
иными словами циклы
C++
1
2
        while ( a[i] < p ) i++;
        while ( a[j] > p ) j--;
можно записать:
C++
1
2
3
4
5
6
7
8
        while ( a[i] < p )
        {
          i++;
        }
        while ( a[j] > p )
        {
          j--;
        }
Значит, ну никак не влияют) сначала циклы, в которых определяются i и j, а потом уже обмен элементов
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 14:10  [ТС] #22
Всё, наконец-то понял весь алгоритм сортировки. Попробовал изменить данную программу,чтоб масив чисел, вводился с клавиатуры, что-то не компилится.
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
int main()
{
  setlocale(LC_ALL, "Russian");   // создаем массив символов
    char str[] = "бвгда";
    // сортируем массив символов
    quickSortR(str, strlen(str));
    // выводим на экран отсортированный массив симовлов
    cout << str <<  endl;
    // создаем целочисленный массив
    int ch,z, k = 0;
    cout<<"Введите количество чисел -> ";
    cin>>k;
    int a[] = {0};
    for(z = 0; z<k; z++)
    {
        cin>>ch;
        a[z] = ch;
    }
     
    // сортируем целочисленный массив
    quickSortR(a, a[z]);
    // выводим на экран отсортированный целочисленный массив
    for(int i = 0; a[z]; i++)
        cout << a[z] << " ";
    cout <<  endl;
    
    system("pause"); 
    return 0; // функция main ДОЛЖНА возвращать число
}
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
26.09.2009, 14:24 #23
Заголовочных файлов нет, определения и объявления quickSortR нет...
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 14:26  [ТС] #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
#include <iostream>
using namespace std;
 
//создается шаблнная функция
template<class T> 
// функция принимает аргументы: 
// массив (так как функция шаблонная, то любого типа массив), и кол-во элементов массива.
void quickSortR(T* a, long N) 
{
    long i = 0, j = N;
    // T - это тип передаваемого массива
    // создаем две перменных этого типа
    T temp, p;
 
  
    p = a[ N>>1 ];
 
    // процедура разделения (разделяет массив на подмассивы)
 
    do {
         
        while ( a[i] < p ) i++;  
        while ( a[j] > p ) j--;  
 
        if (i <= j) 
        {
            // обмен местами элементов a[i] с a[j] 
            // то есть, то что было в a[i] станет в a[j]
            // а то, что было в a[j] станет в a[i]
            temp = a[i]; a[i] = a[j]; a[j] = temp; 
            i++; j--;
        }
    } while ( i<=j );
 
    // рекурсивные вызовы, если есть, что сортировать
    if ( j > 0 ) quickSortR(a, j); 
 
    if ( N > i ) quickSortR(a+i, N-i);
      
}
// ------------------------------------------------------------------------------
int main()
{
  setlocale(LC_ALL, "Russian");   // создаем массив символов
    char str[] = "бвгда";
    // сортируем массив символов
    quickSortR(str, strlen(str));
    // выводим на экран отсортированный массив симовлов
    cout << str <<  endl;
    // создаем целочисленный массив
    int ch,z, k = 0;
    cout<<"Введите количество чисел -> ";
    cin>>k;
    int a[] = {0};
    for(z = 0; z<k; z++)
    {
        cin>>ch;
        a[z] = ch;
    }
     
    // сортируем целочисленный массив
    quickSortR(a, a[z]);
    // выводим на экран отсортированный целочисленный массив
    for(int i = 0; a[z]; i++)
        cout << a[z] << " ";
    cout <<  endl;
    
    system("pause"); 
    return 0; // функция main ДОЛЖНА возвращать число
}
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
26.09.2009, 14:31 #25
У меня всё скомпилилось.
Какие именно ошибки пишет компилятор/линковщик и в каких строках кода (если указывает на строки)?
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 14:33  [ТС] #26
Вы меня не поняли,программа то компилится,но работает не правильно. Я хочу задать ввод с клавиатуры чисел, а программа их уже должна отсортировать. То есть вначале, юзер, должен ввести количество чисел масива,после этого,сами числа, а программа должна вывести эти числа в отсортированном виде.
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
26.09.2009, 14:48 #27
Да всё я правильно понял.

Автор, напиши где-нибудь такую строчку:
C++
1
cout<<"Введите"<< k<< "чисел массива"<<endl;
Ну и... приходи снова.
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 16:28  [ТС] #28
Попробывал так, но опять нее то.
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
#include <iostream>
using namespace std;
 
template < typename T>
void sort(T *a, long N)
{
    long i = 0,  j = N;
   T temp,p;
   p = a[N/2];
   do{
   while(a[i]<p) i++;
   while(a[j]>p) j--;
   if(i<=j)
   {
       temp = a[i]; a[i]= a[j]; a[j] = temp;
       i++; j--;
   }
   }while(i<=j);
   if(j>0) sort(a,j);
   if(N>i) sort(a+i,N-i);
 
}
 
 
int main()
{
setlocale(0,"");
int k,ch;
cout<<"Введите пожалуйста количество чисел:\n";
cin>>k;
int* a = new int[k];
sort(a,a[k-1]);
for(int i = 0; i < k; i++)
cout<<a[i]<<' ';
delete[] a; 
 
cin.get();
}
Добавлено через 23 минуты
Что-то неизвестно, вот наваял ещё по-другому:
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
#include <iostream>
using namespace std;
 
template < typename T>
void sort(T *a, long N)
{
    long i = 0,  j = N;
   T temp,p;
   p = a[N/2];
   do{
   while(a[i]<p) i++;
   while(a[j]>p) j--;
   if(i<=j)
   {
       temp = a[i]; a[i]= a[j]; a[j] = temp;
       i++; j--;
   }
   }while(i<=j);
   if(j>0) sort(a,j);
   if(N>i) sort(a+i,N-i);
 
}
 
 
int main()
{
setlocale(0,"");
int k1 = 0,ch1,i;
int k2 = 0,ch2, s;
cout<<"Введите пожалуйста количество чисел:\n";
cin>>k1;
int* a = new int[k1];
sort(a,a[k1-1]);
for(i = 0; i < k1; i++)
{
cin>>ch1;
a[i] = ch1;
cout<<a[i]<<' ';
}
delete[] a; 
 
cout<<"Введите пожалуйста количество символов:\n";
cin>>k2;
int* b = new int[k2];
sort(a,a[s-1]);
for(s = 0; s < k2; s++)
{
cin>>ch2;
a[s] = ch2;
cout<<a[s]<<' ';
}
delete [] b;
 
cin.get();
}
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
26.09.2009, 16:39 #29
Слушай, Syltan, я отталкиваюсь от твоей же просьбы.
Ты сказал, что необходимо ввести количество элементов массива и сам массив С КЛАВИАТУРЫ
Вот и делай это. Сперва вводи количество элементов. Это ты сделал, ввёл k.
Потом выделил память для этого массива
C++
1
int* a = new int[k];
А потом вызываешь функцию sort. Я так понял она что-то сортирует. Но что? Незаполненный массив?

Заполняй массив вручную, а потом сортируй его.
И это... Добьём мы, конечно твою задачу. Но всё-таки решай сперва задачки попроще. А то не в коня корм получается. Извини.

Добавлено через 5 минут
Цитата Сообщение от Syltan Посмотреть сообщение
Я хочу задать ввод с клавиатуры чисел
Вот и задай. Покажи, где задал, если считаешь, что задал. Если не умеешь, скажи, что не умеешь.

А гадать не надо и простыни выдавать без комментов тоже не надо. Это закончится тем, что тебе в лучшем случае дадут готовый код и разбирайся в нём.
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 18:09  [ТС] #30
Вот так работате, но:
1)не выводятся и не вводятся русские символы;
При вводе первого русского символа, обрывается программа, при вводе английского также.

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
#include <iostream>
using namespace std;
 
template < typename T>
void sort(T *a, long N)
{
    long i = 0,  j = N;
   T temp,p;
   p = a[N/2];
   do{
   while(a[i]<p) i++;
   while(a[j]>p) j--;
   if(i<=j)
   {
       temp = a[i]; a[i]= a[j]; a[j] = temp;
       i++; j--;
   }
   }while(i<=j);
   if(j>0) sort(a,j);
   if(N>i) sort(a+i,N-i);
 
}
 
 
int main()
{
     int k; // Одну и ту же переменную можно использовать дважды и более для разных операций
     setlocale(LC_ALL, "Russian");
 
    cout << "Введите кол-ство чисел: ";
    cin >> k; // Вводим кол-ство элементов
 
     int* a = new int [k]; // Выделяем память под массив
     
     for(int i = 0; i < k; i++) { // Заполняем массив 
     cin >> a[i];       // Введёнными с клавиатуры цифрами
         
     }
 
     sort(a, k-1);  // Сортируем
     cout << "\nОтсортированный массив: ";
     for(int i = 0; i < k; i++) // Выводим отсортированный массив
     cout << a[i] << ' ';
 
     delete[] a; // Освобождаем память.
     ///////////////////////////////////////////////////////////////////////////
     //////////////////////////////////////////////////////////////////////////
     cout << "\nВведите кол-ство символов: ";
     cin >> k;  // Вводим кол-ство символов для второго массива
 
     int* b = new int[k];  // Выделяем под него память.
     
     for(int i = 0; i < k; i++) {  // Вводим значения
          cin >> b[i];
     }
 
     sort(b, k-1);  // Сортируем
     cout << "\nОтсортированный массив: ";
     for(int i = 0; i < k; i++)  // Выводим отсортированный
     cout << b[i] << ' ';
     delete[] b; // Освобождаем память.   
     
     cin.get();
 
     return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2009, 18:09
Привет! Вот еще темы с ответами:

Ошибка в сортировке - C++
#include &lt;iostream&gt; using namespace std; int main() { int A, c; for (int i = 0; i &lt; 3; i++) { for (int j = 0; j &lt; 3;...

Счетчик в сортировке - C++
Помогите исправить ошибки: template &lt;class type&gt;float sortV(type *b,long n) { type a,i,j; float c; for (i=0;i&lt;n;i++) ...

ошибка в сортировке массива - C++
Здравствуйте, помогите пожалуйста исправить ошибку Жалуется на скобку Задание: Нужен код сортировки массива методом...

Ошибка в сортировке пузырьком - C++
помогите разобраться в чем заключается ошибка. при выполнении функции происходит ошибка #include &lt;iostream&gt; using namespace...


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

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

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