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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
#1

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

25.12.2012, 23:51. Просмотров 410. Ответов 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>;
Я что-то не врубаюсь как оперировать с векторами\
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.12.2012, 23:51     векторы и алгоритмы сортировки
Посмотрите здесь:

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

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

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

Алгоритмы сортировки. Подсчетом - C++
#include &lt;iostream&gt; #include &lt;time.h&gt; #include &lt;stdlib.h&gt; using namespace std; const int n = 10,m = 1; int a = {0}; ...

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

алгоритмы сортировки массивов - C++
помогите пожалуйста решить задачу на с++... Если у массива А(50) есть элемент, равный квадрату последнего элемента, то все элементы,...

Алгоритмы сортировки массивов - C++
Всем привет, хочу для общего развития узнать все способы сортировки массивов.(массив произвольный) (метод пузырька я знаю) какой из...

Основные алгоритмы сортировки - C++
Пом-гите решить, заранее благодарен Билет 3 1 Сортировка. Основные алгоритмы сортировки. 2 Решить задачу: представлен фрагмент...

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

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

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

Алгоритмы сортировки. Время выполнения - C++
Написал программу которая вычисляет время выполнения алгоритмов для среднего случая. Нужно сделать еще для лучшего и худшего случая. Для...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gray_fox
What a waste!
1443 / 1172 / 61
Регистрация: 21.04.2012
Сообщений: 2,449
Завершенные тесты: 3
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);
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
26.12.2012, 01:12  [ТС]     векторы и алгоритмы сортировки #3
Эх....было бы понятно\\\
gray_fox
What a waste!
1443 / 1172 / 61
Регистрация: 21.04.2012
Сообщений: 2,449
Завершенные тесты: 3
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
Elfenlide
23 / 23 / 1
Регистрация: 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);
}
Что тут происходит\
gray_fox
What a waste!
1443 / 1172 / 61
Регистрация: 21.04.2012
Сообщений: 2,449
Завершенные тесты: 3
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 минуты

Не по теме:

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

Yandex
Объявления
27.12.2012, 07:20     векторы и алгоритмы сортировки
Ответ Создать тему
Опции темы

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