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

Быстрая сортировка - C++

Восстановить пароль Регистрация
 
QblAnko
0 / 0 / 0
Регистрация: 03.03.2013
Сообщений: 9
16.09.2013, 16:01     Быстрая сортировка #1
Помогите пожалуйста, при использовании алгоритма быстрой сортировки, конечный массив получается не отсортированным, хотя все операции проходят и при этом с правильными индексами.

Сортировка производится с 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");
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,915
Записей в блоге: 2
Завершенные тесты: 1
16.09.2013, 17:25     Быстрая сортировка #2
C++
1
Quicksort(vector<books>A, int l, int r)
копирование вектора
QblAnko
0 / 0 / 0
Регистрация: 03.03.2013
Сообщений: 9
16.09.2013, 20:00  [ТС]     Быстрая сортировка #3
А если без копирования как задать? Просто, например, books A невозможно, т.к. мне нужно передать именно вектор.
iRomul
 Аватар для iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 474
Завершенные тесты: 1
16.09.2013, 20:15     Быстрая сортировка #4
Передать вектор по ссылке?
QblAnko
0 / 0 / 0
Регистрация: 03.03.2013
Сообщений: 9
16.09.2013, 20:57  [ТС]     Быстрая сортировка #5
Спасибо, заработало
Yandex
Объявления
16.09.2013, 20:57     Быстрая сортировка
Ответ Создать тему
Опции темы

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