Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 21.09.2009, 22:19   #1
Syltan
Заблокирован
 
Регистрация: 27.08.2009
Сообщений: 569
Плохо Прокоментировать 2 строки

Разбираюсь с алгоритмом быстрой сортировки, вроде уже разобрался но не до конца. НЕ могу понять вот эти 2 строки:

Код:
 while ( a[i] < p ) i++;
        while ( a[j] > p ) j--;
Что они делают, как их понять?
Вот весь исходник:
Код:
#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 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 ДОЛЖНА возвращать число
}
Syltan вне форума Ответить с цитированием
Старый 21.09.2009, 22:25   #2
Sambuko
Новичок
Джуниор
 
Регистрация: 20.09.2009
Сообщений: 4
По умолчанию

Считают сколько элементов в массиве меньше среднего (по порядку) и сколько больше
Sambuko вне форума Ответить с цитированием
Старый 21.09.2009, 22:31   #3
Syltan
Заблокирован
 
Регистрация: 27.08.2009
Сообщений: 569
По умолчанию

Смысл этих 2 строк таков,или нет? while ( a[i] < p ) i++; пока каждый элемент масива меньше чем общее количество элементов масива,тогда перейти на следующий,количество элементов записать в i? А смысл while ( a[j] > p ) j--; что-то не ясен. А за ним i++ тоесть перейти на следующий элемент масива?
А j-- тогда что?* Объсните эти 2 строки, боюсь,понимаю их не правильно.

Последний раз редактировалось Syltan; 21.09.2009 в 22:36.
Syltan вне форума Ответить с цитированием
Старый 21.09.2009, 22:40   #4
netrino
Участник клуба
 
Аватар для netrino
 
Регистрация: 15.07.2008
Сообщений: 1,933
По умолчанию

Код:
p = a[ N>>1 ]; // Положить p равным числу, которое находится посередине массива
...
while ( a[i] < p ) i++; // Смотрим слева от p, есть ли там элементы больше, чем p
while ( a[j] > p ) j--; // Смотрим справа от p, есть ли там элементы меньше чем p
Собственно зачем это делать, суть в том, чтобы переместить все элементы, которые меньше p влево от него, а которые больше вправо.

Последний раз редактировалось netrino; 21.09.2009 в 22:43.
netrino вне форума Ответить с цитированием
Старый 22.09.2009, 00:40   #5
Syltan
Заблокирован
 
Регистрация: 27.08.2009
Сообщений: 569
По умолчанию

Во всём уже почти разобрался,только вот проблемма не много с рекурсией. Если не сложно,объясните вот этот кусок:

Код:
    if ( j > 0 ) quickSortR(a, j); // рекурсивно вызываем функцию
    if ( N > i ) quickSortR(a+i, N-i); // рекурсивно вызываем функцию
Благодарю.
Syltan вне форума Ответить с цитированием
Старый 22.09.2009, 01:03   #6
netrino
Участник клуба
 
Аватар для netrino
 
Регистрация: 15.07.2008
Сообщений: 1,933
По умолчанию

Цитата:
Сообщение от Syltan Посмотреть сообщение
Во всём уже почти разобрался,только вот проблемма не много с рекурсией. Если не сложно,объясните вот этот кусок:

Код:
    if ( j > 0 ) quickSortR(a, j); // рекурсивно вызываем функцию
    if ( N > i ) quickSortR(a+i, N-i); // рекурсивно вызываем функцию
Благодарю.
Вы бы глянули в отладчике, как оно там происходит )
В двух словах, после того, как все элементы, которые больше p(средний элемент массива), окажутся справа, а все, что меньше - слева, тогда эти две половины отправляем на отдельную обработку:
Код:
if( j > 0 ) quickSortR(a, j); // левую часть массива
if( N > i ) quickSortR(a+i, N-i); // правую часть массива
С каждой из них проводятся те же шаманства, что и с изначальным массивом, таким образом мы получаем полностью отсортированный массив.
netrino вне форума Ответить с цитированием
Старый 22.09.2009, 01:31   #7
Syltan
Заблокирован
 
Регистрация: 27.08.2009
Сообщений: 569
По умолчанию

Со всем вроде разобрался, не могу последнее.
Кто знает,скажите что делается в вот этом:
Код:
quickSortR(a, j);
и этом:

Код:
quickSortR(a+i, j-i);
Я не могу понять эти моменты ,уже час сижу.
Что передаётся в аргументы,желательно яснее?

Последний раз редактировалось Syltan; 22.09.2009 в 23:43.
Syltan вне форума Ответить с цитированием
Старый 24.09.2009, 15:20   #8
Syltan
Заблокирован
 
Регистрация: 27.08.2009
Сообщений: 569
По умолчанию

Опишите пожалуйста именно с этими числами, а не с другими,так как я исследую код полностью, именно с этими числами.
Вот числа:

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

Код:
if ( j > 0 ) quickSortR(a, j);
    if ( N > i ) quickSortR(a+i, N-i);

Когда мы дошли до этого, как числа будут сортироваться, и какие они будут,когда мы дошли до этого куска. Напишите,что за первым разом, за вторым,чисел не много. Благодарю.
Syltan вне форума Ответить с цитированием
Старый 24.09.2009, 18:29   #9
netrino
Участник клуба
 
Аватар для netrino
 
Регистрация: 15.07.2008
Сообщений: 1,933
По умолчанию

Я же расписал Вам каждый шаг, что там ещё может быть не ясно?
netrino вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Господа можете прокоментировать код. hub2002 Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 1 07.08.2009 02:03
Перенести символа с начала строки в место перед запятой этой же строки. Zhiltsov Microsoft Office Excel 4 05.06.2009 13:10
С++ Прокоментировать программу М@лышка Помощь студентам 10 05.06.2009 03:30
Строки. Как вывести часть строки? Anfall Общие вопросы Delphi 7 26.02.2009 09:10
считать из файла две строки, вывести на экран символы первой строки, которые отсутствуют во второй gotex Помощь студентам 4 08.05.2008 02:27