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

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

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

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

22.09.2009, 19:05. Просмотров 1685. Ответов 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, с конца, спускаясь в низ, сравниваться с серединой масива?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Delphin_KKC
UNIX-way
709 / 494 / 17
Регистрация: 15.01.2009
Сообщений: 1,721
22.09.2009, 21:31     Прокоментировать 2 строки по сортировке #2
Цитата Сообщение от Syltan Посмотреть сообщение
...
// массив (так как функция шаблонная, то любого типа массив), и кол-во элементов массива.
Правильнее описать так:
// массив (так как функция шаблонная, то любого типа массив), и максимальный индекс массива.
Правильность такого описания подтверждается приведённым примером:
C++
1
2
3
int a[] = { 2, 5, 1, 20, 8, 0, 9 };
    // сортируем целочисленный массив
    quickSortR(a, 6);
Цитата Сообщение от Syltan Посмотреть сообщение
Происходит сравнение общего количества элементов масива с серединой масива. Тоесть если масив сосстоит из 6 элементов,тогда будет каждый элемент с 6, с конца, спускаясь в низ, сравниваться с серединой масива?
Это откуда там взялось сравнение общего количества?
Если масив сосстоит из 6 элементов,тогда каждый элемент с 5(отсчёт ведь от нуля), с конца, спускаясь в низ, сравниваться с серединой масива.
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
22.09.2009, 21:42     Прокоментировать 2 строки по сортировке #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-й элементы
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
22.09.2009, 22:08  [ТС]     Прокоментировать 2 строки по сортировке #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 строки?
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
22.09.2009, 22:26     Прокоментировать 2 строки по сортировке #5
эти 2 строки вызывают quickSortR для левой и правой части (при выполнении условий - соответствующие части еще м.б. не отсортированы). т.е. все по алгоритму быстрой сортировки:
1. делим пополам
2. меняем местами элементы (меньшие - влево, большие вправо)
3. из каждой "половины" выделяем неотсортированую часть и выполняем 1-3
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
22.09.2009, 22:50  [ТС]     Прокоментировать 2 строки по сортировке #6
Алгоритм я читал,просто не могу понять: аот это:
C++
1
 quickSortR(a, j);
и вот это:
C++
1
quickSortR(a+i, N-i)
Будьте добры,растолкуйте.
lexus_ilia
3045 / 921 / 34
Регистрация: 24.09.2008
Сообщений: 1,530
23.09.2009, 04:48     Прокоментировать 2 строки по сортировке #7
Вам непонятно что здесь происходит вызов функции из самой себя (рекурсия), или Вам не понятны переменные которые передаются функции, и почему они именно такие?
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
23.09.2009, 11:28  [ТС]     Прокоментировать 2 строки по сортировке #8
Вот именно:

C++
1
не понятны переменные которые передаются функции, и почему они именно такие?
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
23.09.2009, 11:47     Прокоментировать 2 строки по сортировке #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
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
23.09.2009, 18:49  [ТС]     Прокоментировать 2 строки по сортировке #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 итерация также не происходит.

Как по поводу этого?
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
24.09.2009, 00:30  [ТС]     Прокоментировать 2 строки по сортировке #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);
R0mm
Псевдо программист
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
24.09.2009, 14:14     Прокоментировать 2 строки по сортировке #12
Цитата Сообщение от Syltan Посмотреть сообщение
C++
1
2
while ( a[i] < p ) i++; 
 while ( a[j] > p ) j--;
данными операторами мы "выделяем" место, в котором будет производится сортировка.
другими словами между a[i] и a[j] числа НЕ упорядочены.

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

я не знаю как это на словах описать, тут все бонально %)
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
24.09.2009, 15:01  [ТС]     Прокоментировать 2 строки по сортировке #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);
Когда мы дошли до этого, как числа будут сортироваться, и какие они будут,когда мы дошли до этого куска. Напишите,что за первым разом, за вторым,чисел не много. Благодарю.
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
24.09.2009, 15:27     Прокоментировать 2 строки по сортировке #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)
R0mm
Псевдо программист
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
24.09.2009, 15:30     Прокоментировать 2 строки по сортировке #17
Syltan, я же написал. ты знаешь что такое трассировка? выводи на каждом шаге массив. если это сложно - значит программинг не твое..
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
24.09.2009, 23:53  [ТС]     Прокоментировать 2 строки по сортировке #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--;
        }
Выполняется,только в случае,если нашлось одно из чисел которые не соответствуют условию вайл?
GAV_13
81 / 81 / 4
Регистрация: 14.09.2009
Сообщений: 252
25.09.2009, 08:54     Прокоментировать 2 строки по сортировке #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)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.09.2009, 13:31     Прокоментировать 2 строки по сортировке
Еще ссылки по теме:
C++ Ошибка в сортировке
Ошибка в пирамидальной сортировке C++
C++ ошибка в сортировке массива
Программа по сортировке участников C++

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

Или воспользуйтесь поиском по форуму:
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
25.09.2009, 13:31  [ТС]     Прокоментировать 2 строки по сортировке #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 вайлов выше.
Yandex
Объявления
25.09.2009, 13:31     Прокоментировать 2 строки по сортировке
Ответ Создать тему
Опции темы

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