Модераторы: bsa
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Сортировка слиянием. Количество перестановок 
:(
    Опции темы
Rostislav1
Дата 5.5.2013, 09:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 5
Регистрация: 5.5.2013

Репутация: нет
Всего: нет
Нужно найти минимальное количество перестановок соседних элементов последовательности, необходимое для того, чтобы отсортировать ее по возрастанию. Пробовал просто посчитать кол-во шагов, за которое сортировка пузырьком сделает это - не проходит по времени. Посоветовали сортировку слиянием использовать.
Код

#include<stdio.h>
int flag;
template<class T> void Merge(T const *const A, int const nA,
                             T const *const B, int const nB,
                             T *const C)
{ //Выполнить слияние массива A, содержащего nA элементов,
  //  и массива B, содержащего nB элементов.
  //  Результат записать в массив C.
 
    int a(0), b(0); //Номера текущих элементов в массивах A и B
 
    while( a+b < nA+nB ) //Пока остались элементы в массивах
    {
        if( (b>=nB) || ( (a<nA) && (A[a]<=B[b]) ) )
        { //Копирую элемент из массива A
            C[a+b] = A[a];
            ++a;
        } else { //Копирую элемент из массива B
            C[a+b] = B[b];
            ++b;
        }
    }
}
template<class T> int MergeSort(T *const A, int const n)
{ //Отсортировать массив A, содержащий n элементов
    if( n < 2 ) return 0; //Сортировка не нужна
 
    if( n == 2 ) //Два элемента проще поменять местами,
    {            //  если нужно, чем делать слияние
        if( A[0] > A[1] )
        { 
            T const t=A[0]; A[0]=A[1]; A[1]=t; 
            flag++;
        }       
    }
    
    MergeSort(A    , n/2  ); //Сортируем первую половину
    MergeSort(A+n/2, n-n/2); //Сортируем вторую половину
     
 
    T *const B( new T[n] ); //Сюда запишем результат слияния
 
    Merge(A,n/2, A+n/2,n-n/2, B); //Слияние половин
 
    //Копирование результата слияния в исходный массив:
    for(int i = 0; i < n; i++) 
    {
        A[i]=B[i];
    }
    return flag; //Кол-во перестановок?
    delete[n] B; //Удаляем временный буфер
}

Вот, что получилось, но эта функция не правильно считает кол-во перестановок. Где я ошибся?
PM MAIL   Вверх
feodorv
Дата 5.5.2013, 15:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45
Цитата(Rostislav1 @  5.5.2013,  10:44 Найти цитируемый пост)
Где я ошибся? 

По сути, везде. Вам можно переставлять только соседние элементы, а Вы что делаете?


Цитата(Rostislav1 @  5.5.2013,  10:44 Найти цитируемый пост)
    return flag; //Кол-во перестановок?
    delete[n] B; //Удаляем временный буфер

А это что такое?)))


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
Rostislav1
Дата 5.5.2013, 16:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 5
Регистрация: 5.5.2013

Репутация: нет
Всего: нет
Цитата

А это что такое?))) 

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

 if( A[0] > A[1] )
        { 
            T const t=A[0]; A[0]=A[1]; A[1]=t; 
            flag++;
        }       
PM MAIL   Вверх
math64
Дата 5.5.2013, 19:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72
Нужно же посчитать число перестановок, а саму сортировку делать не обязательно?
Используя сортировку слиянием, во время слияния делаем неподсчитанное число перестановок, и не обезательно соседних.
Сортировка будет быстрее, но ответ будет неправильным.
Если сливать по правилам - переставляя только сосединие элементы - будет много лишних перестановок.
Чтобы получить правильный ответ, нужно делать сортировку пузырьком, или, не делая саму сортировку, сравнить все элементы попарно.
Число сравнений N*(N-1)/2 - много, но ответ будет правильным.
PM   Вверх
feodorv
Дата 5.5.2013, 19:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45
Цитата(Rostislav1 @  5.5.2013,  17:30 Найти цитируемый пост)
вот здесь

Вот именно здесь сначала return, потом delete... Некошерно...

Цитата(Rostislav1 @  5.5.2013,  17:30 Найти цитируемый пост)
в конечном итоге

Цитата(Rostislav1 @  5.5.2013,  10:44 Найти цитируемый пост)
    Merge(A,n/2, A+n/2,n-n/2, B); //Слияние половин

Здесь-то Вы тоже делаете перемещения, но их-то не учитываете во flags... 


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
Rostislav1
Дата 5.5.2013, 21:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 5
Регистрация: 5.5.2013

Репутация: нет
Всего: нет
Цитата(math64 @  5.5.2013,  19:21 Найти цитируемый пост)
Нужно же посчитать число перестановок, а саму сортировку делать не обязательно?

Да, не обязательно.
Цитата(math64 @  5.5.2013,  19:21 Найти цитируемый пост)
Чтобы получить правильный ответ, нужно делать сортировку пузырьком, или, не делая саму сортировку, сравнить все элементы попарно.
Число сравнений N*(N-1)/2 - много, но ответ будет правильным. 

так и делал, но как уже говорил - не проходит по времени. Те, кто сделал утверждают, что использовали именно сортировку слиянием. Может быть есть еще какой-нибудь более быстрый вариант?

Цитата(feodorv @  5.5.2013,  19:46 Найти цитируемый пост)
Вот именно здесь сначала return, потом delete... Некошерно...

Согласен smile Исправлю.
 
PM MAIL   Вверх
math64
Дата 5.5.2013, 22:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72
Сначала можно из массива элементов сделать массив или список указателей - тогда сами элементы копировать не надо.
При слиянии временный массив не создаётся, перемещаются указатели и подсчитывается число перемещений, со списком вроде будет быстрее.
Заодно сделайте вариант с пузырьком - для проверки правильности ответа.
PM   Вверх
Rostislav1
Дата 6.5.2013, 12:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 5
Регистрация: 5.5.2013

Репутация: нет
Всего: нет
Переделал, но снова не верно считает... 
Код

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;
int tmp;
vector<int>mas;
int merge(vector<int>&mas, int l, int m, int r)
{
    int per = 0;
    vector<int> buffer(r - l + 1);
    int pos1 = l;
    int pos2 = m+1;
    int posB = 0;

    while(pos1 <=m && pos2<=r)
    {
        if(mas[pos1] < mas[pos2])
            buffer[posB++] = mas[pos1++];
        else
        {
            buffer[posB++] = mas[pos2++];
            per+=m-pos1 + l;
        }
    }

    while (pos1 <=m)
        buffer[posB++] = mas[pos1++];
    while (pos2 <=r)
        buffer[posB++] = mas[pos2++];
    copy(buffer.begin(), buffer.end(), mas.begin()+l);
    return per;

}
int merge_sort(vector<int> & mas, int l, int r)
{
    int per = 0;
    if(l == r)
        return per;
    int m = (l + r)/2;
    per +=merge_sort(mas, l,m);
    per +=merge_sort(mas, m+1,r);
    per += merge(mas, l, m, r);
    return per;
}
void input()
{
    int n ;
    vector<int> mas;
    scanf("%d", &n);
    mas.resize(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &mas[i]);
    int per = merge_sort(mas,0,n-1);
    tmp = per;
}
void output()
{
    cout<<tmp;
}
int main()
{
    input();
    output();
}


Это сообщение отредактировал(а) Rostislav1 - 6.5.2013, 13:15
PM MAIL   Вверх
feodorv
Дата 6.5.2013, 13:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45
Цитата(Rostislav1 @  6.5.2013,  13:41 Найти цитируемый пост)
снова не верно считает...

Вы всё время обнуляете счётчик:
Цитата(Rostislav1 @  6.5.2013,  13:41 Найти цитируемый пост)
6:  int per;

Цитата(Rostislav1 @  6.5.2013,  13:41 Найти цитируемый пост)
10:    per = 0;

Цитата(Rostislav1 @  6.5.2013,  13:41 Найти цитируемый пост)
37:    per = 0;

Тогда как нужно:
Цитата(Rostislav1 @  6.5.2013,  13:41 Найти цитируемый пост)
6:  int per;

Цитата(Rostislav1 @  6.5.2013,  13:41 Найти цитируемый пост)
10:    int per = 0;

Цитата(Rostislav1 @  6.5.2013,  13:41 Найти цитируемый пост)
37:    int per = 0;

Цитата(Rostislav1 @  6.5.2013,  13:41 Найти цитируемый пост)
int main()
{
    int per = input();
    output( per );
}

с соответствующими изменениями в input и output...


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
Rostislav1
Дата 6.5.2013, 13:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 5
Регистрация: 5.5.2013

Репутация: нет
Всего: нет
да, я заметил уже, отредактировал, но все равно не правильно считает(в предыдущем комментарии уже выложил отредактированную версию, но скину еще раз)

Код

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int tmp;
vector<int>mas;
int merge(vector<int>&mas, int l, int m, int r)
{
    int per = 0;
    vector<int> buffer(r - l + 1);
    int pos1 = l;
    int pos2 = m+1;
    int posB = 0;
    while(pos1 <=m && pos2<=r)
    {
        if(mas[pos1] < mas[pos2])
            buffer[posB++] = mas[pos1++];
        else
        {
            buffer[posB++] = mas[pos2++];
            per+=m-pos1 + l;
        }
    }
    while (pos1 <=m)
        buffer[posB++] = mas[pos1++];
    while (pos2 <=r)
        buffer[posB++] = mas[pos2++];
    copy(buffer.begin(), buffer.end(), mas.begin()+l);
    return per;
}
int merge_sort(vector<int> & mas, int l, int r)
{
    int per = 0;
    if(l == r)
        return per;
    int m = (l + r)/2;
    per +=merge_sort(mas, l,m);
    per +=merge_sort(mas, m+1,r);
    per += merge(mas, l, m, r);
    return per;
}
void input()
{
    int n ;
    vector<int> mas;
    scanf("%d", &n);
    mas.resize(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &mas[i]);
    int per = merge_sort(mas,0,n-1);
    tmp = per;
}
void output()
{
    cout<<tmp;
}
int main()
{
    input();
    output();
}
PM MAIL   Вверх
math64
Дата 6.5.2013, 17:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72
Зачем вы создаёте vector<int> buffer? Нужно всё делать в vector<int>&mas.
Примерно так:
Код

int merge(vector<int>&mas, int l, int m, int r)
{
    int per = 0;
    while(l < m && m+1 < r) {
        if (mas[l] <= mas[m+1]) {
           l++;
        } else {
          // переставляем mas[m+1] на место mas[l] 
          per += m+1-l;
          l++;
          m++;
        }
    }
    return per;
}
PM   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0593 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.