Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Странные аргументы

Автор: Syltan 23.9.2009, 15:24

Код

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);

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

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

Автор: zim22 23.9.2009, 15:38

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

)

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

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

Автор: Syltan 23.9.2009, 23:52

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

Код

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);

Автор: bsa 24.9.2009, 00:22

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

Автор: Syltan 24.9.2009, 22:11

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

Код


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

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

Код


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

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

Автор: ller 24.9.2009, 22:18

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

Автор: Syltan 24.9.2009, 22:51

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

Код


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

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