VPF::Вопросы насчёт быстрой сортировки

stopafilm

Дата 31.7.2010, 13:03 (ссылка)

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

Загрузка ...

Новичок

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

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

Здравствуйте. Объясните, пожалуйста. Есть алгоритм быстрой сортировки:

Код


int shag=1;

void quickSort(int arr[], int left, int right, char v) {

            cout <<"--------" <<shag <<"-------" <<endl;

      if(v=='a') {cout <<"       Вариант №1"  <<endl; shag++;}
      else       {cout <<"        Вариант №2" <<endl; shag++;}
      cout <<"                                    left: " <<left <<endl;
      cout <<"                                    right: " <<right <<endl;

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];
      cout  <<endl <<"pivot: " <<pivot <<' ' <<endl;



      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;
                 cout <<"               a[i]: "  <<arr[i] <<endl;
                 cout <<"               a[j]: "  <<arr[j] <<endl;
            }

      };

        cout <<"j: " <<j <<' ' <<endl;
        cout <<"i: " <<i <<' ' <<endl;




      if (left < j)

          quickSort(arr, left, j, 'a');


      if (i < right)

          quickSort(arr, i, right , 'b');

}


int main()
{
int z[]={1, 2, 3, 5, 7, 7, 12, 26, 14};
quickSort(z,0,8,'a');
}

В нём непонятно 2 вещи:
1)Почему срабатывает рекурсивно второй вариант (b) (шаг 4), если значение i=1 (i<right). Я, наверно, неправильно понимаю рекурсию. Просто, в конце 3 шага не срабатывает ни

Код

if (left < j)

( j меньше нуля) ни

Код

if (i < right)

(1<1).
2)Откуда берутся значения: left: 3 и right: 4 (шаг 4).
P.S. Массив сортируется правильно.

Спасибо за ответ dva300.

Это сообщение отредактировал(а) stopafilm - 31.7.2010, 21:10

dva300

Дата 31.7.2010, 19:44 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата

Код

if (left < j)

( j меньше нуля) ни

Код

if (i < right)

(1<1).
2)Откуда берутся значения: left: 3 и right: 4 (шаг 4).
P.S. Массив сортируется правильно.

Доброго дня,
суть вопроса на понятна.
что значит почему ? потому что алгоритм такой.
тут есть описание http://ru.wikipedia.org/wiki/Quicksort
поповоду рекурсии - просто почитайте что-нибудь.

у меня есть пример визуализации этого алгоритма на MVС++. может пригодиться

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

qs.exe 65,00 Kb

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

Участник движения Культура Вождения

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