0 / 0 / 0
Регистрация: 03.03.2013
Сообщений: 9
1

Быстрая сортировка

16.09.2013, 16:01. Показов 503. Ответов 4
Метки нет (Все метки)

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

Сортировка производится с 44 по 49.

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <vector.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
 
using namespace std;
 
int l, r, steps;
 
struct books {
    char naimen[50];
    int god_izdan;
};
 
void cmp() {
    int n = 5;
    printf("nlog2(n): %0.3f\nn2: %0.0f\nsteps: %i\n", n * log(n) / log(2),
        pow(n, 2), steps);
}
 
void vuvod(vector<books>A) {
    for (int i = 0; i < 5; i++) {
        printf("naimen: %s\tgod_izdan: %i\n", A[i].naimen, A[i].god_izdan);
    }
    printf("\n");
}
 
int Partition(vector<books>A, int l, int r) {
    int x, cg, i, j;
    char cn[50];
    x = A[l].god_izdan;
    i = l;
    j = r;
    while (1) {
        steps++;
        while (A[i].god_izdan < x) {
            i += 1;
        }
        steps++;
        while (A[j].god_izdan > x) {
            j -= 1;
        }
        if (i < j) {
            cg = A[i].god_izdan;
            A[i].god_izdan = A[j].god_izdan;
            A[j].god_izdan = cg;
            strcpy(cn, A[i].naimen);
            strcpy(A[j].naimen, A[i].naimen);
            strcpy(A[j].naimen, cn);
            i += 1;
            j -= 1;
        }
        else {
            return j;
        }
    }
}
 
void Quicksort(vector<books>A, int l, int r) {
    int q;
    if (l < r) {
        q = Partition(A, l, r);
        Quicksort(A, l, q);
        Quicksort(A, q + 1, r);
    }
}
 
void main() {
    randomize();
    l = 0;
    r = 4;
    steps = 0;
    vector<books>A(5);
    strcpy(A[0].naimen, "000");
    strcpy(A[1].naimen, "111");
    strcpy(A[2].naimen, "222");
    strcpy(A[3].naimen, "333");
    strcpy(A[4].naimen, "444");
    for (int i = 0; i < 5; i++) {
        A[i].god_izdan = random(10);
    }
    vuvod(A);
    Quicksort(A, l, r);
    vuvod(A);
    cmp();
    system("pause");
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.09.2013, 16:01
Ответы с готовыми решениями:

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным...

Быстрая сортировка (сортировка Хоара) для связных списков
есть у кого готовый алгоритм? или подскажите как реализовать

Сортировка Слиянием vs Быстрая Сортировка - что лучше
Народ, помогите разобраться какой из методов сортировки лучше &quot;Сортировка Слиянием&quot; или &quot;Быстрая...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода...

4
Don't worry, be happy
17758 / 10526 / 2030
Регистрация: 27.09.2012
Сообщений: 26,502
Записей в блоге: 1
16.09.2013, 17:25 2
C++
1
Quicksort(vector<books>A, int l, int r)
копирование вектора
1
0 / 0 / 0
Регистрация: 03.03.2013
Сообщений: 9
16.09.2013, 20:00  [ТС] 3
А если без копирования как задать? Просто, например, books A невозможно, т.к. мне нужно передать именно вектор.
0
160 / 101 / 14
Регистрация: 17.10.2012
Сообщений: 488
16.09.2013, 20:15 4
Передать вектор по ссылке?
1
0 / 0 / 0
Регистрация: 03.03.2013
Сообщений: 9
16.09.2013, 20:57  [ТС] 5
Спасибо, заработало
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.09.2013, 20:57
Помогаю со студенческими работами здесь

Быстрая сортировка (сортировка методом Хоара)
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные элементы в порядке...

Сортировка Хоара / Быстрая сортировка
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int...

Сортировка расчёской и быстрая сортировка
В файле in.txt записана последовательность целых чисел. Заданными методами отсортировать числа и...

Быстрая сортировка
Смотрел в тему посвященной быстрой сортировке, и не совсем понял. написал подобный код. Хотелось...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru