Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
23 / 23 / 11
Регистрация: 15.04.2012
Сообщений: 183
1

векторы и алгоритмы сортировки

25.12.2012, 23:51. Показов 631. Ответов 5
Метки нет (Все метки)

У меня есть алгоритм сортировки In-place merge sort, для обычных массивов любого типа данных.
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
#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
template<class T>
void merge(T *a, int sizei, int sizej);
 
template<class T>
void InPlaceMergesort(T *a, int len);
 
template<class T>
void InPlaceMergesort(T *a, int len) {
   int listsize, xsize;
 
    for (listsize = 1; listsize <= len; listsize*=2) {
        for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) {
            merge(&a[i], listsize, listsize);
        }
    }
 
    listsize /= 2;
 
    xsize = len % listsize;
    if (xsize > 1)
        InPlaceMergesort(&a[len-xsize], xsize);
    merge(a, listsize, xsize);
}
 
template<class T>
void merge(T *a, int sizei, int sizej) {
    T temp;
    int ii = 0;
    int ji = sizei;
    int flength = sizei+sizej;
 
    for (int f = 0; f < (flength-1); f++) {
        if (sizei == 0 || sizej == 0)
            break;
 
        if (a[ii] < a[ji]) {
            ii++;
            sizei--;
        }
        else {
            temp = a[ji];
 
            for (int z = (ji-1); z >= ii; z--)
                a[z+1] = a[z];  
            ii++;
 
            a[f] = temp;
 
            ji++;
            sizej--;
        }
    }
}
 
int main()
{
   const int kol = 8;
cout << "In-place merge sort: " << endl;
    cout << "char mas[] sort:" << endl;
    char mas3[kol];
    mas3[0] = 'x'; mas3[1] = 't'; mas3[2] = 'p'; mas3[3] = 'i'; mas3[4] = 'v'; mas3[5] = 'm'; mas3[6] = 'f'; mas3[7] = 'e';
    InPlaceMergesort(mas3, kol);
    for (int i = 0; i < kol; i++)
        cout << mas3[i] << " ";
    cout << endl << endl;
}
Помогите адаптировать его для того чтобы можно было использовать не обычные массивы а std::vector<T>;
Я что-то не врубаюсь как оперировать с векторами\
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.12.2012, 23:51
Ответы с готовыми решениями:

Написать две функции сортировки массива целых чисел, реализующих заданные алгоритмы сортировки – один из класса квадрат
#include &lt;stdio.h&gt; #include &quot;stdafx.h&quot; #include &quot;iostream&quot; #include &lt;stdlib.h&gt; #include...

алгоритмы сортировки
нужно выполнить сортировку массива целых чисел 3 методами: простыми включениями, простым выбором,...

Алгоритмы Сортировки
помогите пожалуйста выполнить вот такое задание... завтра утром нужно сдать.... 1) Реализовать...

Алгоритмы сортировки массивов
Дан массив А(50). Отсортировать элементы, предшествующие первому нулевому элементу, по возрастанию...

5
What a waste!
1604 / 1297 / 179
Регистрация: 21.04.2012
Сообщений: 2,723
26.12.2012, 00:37 2
C++
1
2
3
4
5
6
7
8
template<typename Iterator>
void in_place_mergesort(Iterator const first, Iterator const last) {
   InPlaceMergesort(&*first, static_cast<int>(std::distance(first, last)));
}
 
// ....
 
in_place_mergesort(vector.begin(), vector.end());
Опционально:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename Container>
void in_place_mergesort(Container & container) {
   in_place_mergesort(container.begin(), container.end());
}
 
template<typename Value, int N>
void in_place_mergesort(Value (&array)[N]) {
   InPlaceMergesort(&array[0], N);
}
 
// ...
 
in_place_mergesort(vector);
in_place_mergesort(plainArray);
1
23 / 23 / 11
Регистрация: 15.04.2012
Сообщений: 183
26.12.2012, 01:12  [ТС] 3
Эх....было бы понятно\\\
0
What a waste!
1604 / 1297 / 179
Регистрация: 21.04.2012
Сообщений: 2,723
26.12.2012, 01:17 4
Чего не понятно?
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
template<class T>
void merge(T *a, int sizei, int sizej);
 
template<class T>
void InPlaceMergesort(T *a, int len);
 
template<class T>
void InPlaceMergesort(T *a, int len) {
   int listsize, xsize;
 
    for (listsize = 1; listsize <= len; listsize*=2) {
        for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) {
            merge(&a[i], listsize, listsize);
        }
    }
 
    listsize /= 2;
 
    xsize = len % listsize;
    if (xsize > 1)
        InPlaceMergesort(&a[len-xsize], xsize);
    merge(a, listsize, xsize);
}
 
template<class T>
void merge(T *a, int sizei, int sizej) {
    T temp;
    int ii = 0;
    int ji = sizei;
    int flength = sizei+sizej;
 
    for (int f = 0; f < (flength-1); f++) {
        if (sizei == 0 || sizej == 0)
            break;
 
        if (a[ii] < a[ji]) {
            ii++;
            sizei--;
        }
        else {
            temp = a[ji];
 
            for (int z = (ji-1); z >= ii; z--)
                a[z+1] = a[z];  
            ii++;
 
            a[f] = temp;
 
            ji++;
            sizej--;
        }
    }
}
 
 
template<typename Iterator>
void in_place_mergesort(Iterator const first, Iterator const last) {
   InPlaceMergesort(&*first, static_cast<int>(std::distance(first, last)));
}
 
template<typename Container>
void in_place_mergesort(Container & container) {
   in_place_mergesort(container.begin(), container.end());
}
 
template<typename Value, int N>
void in_place_mergesort(Value (&array)[N]) {
   InPlaceMergesort(&array[0], N);
}
 
 
int main()
{
   const int kol = 8;
cout << "In-place merge sort: " << endl;
    cout << "char mas[] sort:" << endl;
    char mas3[kol];
    mas3[0] = 'x'; mas3[1] = 't'; mas3[2] = 'p'; mas3[3] = 'i'; mas3[4] = 'v'; mas3[5] = 'm'; mas3[6] = 'f'; mas3[7] = 'e';
    char mas1[kol];
    std::copy(mas3, mas3 + kol, mas1);
    char mas2[kol];
    std::copy(mas3, mas3 + kol, mas2);
    std::vector<char> v1(mas3, mas3 + kol);
    std::vector<char> v2(v1);
    std::string s1(mas3, mas3 + kol);
    std::string s2(s1);
    InPlaceMergesort(mas3, kol);
    for (int i = 0; i < kol; i++)
        cout << mas3[i] << " ";
    cout << endl << endl;
    in_place_mergesort(&mas1[0], &mas1[0] + kol);
    for (int i = 0; i < kol; i++)
        cout << mas1[i] << " ";
    cout << endl << endl;
    in_place_mergesort(&mas2[0], &mas2[0] + kol);
    for (int i = 0; i < kol; i++)
        cout << mas2[i] << " ";
    cout << endl << endl;
    in_place_mergesort(v1.begin(), v1.end());
    for (int i = 0; i < kol; i++)
        cout << v1[i] << " ";
    cout << endl << endl;
    in_place_mergesort(v2);
    for (int i = 0; i < kol; i++)
        cout << v2[i] << " ";
    cout << endl << endl;
    in_place_mergesort(s1.begin(), s1.end());
    for (int i = 0; i < kol; i++)
        cout << s1[i] << " ";
    cout << endl << endl;
    in_place_mergesort(s2);
    for (int i = 0; i < kol; i++)
        cout << s2[i] << " ";
    cout << endl << endl;
}
http://liveworkspace.org/code/1HVJW9
0
23 / 23 / 11
Регистрация: 15.04.2012
Сообщений: 183
26.12.2012, 02:48  [ТС] 5
Цитата Сообщение от gray_fox Посмотреть сообщение
Чего не понятно?
Я не понимаю что вы сделали чтобы это работало.....я думал нужно перегружать функции и делать отдельно для вектора...что-то типо этого: template <class T>
void bogoSort(vector<T> &arr);
Я так делал другую сортировку:
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <iterator>
#include <string>
using namespace std;
 
template <class T>
void bogoSort(vector<T> &arr);
 
template <class T>
void bogoSort(T &arr, int kol); 
 
 
//сортировка для векторов
template <class T>
void bogoSort(vector<T> &arr)
{
    const auto begin = arr.begin();
    const auto end = arr.end();
 
    while (!is_sorted(begin, end))
        random_shuffle(begin, end);
}
 
//проверка на сортированность в порядке возрастания
template <class T>
int correct( T *arr, int size )
{
    while (--size > 0)
        if (arr[size - 1] > arr[size])
            return 0;
    return 1;
}
//рандом перемешка
template <class T>
void shuffle( T *arr, int size )
{
    int i;
    for (i = 0; i < size; i++)
    {
        int k = rand() % size;
        T temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
}
 
//сортировка БОгоСорт для массивов 
template <class T>
void bogoSort(T *arr, int size )
{
    while (!correct(arr, size))
        shuffle(arr, size);
}
 
int main(){
vector<char> charData;
    charData.push_back('q'); charData.push_back('g');  charData.push_back('v'); charData.push_back('z'); charData.push_back('w');
    charData.push_back('p'); charData.push_back('n'); charData.push_back('b');
    cout << "BogoSort\nVector<char>: " << endl;
    bogoSort(charData);
    for(size_t i = 0; i < charData.size(); i++)
        cout << charData[i] << " ";
    cout << endl << endl;
return 0;
}
Добавлено через 18 минут
И всёравно, если я определю например пользовательский тип, то с ним даже ваш код не сработает....
Но мне важно понять что вы сделали....

Добавлено через 20 минут
А не, прошу прощения, с пользовательскими типам данных тоже работает, но я всё равно не понимаю как и каким образом...
Немогли бы вы пояснить:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename Iterator>
void in_place_mergesort(Iterator const first, Iterator const last) {
   InPlaceMergesort(&*first, static_cast<int>(std::distance(first, last)));
}
 
template<typename Container>
void in_place_mergesort(Container & container) {
   in_place_mergesort(container.begin(), container.end());
}
 
template<typename Value, int N>
void in_place_mergesort(Value (&array)[N]) {
   InPlaceMergesort(&array[0], N);
}
Что тут происходит\
0
What a waste!
1604 / 1297 / 179
Регистрация: 21.04.2012
Сообщений: 2,723
27.12.2012, 07:20 6
Цитата Сообщение от Elfenlide Посмотреть сообщение
я думал нужно перегружать функции и делать отдельно для вектора...что-то типо этого: template <class T>
void bogoSort(vector<T> &arr);
Ну можно и так сделать, если хочется, но это будет работать только в vector. Это
C++
1
2
3
4
template<typename Container>
void in_place_mergesort(Container & container) {
   in_place_mergesort(container.begin(), container.end());
}
будкт работать со всем, у чего есть методы begin и end, с std::deque, например. Container ведь может быть любым типом, вот только если у него не будет методов begin/end, будет ошибка компиляции. А это
C++
1
2
3
4
template<typename Value, int N>
void in_place_mergesort(Value (&array)[N]) {
   InPlaceMergesort(&array[0], N);
}
перегрузка для массивов, у них ведь нет методов. Если есть std::begin и std::end, то обе эти ф-ии можно заменить одной:
C++
1
2
3
4
template<typename Container>
void in_place_mergesort(Container & container) {
   in_place_mergesort(std::begin(container), std::end(container));
}
C++
1
2
template<typename Iterator>
void in_place_mergesort(Iterator const first, Iterator const last)
это прототип а ля stl (можешь посмотреть, какие прототипы у алгоритмов stl здесь, например std::sort), последовательность (std::vector, массив и т.д.) представляется в виде двух итераторов: первый указывает на начало последовательности, второй - на "следующий за последним" элемент. Iterator может быть чем угодно, что ведёт себя как итератор, иначе просто не скомпилируется. Т.е. для std::vector<T> Iterator = std::vector<T>::iterator, для массива из int Iterator = int *.
C++
1
InPlaceMergesort(&*first, static_cast<int>(std::distance(first, last)));
Здесь просто вызывается твоя ф-ия. Что бы её вызвать, надо получить указатель на первый элемент (&*first) и размер последовательности (std::distance(first, last)). В действительности это не совсем хорошо, т.к. будет работать только с тем, что последовательно располагает элементы в памяти (массив, std::vector), но не с std::deque, например. Это потому что твоя ф-я явно принимает указатель, что бы от этого избывиться, надо абстрагироваться от указателя до итератора, т.е. переписать прототип твоей ф-ии
C++
1
2
template<class T>
void InPlaceMergesort(T *a, int len);
так, например:
C++
1
2
template<typename Iterator>
void InPlaceMergesort(Iterator a, int len);
или лучше так:
C++
1
2
template<typename Iterator>
void InPlaceMergesort(Iterator begin, Iterator end);
Тогда твоя ф-я будет работать с любыми итераторами с произвольным доступом.

Добавлено через 3 минуты

Не по теме:

да, я очень понятно объясняю)

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.12.2012, 07:20

STL алгоритмы сортировки
Здрасти. В STL есть алгоритмы sort - упорядочивает последовательность и stable_sort -...

Алгоритмы внешней сортировки
Добрый день. Интересуют такие алгоритмы сортировки, как многофазное слияние, каскадное слияние и...

типовые алгоритмы сортировки
типовые алгоритмы сортировки как они выглядят ?

Алгоритмы сортировки и поиска
Помогите, пожалуйста!! Нужно выполнить сортировку целочисленного массива (поиск в массиве) из n...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.