Форум программистов, компьютерный форум CyberForum.ru

Вопросы насчёт быстрой сортировки - C++

Восстановить пароль Регистрация
 
Saf
0 / 0 / 0
Регистрация: 30.07.2010
Сообщений: 6
30.07.2010, 11:47     Вопросы насчёт быстрой сортировки #1
Здравствуйте. Объясните, пожалуйста. Есть алгоритм быстрой сортировки:
Код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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)Почему срабатывает рекурсивно второй вариант (шаг 4), если значение i=1 (i<1). Т.е. неподходят оба варианта и наступает конец функции.
2)Откуда значения: left: 3 и right: 4 (шаг 4).
P.S. Массив сортируется правильно.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2010, 11:47     Вопросы насчёт быстрой сортировки
Посмотрите здесь:

C++ Поиск самой быстрой сортировки
Реализовать алгоритм быстрой сортировки C++
C++ Тонкости быстрой сортировки
C++ Алгорим быстрой сортировки
Визуализатор быстрой сортировки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sekt
 Аватар для Sekt
156 / 155 / 10
Регистрация: 29.04.2009
Сообщений: 637
30.07.2010, 13:38     Вопросы насчёт быстрой сортировки #2
Цитата Сообщение от Saf Посмотреть сообщение
Почему срабатывает рекурсивно второй вариант (шаг 4), если значение i=1 (i<1). Т.е. неподходят оба варианта и наступает конец функции
где у вас значение i<1?

Цитата Сообщение от Saf Посмотреть сообщение
Откуда значения: left: 3 и right: 4 (шаг 4).
Границы вашего массива. 0 -начало Left 8-Right конец
Saf
0 / 0 / 0
Регистрация: 30.07.2010
Сообщений: 6
30.07.2010, 14:44  [ТС]     Вопросы насчёт быстрой сортировки #3
где у вас значение i<1?
Я ошибся. i<right(1<1).
Границы вашего массива. 0 -начало Left 8-Right конец
Про границы массива мне понятно. Мне непонятно откуда берутся эти границы - 3 и 4 (исходя из кода). Если не срабатывает условие на шаге 3:
C++
1
if (left < j)
( j стал меньше 0) и
C++
1
if (i < right)
(i=1 и right=1), то каким образом шаг 4 является следствием рекурсии quickSort(arr, i, right , 'b') ?
Saf
0 / 0 / 0
Регистрация: 30.07.2010
Сообщений: 6
01.08.2010, 20:18  [ТС]     Вопросы насчёт быстрой сортировки #4
На вопрос мне ответили. Функция на 4 шаге была вызвана из второго, на 5 из первого и на 6 из второго.
Тему можно закрыть...
Yandex
Объявления
01.08.2010, 20:18     Вопросы насчёт быстрой сортировки
Ответ Создать тему
Опции темы

Текущее время: 07:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru