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

сортировка хоара - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.63
ТОрчОК
Заблокирован
08.08.2013, 13:48     сортировка хоара #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
void QuickSort(int* const a, int low, int N)
{
    int i = low, j = N;        
    int temp, p;
    p = a[(low+N)/2];   
    do {
        while (a[i] < p) i++;
        while (a[j] > p) j--;
 
        if (i <= j) {
            temp = a[i]; 
            a[i] = a[j]; 
            a[j] = temp;
            i++; j--;
         }
       } while (i <= j);
 
 
 
    if(j > low) 
        QuickSort(a, low, j);
    if(i < N) 
        QuickSort(a, i, N);
}
int main()
{
    int mas[6] = {6,3,7,1,2,5};
    int* pmas = mas;
    QuickSort(pmas, 0, sizeof(mas)/sizeof(int));
    std::copy(mas, mas + sizeof(mas)/sizeof(int), std::ostream_iterator<int>(std::cout, "\n"));
    system("pause");
    return 0;
}
Добавлено через 1 минуту
не работает как надо. плюс не понятен момент при первом заходе в цикл do while, что происходит в первых 2 циклах while. в них вообще не заходит?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
 Аватар для Catstail
21445 / 10230 / 1667
Регистрация: 12.02.2012
Сообщений: 17,105
08.08.2013, 13:51     сортировка хоара #2
Ты сортируешь массив из семи элементов, а значения присвоил только шести...
Если написать так:

C++
1
2
3
    int mas[] = {6,3,7,1,2,5};
    int* pmas = mas;
    QuickSort(pmas, 0, 6);
то все прекрасно работает.
ТОрчОК
Заблокирован
08.08.2013, 13:57  [ТС]     сортировка хоара #3
у меня при первом заходе в цикл do while после циклов while индексы равны 0 и 6, хотя переменная p = 1? почему?

Добавлено через 1 минуту
косяк, но это не столь важно до этого там их было 7

Добавлено через 4 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
 do {
        while (a[i] < p) i++;
        while (a[j] > p) j--;
        std::cout << i << j;
        if (i <= j) {
            temp = a[i]; 
            a[i] = a[j]; 
            a[j] = temp;
            i++; j--;
         }
       } while (i <= j);
после первого захода у меня индексы i и j равны 0 и 6. то есть не в один цикл while программа не заходит, но почему?
Catstail
Модератор
 Аватар для Catstail
21445 / 10230 / 1667
Регистрация: 12.02.2012
Сообщений: 17,105
08.08.2013, 14:03     сортировка хоара #4
Цитата Сообщение от ТОрчОК Посмотреть сообщение
индексы равны 0 и 6, хотя переменная p = 1? почему?
- давай посмотрим:

low=0; N=6; -> low+N=6 -> (low+N)/2=3 -> p=a[3]=1 (см. свой массив). Что не так?

Добавлено через 3 минуты
Цикл
C++
1
while (a[i] < p) i++;
не прорабатывает ни разу, т.к. первый же i-й элемент больше p
ТОрчОК
Заблокирован
08.08.2013, 14:17  [ТС]     сортировка хоара #5
это я понял, а вот
C++
1
while (a[j] > p) j--;
здесь j = N = 6 и цикл тоже не срабатывает ни разу, хотя все элементы больше чем р

Добавлено через 11 минут
никак не пойму
Catstail
Модератор
 Аватар для Catstail
21445 / 10230 / 1667
Регистрация: 12.02.2012
Сообщений: 17,105
08.08.2013, 14:28     сортировка хоара #6
Вставим отладочную печать:

C++
1
2
3
4
5
6
7
8
9
    do {
        while (a[i] < p) i++;
        while (a[j] > p) j--;
 
cout << "p=" << p << endl;
cout << "i=" << i << endl;
cout << "j=" << j << endl << endl;
 
/////
И убеждаемся, что все меняется, как и положено:

p=1
i=0
j=3 !!!

p=1
i=1
j=0

p=6
i=2
j=5

p=6
i=3
j=4

p=5
i=2
j=3

p=3
i=1
j=2

p=7
i=5
j=5

1 2 3 5 6 <- результат
Press any key to continue
ТОрчОК
Заблокирован
08.08.2013, 14:33  [ТС]     сортировка хоара #7
у меня все совершенно по другому

для первого:
p=1
i=0
j=6

остальное тоже, в чем может быть причина?
Catstail
Модератор
 Аватар для Catstail
21445 / 10230 / 1667
Регистрация: 12.02.2012
Сообщений: 17,105
08.08.2013, 14:39     сортировка хоара #8
Выложи свой код с отл. печатью
ТОрчОК
Заблокирован
08.08.2013, 14:58  [ТС]     сортировка хоара #9
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
void QuickSort(int* const a, int low, int N)
{
    int i = low, j = N;        
    int temp, p;
    p = a[(low+N)/2];   
    do {
        while (a[i] < p) i++;
        while (a[j] > p) j--;
    std::cout << "p=" << p << std::endl;
        std::cout << "i=" << i << std::endl;
        std::cout << "j=" << j << std::endl << std::endl;
        if (i <= j) {
            temp = a[i]; 
            a[i] = a[j]; 
            a[j] = temp;
            i++; j--;
         }
       } while (i <= j);
 
    if(j > low) 
        QuickSort(a, low, j);
    if(i < N) 
        QuickSort(a, i, N);
}
int main()
{
    int mas[6] = {6,3,7,1,2,5};
    int* pmas = mas;
    QuickSort(pmas, 0, 6);
    std::copy(mas, mas + 6, std::ostream_iterator<int>(std::cout, "\n"));
    system("pause");
    return 0;
}
Добавлено через 16 минут
p=1
i=0
j=6

p=1
i=1
j=3

p=1
i=2
j=1

p=-858993460
i=0
j=0

p=2
i=2
j=4

p=2
i=3
j=2

p=7
i=4
j=6

p=7
i=6
j=5

p=6
i=4
j=5

p=3
i=3
j=3
Catstail
Модератор
 Аватар для Catstail
21445 / 10230 / 1667
Регистрация: 12.02.2012
Сообщений: 17,105
08.08.2013, 15:13     сортировка хоара #10
Я немного ошибся: поставь в 29-й строке

C++
1
QuickSort(pmas, 0, 5); // ведь индекс последнего эл-та = 5 (а не 6)
и посмотри, что будет
ТОрчОК
Заблокирован
08.08.2013, 15:25  [ТС]     сортировка хоара #11
ну все равно в цикл
C++
1
while (a[j] > p) j--;
при первом заходе в do while не входит
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.08.2013, 15:32     сортировка хоара
Еще ссылки по теме:

C++ Сортировка Хоара
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Belfegor
Ghost
 Аватар для Belfegor
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 524
08.08.2013, 15:32     сортировка хоара #12
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
#include <iostream>
#include <vector>
 
using namespace std;
 
template < typename T, typename X, typename Y>
void QuickSort(vector <T> &v, X b0, Y e0) {
    auto e = e0;
    auto d = v[e];
    auto b = b0;
    do {
        while (v[b] < d)
            ++b;
        while (v[e] > d)
            --e;
        if (b <= e) {
            swap(v[b], v[e]);
            ++b;
            --e;
        }
    } while (b <= e);
    if (e > b0) {
        QuickSort(v, b0, e);
    }
    if (b < e0) {
        QuickSort(v, b, e0);
    }
}
 
int main() {
    vector < int > v;
    for (int i = 0; i < 20; i++) {
        v.push_back(i);
    }
    for (int i = 0; i < v.size(); i++) {
        swap(v[i], v[rand() % (v.size() - i) + i]);
    }
    for (auto i : v) {
        cout << i << ' ';
    }
    cout << endl;
    QuickSort(v, 0, v.size() - 1);
    for (auto i : v) {
        cout << i << ' ';
    }
    cout << endl;
    return 0;
}
Yandex
Объявления
08.08.2013, 15:32     сортировка хоара
Ответ Создать тему
Опции темы

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