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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
22.09.2009, 19:05     Прокоментировать 2 строки по сортировке #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
#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, с конца, спускаясь в низ, сравниваться с серединой масива?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.09.2009, 19:05     Прокоментировать 2 строки по сортировке
Посмотрите здесь:

Счетчик в сортировке C++
C++ Ошибка в порязрядной сортировке?!
C++ прокоментировать функцию "ввод из типизированного файла"
C++ Ошибка в сортировке
C++ Помощь в сортировке
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
25.09.2009, 13:41     Прокоментировать 2 строки по сортировке #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, а потом уже обмен элементов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 14:10  [ТС]     Прокоментировать 2 строки по сортировке #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 ДОЛЖНА возвращать число
}
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
26.09.2009, 14:24     Прокоментировать 2 строки по сортировке #23
Заголовочных файлов нет, определения и объявления quickSortR нет...
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 14:26  [ТС]     Прокоментировать 2 строки по сортировке #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 ДОЛЖНА возвращать число
}
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
26.09.2009, 14:31     Прокоментировать 2 строки по сортировке #25
У меня всё скомпилилось.
Какие именно ошибки пишет компилятор/линковщик и в каких строках кода (если указывает на строки)?
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 14:33  [ТС]     Прокоментировать 2 строки по сортировке #26
Вы меня не поняли,программа то компилится,но работает не правильно. Я хочу задать ввод с клавиатуры чисел, а программа их уже должна отсортировать. То есть вначале, юзер, должен ввести количество чисел масива,после этого,сами числа, а программа должна вывести эти числа в отсортированном виде.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
26.09.2009, 14:48     Прокоментировать 2 строки по сортировке #27
Да всё я правильно понял.

Автор, напиши где-нибудь такую строчку:
C++
1
cout<<"Введите"<< k<< "чисел массива"<<endl;
Ну и... приходи снова.
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 16:28  [ТС]     Прокоментировать 2 строки по сортировке #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();
}
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
26.09.2009, 16:39     Прокоментировать 2 строки по сортировке #29
Слушай, Syltan, я отталкиваюсь от твоей же просьбы.
Ты сказал, что необходимо ввести количество элементов массива и сам массив С КЛАВИАТУРЫ
Вот и делай это. Сперва вводи количество элементов. Это ты сделал, ввёл k.
Потом выделил память для этого массива
C++
1
int* a = new int[k];
А потом вызываешь функцию sort. Я так понял она что-то сортирует. Но что? Незаполненный массив?

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

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

А гадать не надо и простыни выдавать без комментов тоже не надо. Это закончится тем, что тебе в лучшем случае дадут готовый код и разбирайся в нём.
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
26.09.2009, 18:09  [ТС]     Прокоментировать 2 строки по сортировке #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;
}
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
27.09.2009, 11:06     Прокоментировать 2 строки по сортировке #31
По выводу на экран русских символов тут есть отдельная тема, setlocale(LC_ALL, "Russian"); не всегда работает, ищи другой вариант.

По второму вопросу.
Вводишь символы, так и объявляй указатель на соответствующий тип. То есть так:

C++
1
2
[FONT=monospace]char* b = new char[k];  // Выделяем под него память.
[/FONT]
Это строка 52
а не как у тебя.
...И не вздумай писать, что у тебя не выводится отсортированный массив символов.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.11.2010, 15:56     Прокоментировать 2 строки по сортировке
Еще ссылки по теме:

Ошибка в сортировке C++
Как прокоментировать программу C++
Нужно прокоментировать программу C++

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

Или воспользуйтесь поиском по форуму:
RU4NIK
Заблокирован
17.11.2010, 15:56     Прокоментировать 2 строки по сортировке #32
52!100%да!
Yandex
Объявления
17.11.2010, 15:56     Прокоментировать 2 строки по сортировке
Ответ Создать тему
Опции темы

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