VPF::Разъяснить 2 строки - Форум программистов

Syltan

Дата 21.9.2009, 21:23 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: -1
Всего: -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 ДОЛЖНА возвращать число
}

Данкинг

Дата 21.9.2009, 21:29 (ссылка)

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

Загрузка ...

Yersinia pestis

Профиль
Группа: Завсегдатай
Сообщений: 8302
Регистрация: 7.11.2006
Где: მოსკოვი

Репутация: нет
Всего: 130

Как их понять? Ну, цикл до тех пор, пока значение элемента массива a с индексом i меньше значения переменной p. Ну, о второй строчке догадаешься. smile

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

There's nothing left but silent epitaphs.

Syltan

Дата 21.9.2009, 21:35 (ссылка)

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

Загрузка ...

Опытный

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

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

А за ним i++ тоесть перейти на следующий элемент масива?
А j-- тогда что?*

zim22

Дата 21.9.2009, 21:37 (ссылка)

(голосов:2)

Загрузка ...

depict1

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

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

Цитата(Syltan @ 21.9.2009, 21:23

)

Что они делают, как их понять?

очень просто. пошаговая отладка программы + листик + ручка.

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

C++ FAQ Lite

Данкинг

Дата 21.9.2009, 21:51 (ссылка)

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

Загрузка ...

Yersinia pestis

Профиль
Группа: Завсегдатай
Сообщений: 8302
Регистрация: 7.11.2006
Где: მოსკოვი

Репутация: нет
Всего: 130

Цитата(Syltan @ 21.9.2009, 22:35

)

А за ним i++ тоесть перейти на следующий элемент масива?

Это увеличение значения переменной i.

Это сообщение отредактировал(а) Данкинг - 21.9.2009, 21:51

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

There's nothing left but silent epitaphs.

IKM2007

Дата 21.9.2009, 21:51 (ссылка)

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

Загрузка ...

Зима близко

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

Репутация: 3
Всего: 40

Syltan, читай книжки.

Добавлено @ 21:52
или если лень читать книги, используй гугл и узнаешь какой оператор для чего.

Это сообщение отредактировал(а) IKM2007 - 21.9.2009, 21:52

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

"К чёрту обстоятельства, я создаю возможности."

Брюс Ли

Syltan

Дата 21.9.2009, 22:06 (ссылка)

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

Загрузка ...

Опытный

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

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

Как запустить пошаговую отладку студия 2005?

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

586

Дата 21.9.2009, 22:25 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 8
Всего: 146

Цитата(Syltan @ 21.9.2009, 23:06

)

Как запустить пошаговую отладку студия 2005?

В меню: Debug->Step Into

Syltan

Дата 21.9.2009, 22:30 (ссылка)

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

Загрузка ...

Опытный

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

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

Следую вашей инструкции, получаю на экран вот такое при запуске, как теперь я смогу проследить действия программы.

Присоединённый файл ( Кол-во скачиваний: 19 )

clip_image002.jpg 40,83 Kb

iRUSH

Дата 21.9.2009, 23:02 (ссылка)

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

Загрузка ...

Новичок

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

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

В данном случае смею предположить что исмользуеться алгоритм quick sort почитать можно тут
Если ты внимательно вкуришь в написаное(то что по ссылке), то сразу же догадаешься и найдешь решение своей проблеме, а именно:

Код


p = a[ N>>1 ];

Тут мы берем грубо говоря середину массива(опорную точку по алгоритму), далее:

Код


while ( a[i] < p ) i++;
        while ( a[j] > p ) j--;

тут как мы видим идет два цикла, первый от начала к опорной точке, второй наоборот от конца к опорной точке....
Ну а далее по алгоритму действуем...

586

Дата 22.9.2009, 00:19 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 8
Всего: 146

Syltan, поставь BreakPoint (Debug->Toggle Breakpoint) на функции main, и запусти отладку (Debug->Start Debugging).
И убедись, что версия проекта Debug а не релиз.

Syltan

Дата 22.9.2009, 00:19 (ссылка)

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

Загрузка ...

Опытный

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

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

Спасибо,ссылочку я прочитал. Вот смотрите,строка:

Код


while ( a[i] < p ) i++;

Этим мы производим сравнение каждого элемента масива с серединой масива, выполняя замену,тоесть числа,меньшие середины масива, переходят в левую сторону. Но вот эта строка:

Код


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

Происходит сравнение общего количества элементов масива с серединой масива,тоесть если масив сосстоит из 6 элементов,тогда будет каждый элемент с 6, с конца, спускаясь в низ, сравниваться с серединой масива?

Это сообщение отредактировал(а) Syltan - 22.9.2009, 00:20

ller

Дата 22.9.2009, 08:25 (ссылка)

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

Загрузка ...

Опытный

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

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

1. Ставишь дебаг, а не релиз. Это важно.
2. Тыкаешь в поле около нужной строки, появляется знак, breakpoint - точка останова
3. Тыкаешь запустить и у тебя программа останавливается на нужной строке

zim22

Дата 22.9.2009, 08:43 (ссылка)

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

Загрузка ...

depict1

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

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

мне кажется эта версия quicksort будет легче для понимания

Код


template <class Item>
void quicksort(Item a[], int l, int r) {
  if (r <= l) return;
  int i = partition(a, l, r);
  quicksort(a, l, i - 1);
  quicksort(a, i + 1, r);
}


template <class Item>
int partition(Item a[], int l, int r) {
  int i = l - 1;
  int j = r; 
  Item v = a[r];

  for (;;) {
    while (a[++i] < v);

    while (v < a[--j]) 
      if (j == l) break;

    if (i >= j) break;
    std::swap(a[i], a[j]);
  }
  std::swap(a[i], a[r]);
  return i;
}

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

C++ FAQ Lite

Syltan

Дата 22.9.2009, 17:54 (ссылка)

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

Загрузка ...

Опытный

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

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

Проверьте, правильно ли я пояснил строку:

Код


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

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