VPF::Странные аргументы - Форум программистов

Syltan

Дата 23.9.2009, 15:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 301
Регистрация: 31.8.2009

Репутация: -1
Всего: -2

Код

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); // рекурсивно вызываем функцию
  }

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

Код


quickSortR(a, j);

и этом:

Код


quickSortR(a+i, j-i);

Я не могу понять эти моменты ,уже час сижу.
Что передаётся в аргументы,желательно яснее?

Модератор: Пожалуйста, один топик - один вопрос.

Это сообщение отредактировал(а) bsa - 24.9.2009, 00:17

zim22

Дата 23.9.2009, 15:38 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Syltan @ 23.9.2009, 15:24

)

Что передаётся в аргументы,желательно яснее?

кусочки массивчика передаются. принцип "разделяй и властвуй".

Это сообщение отредактировал(а) zim22 - 23.9.2009, 15:39

--------------------

C++ FAQ Lite

Syltan

Дата 23.9.2009, 23:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 301
Регистрация: 31.8.2009

Репутация: -1
Всего: -2

Хорошо, давайте возьмём другие числа в масиве.

Код

50, 7, 3, 9, 25, 33, -5

Я напишу своё толкование:

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 строк за каждой рекурсией,как происходит с теми числами,которые я писал выше?

Код


if ( j > 0 ) quickSortR(a, j);
    if ( N > i ) quickSortR(a+i, N-i);

Это сообщение отредактировал(а) Syltan - 23.9.2009, 23:53

bsa

Дата 24.9.2009, 00:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Ну что непонятного?
Если j > 0, то тогда сортировать j элементов от начала массива
Если i < N, то тогда сортировать N-i элементов начиная с элемента a[i]

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Syltan

Дата 24.9.2009, 22:11 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 301
Регистрация: 31.8.2009

Репутация: -1
Всего: -2

Вроде уже уяснил. Ещё один момент. Смотрите вот эта строка:

Код


if ( j > 0 ) quickSortR(a, j);

сортирует левую часть масива,
эта строка:

Код


if ( N > i ) quickSortR(a+i, N-i);

сортирует правую часть масива.
Скажите, при вызове функции, также выбирается опорный элемент p, для левой и правой части?

Это сообщение отредактировал(а) Syltan - 24.9.2009, 22:12

ller

Дата 24.9.2009, 22:18 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 325
Регистрация: 4.8.2008
Где: г. Таганрог

Репутация: 2
Всего: 4

Рекурсивный вызов...
Все повторяется снова... Только исходные данные другие...

Syltan

Дата 24.9.2009, 22:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 301
Регистрация: 31.8.2009

Репутация: -1
Всего: -2

Скажите,условие:

Код


if (i <= j) 
        {
            temp = a[i]; a[i] = a[j]; a[j] = temp; 
            i++; j--;
        }

Выполняется,только в случае,если нашлось одно из чисел которые не соответствуют условию вайл?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »