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

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

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 31.07.2010, 20:32   #1
Stopafilm
Новичок
Джуниор
 
Регистрация: 03.07.2010
Сообщений: 2
По умолчанию Вопросы насчёт быстрой сортировки(С++)

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

Код:
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. Массив сортируется правильно.

Последний раз редактировалось Stilet; 03.08.2010 в 09:12.
Stopafilm вне форума Ответить с цитированием
Старый 01.08.2010, 08:41   #2
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Цитата:
2)Откуда берутся значения: left: 3 и right: 4 (шаг 4).
Из параметров функции.

Цитата:
Почему срабатывает рекурсивно второй вариант (b) (шаг 4),
Цитата:
значение i=1 (i<right)
Вы сам то алгоритм знаете и понимаете?
p51x вне форума Ответить с цитированием
Старый 01.08.2010, 10:43   #3
Stopafilm
Новичок
Джуниор
 
Регистрация: 03.07.2010
Сообщений: 2
По умолчанию

На вопрос мне ответили. ункция на 4 шаге была вызвана из второго, на 5 из первого и на 6 из второго.
Тему можно закрыть...

Последний раз редактировалось Stopafilm; 02.08.2010 в 09:09.
Stopafilm вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сортировка двумерного массива по столбцам методом быстрой сортировки( Хоара) и пирамидальной. tworc22 Помощь студентам 3 28.10.2011 23:05
Метод быстрой сортировки Nord18 Паскаль, Turbo Pascal, PascalABC.NET 1 05.06.2010 11:24
Метод быстрой сортировки Хоора Pascal Бармалей Помощь студентам 8 18.11.2009 21:21
сортировка массива Методом Хоара (быстрой сортировкой) wild-weight Паскаль, Turbo Pascal, PascalABC.NET 3 26.09.2009 16:46
Список с быстрой перемоткой(Delphi) drumerbaker Помощь студентам 6 13.06.2009 23:20