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

@Elfenlide · Регистрация: 15.04.2012

У меня есть алгоритм сортировки In-place merge sort, для обычных массивов любого типа данных.

C++

#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>;
Я что-то не врубаюсь как оперировать с векторами\

@gray_fox · 26.12.2012, 00:37

C++

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++

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 · 26.12.2012, 01:12 **[ТС]**

Эх....было бы понятно\\\

@gray_fox · 26.12.2012, 01:17

Чего не понятно?

C++

#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 · 26.12.2012, 02:48 **[ТС]**

Сообщение от gray_fox

Чего не понятно?

Я не понимаю что вы сделали чтобы это работало.....я думал нужно перегружать функции и делать отдельно для вектора...что-то типо этого: template <class T>
void bogoSort(vector<T> &arr);
Я так делал другую сортировку:

C++

#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++

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 · 27.12.2012, 07:20

Сообщение от Elfenlide

я думал нужно перегружать функции и делать отдельно для вектора...что-то типо этого: template <class T>
void bogoSort(vector<T> &arr);

Ну можно и так сделать, если хочется, но это будет работать только в vector. Это

C++

template<typename Container>
void in_place_mergesort(Container & container) {
   in_place_mergesort(container.begin(), container.end());
}

будкт работать со всем, у чего есть методы begin и end, с std::deque, например. Container ведь может быть любым типом, вот только если у него не будет методов begin/end, будет ошибка компиляции. А это

C++

template<typename Value, int N>
void in_place_mergesort(Value (&array)[N]) {
   InPlaceMergesort(&array[0], N);
}

перегрузка для массивов, у них ведь нет методов. Если есть std::begin и std::end, то обе эти ф-ии можно заменить одной:

C++

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 минуты

Не по теме:

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

@Elfenlide 23 / 23 / 11 Регистрация: 15.04.2012 Сообщений: 183
	26.12.2012, 01:12 [ТС]	3
	Эх....было бы понятно\\\ 0