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

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

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

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

22.09.2009, 19:05. Просмотров 1710. Ответов 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++
Часть программы я сделал, но сортировка массива выходит кривой, та строка, которая после сортировки должна быть первой, внезапно...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Delphin_KKC
UNIX-way
710 / 495 / 17
Регистрация: 15.01.2009
Сообщений: 1,721
22.09.2009, 21:31 #2
Цитата Сообщение от Syltan Посмотреть сообщение
...
// массив (так как функция шаблонная, то любого типа массив), и кол-во элементов массива.
Правильнее описать так:
// массив (так как функция шаблонная, то любого типа массив), и максимальный индекс массива.
Правильность такого описания подтверждается приведённым примером:
C++
1
2
3
int a[] = { 2, 5, 1, 20, 8, 0, 9 };
    // сортируем целочисленный массив
    quickSortR(a, 6);
Цитата Сообщение от Syltan Посмотреть сообщение
Происходит сравнение общего количества элементов масива с серединой масива. Тоесть если масив сосстоит из 6 элементов,тогда будет каждый элемент с 6, с конца, спускаясь в низ, сравниваться с серединой масива?
Это откуда там взялось сравнение общего количества?
Если масив сосстоит из 6 элементов,тогда каждый элемент с 5(отсчёт ведь от нуля), с конца, спускаясь в низ, сравниваться с серединой масива.
1
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
22.09.2009, 21:42 #3
Ну что не ясного? предположим, р - 3-й элемент. p=7
1-я строка. например 2-й эл-нт = 5. 5<7 цикл заканчивается, в i остается индекс элемента
2-я строка. например 4-й эл-нт = 9. 9>7 цикл заканчивается, в j остается индекс элемента
C++
1
2
        while ( a[i] < p ) i++;  // ищем индекс эл-нта меньшего p в левой части
        while ( a[j] > p ) j--;  // ищем индекс эл-нта большего p в правой части
а после этого меняем местами i-й и j-й элементы
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
22.09.2009, 22:08  [ТС] #4
Наконец-то у яснил. И последнее, вот этот кусок,уже почти час смотрю в него, и не възжаю.

C++
1
2
3
4
5
 //Если индекс с конца масива больше нуля, тогда вызвать функцию, 
//quickSortR(a, j)  и передать в качестве аргумента,что и от куда с мэин или с с цикла ду..вайл?
//Расшифруйте пожалуйста подробней эти 2 усоловия,как и что передаётся
if ( j > 0 ) quickSortR(a, j);
 if ( N > i ) quickSortR(a+i, N-i); // рекурсивно вызываем функцию

Прошу вас,объясните эти 2 строки?
0
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
22.09.2009, 22:26 #5
эти 2 строки вызывают quickSortR для левой и правой части (при выполнении условий - соответствующие части еще м.б. не отсортированы). т.е. все по алгоритму быстрой сортировки:
1. делим пополам
2. меняем местами элементы (меньшие - влево, большие вправо)
3. из каждой "половины" выделяем неотсортированую часть и выполняем 1-3
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
22.09.2009, 22:50  [ТС] #6
Алгоритм я читал,просто не могу понять: аот это:
C++
1
 quickSortR(a, j);
и вот это:
C++
1
quickSortR(a+i, N-i)
Будьте добры,растолкуйте.
0
lexus_ilia
3046 / 922 / 34
Регистрация: 24.09.2008
Сообщений: 1,530
23.09.2009, 04:48 #7
Вам непонятно что здесь происходит вызов функции из самой себя (рекурсия), или Вам не понятны переменные которые передаются функции, и почему они именно такие?
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
23.09.2009, 11:28  [ТС] #8
Вот именно:

C++
1
не понятны переменные которые передаются функции, и почему они именно такие?
0
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
23.09.2009, 11:47 #9
C++
1
quickSortR(a, j);
a - указатель на начало массива
j - максимальный индекс массива.
Откуда что? a - мы получали в качестве параметра функции quickSortR.
j - только что нашли. это индекс, ПЕРЕД элементом, который мы вставили обменом (строка 32 кода выше)
т.е. передаем не весь, а только до j, т.к. дальше в массиве идут элементы меньшие p.

Добавлено через 5 минут
C++
1
quickSortR(a+i, N-i)
a+i - указатель на начало массива
N-i - максимальный индекс массива.
за начало берем часть от i-го элемента (a+i) до конца массива(N-i) N - максимальный индекс в массиве а. но передаем не весь массив, а отбрасываем левую часть до i-го эл-та, следовательно, и максимальный индекс должен уменьшиться на величину сдвига i
1
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
23.09.2009, 18:49  [ТС] #10
Вернусь к предыдущему вопросу:

Как будет сравниваться центральный элемент,если элементы в масиве будут расположенны вот так:

Код
[B]50 7 3 9 25 33 -5  [/B]
Центральный равен = 9

Если мы будем следовать вот этому условию:
Код
  while ( a[i] < p ) i++;  
        while ( a[j] > p ) j--;
1 итерация) 50<9 нет, итерация не происходит,условие if (i<=j) не выполняется
1 итерация 2-го вайла) -5>9 итерация также не происходит.

Как по поводу этого?
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
24.09.2009, 00:30  [ТС] #11
Хорошо, давайте возьмём другие числа в масиве.

Код
[B] 50, 7, 3, 9, 25, 33, -5 [/B]
Я напишу своё толкование:

p = 9, i = 0, j = 6

Код
1) while(a[i]<p) i++;
50<p? НЕТ i осталось 0;

while(a[i]>p) j--;
-5>p? Нет j осталось 6.
Код
2)if (i <= j)
        {
            temp = a[i]; a[i] = a[j]; a[j] = temp;
            i++; j--;
        }
Если i меньше чем j(тоесть если мы нашли такие элементы,которые заставили предыдущие циклы остановится, то меняем местами a[i], a[j] ;
i = 0; j = 6;
Меняем a[0] = 50, a[6] = -5/

-5   7   3    9    25     33    50


Увеличиваем i  на один, j уменьшаем на один.
Код
3) i = 1,  j = 5;
 while(a[i]<p) i++;
7<9? Да.  i стаёт равно = 2;

while(a[j]>p) j--;
33>9? Да. j стаёт равно 4

Результат счётчиков i = 2,  j = 4;
Код
4)while(a[i]<p) i++;
3<9? Да  i = 3;

5) while(a[j]>p) j--;

25>9? Да. j = 3;

Результат i = 3;  j  = 3;

Как заканчивается цикл do ..while ?
Меня интересует место: while(i < = j) От куда подставляется в i и j?
Если кому не трудно,можете так,как я расписал выше, расписать вот эти 2 строчки и всё, буду всей жизню благодарен. Распишите, действия этих 2 строк за каждой рекурсией,как происходит с теми числами,которые я писал выше?
C++
1
2
if ( j > 0 ) quickSortR(a, j);
    if ( N > i ) quickSortR(a+i, N-i);
0
R0mm
Псевдо программист
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
24.09.2009, 14:14 #12
Цитата Сообщение от Syltan Посмотреть сообщение
C++
1
2
while ( a[i] < p ) i++; 
 while ( a[j] > p ) j--;
данными операторами мы "выделяем" место, в котором будет производится сортировка.
другими словами между a[i] и a[j] числа НЕ упорядочены.

Цитата Сообщение от Syltan Посмотреть сообщение
Как заканчивается цикл do ..while ?
как только i станет = j, то массив будет отсортирован, другими словами не останется не упорядоченных элементов.
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
24.09.2009, 14:18  [ТС] #13
Напишите пожалуйста на примере именно этих их чисел, мне так легче понять. Очень нужно.
меня интересует вот это:
C++
1
2
if ( j > 0 ) quickSortR(a, j);
    if ( N > i ) quickSortR(a+i, N-i);
Напишите последовательно, с числами,как происходят действия:
0
R0mm
Псевдо программист
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
24.09.2009, 14:41 #14
пф.. немного неправильно написал в прошлый раз.
итак имеем последовательность:
50, 7, 3, 9, 25, 33, -5
i j

следуя алгоритму переносим меньшие элементы вправо, наибольшие влево(относительно p=9).
50, 7, 3, 9, 25, 33, -5
имеем
-5, 7, 3, 9, 25, 33, 50
мы знаем что все элементы справа от p больше всех элементов слева от p.
поэтому применяем ту же сортировку к последовательностям
-5, 7, 3, 9, 25, 33, 50
ну и дальше по аналогии

Добавлено через 4 минуты
то есть сортируем относительно центрального элемента.
5, 4, 3, 2, 6, 2, 54, 23, -3, 231, 30
сортируем относительно "красного".
все меньшие него справа переносим влево.
все большие его слева переносим вправо.
-3, 3, 4, 2, 6, 2, 54, 23, 5, 231, 30

я не знаю как это на словах описать, тут все бонально %)
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
24.09.2009, 15:01  [ТС] #15
Опишите пожалуйста именно с этими числами, а не с другими,так как я исследую код полностью, именно с этими числами.
Вот числа:

Код
50, 7, 3, 9, 25, 33, -5
Когда закончатся действия предыдущих циклов, мы перейдём к вот этому:

C++
1
2
if ( j > 0 ) quickSortR(a, j);
    if ( N > i ) quickSortR(a+i, N-i);
Когда мы дошли до этого, как числа будут сортироваться, и какие они будут,когда мы дошли до этого куска. Напишите,что за первым разом, за вторым,чисел не много. Благодарю.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2009, 15:01
Привет! Вот еще темы с ответами:

Ошибка в сортировке - 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
Объявления
24.09.2009, 15:01
Ответ Создать тему
Опции темы

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