VPF::Методы сортировки с квадратичной трудоемкостью

M9C1K

Дата 4.9.2009, 19:40 (ссылка)

(голосов:3)

Загрузка ...

Новичок

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

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

Порядок выполнения работы:
1.    Разработать процедуры сортировки массива целых чисел методом прямого выбора, методом пузырьковой сортировки и методом шейкерной сортировки (язык программирования  Си).
2.    Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве.
3.    Во время сортировки предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.
4.    Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве)
5.    Проанализировать полученные результаты. (Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности?)

Помогите пожалуйста разобраться!
Программа есть , тока не запускается ->

Код

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

//максимальная длина массива
const int maxn=500;

int ar[maxn],br[maxn],cr[maxn],dr[maxn];
int kolc,kolm;

//метод прямого выбора
int prv(int size,int* arr)
{
    int i,k,b;
    int m,c;
    int min;
    //количество пересылок и сравнений
    m=0; c=0;
    //проходимся по массиву с 0 до сайз-2
    for (i=0; i<size-1; i++)
    {
        min=i;
        //проходимся с и до конца массива и ищем минимальный
        for (k=i+1; k<size; k++)
        {
            c++;
            if (arr[k]<arr[min]) min=k;
        }
        if (min!=i)
        {
            b=arr[i]; arr[i]=arr[min]; arr[min]=b;
            m++;
        }
    }
    //запоминаем количество пересылок и сравнений
    kolc=c; kolm=m;
    return 0;
}

//метод пузырька
int puz(int size,int* arr)
{
    int i,k,b,c,m;
    //количество пересылок и сравнений
    c=0; m=0;
    //проходимся по всему массиву сайз-1 раз
    for (i=1; i<size; i++)
    {
        //с конца до текущего элемента
        for (k=size-1; k>=i; k--)
        {
            c++;
            if (arr[k-1]>arr[k]) 
            {
                b=arr[k-1]; arr[k-1]=arr[k]; arr[k]=b; m++;
            }
        }
    }
    //запоминаем количество пересылок и сравнений
    kolc=c; kolm=m;
    return 0;
}
//метод Щейкера
int sheiker(int size,int* arr)
{
    int i,k,b,m,c;
    m=0; c=0;
    int l=1;
    int r=size-1; k=size-1;
    do
    {
        for (i=r; i>=l; i--)
        {
            c++;
            if (arr[i-1]>arr[i])
            { 
                b=arr[i-1]; arr[i-1]=arr[i]; arr[i]=b; k=i; m++;
            }
        }
        l++;
        for (i=l; i<=r; i++)
        {
            c++;
            if (arr[i-1]>arr[i]) 
            {
                b=arr[i-1]; arr[i-1]=arr[i]; arr[i]=b; k=i; m++;
            }
        }
        r=k-1;
    }
    while (r>=l);
    kolm=m; kolc=c;
    return 0;
}
//считаем контрольную сумму
int consum(int size, int* arr)
{
    int sum=0;
    //считаем сумму всех чисел массива
    for (int i=0; i<size; i++) sum+=arr[i];
    //возращаем данное значение
    return sum;
}
//считаем количество серий
int kolser(int size,int* arr)
{
    int kol=1;
    for (int i=1; i<size; i++) 
        if (arr[i]!=arr[i-1]) kol++;
    return kol;
}

int main()
{
    int n;
    //делаем ввод данных
    printf("Enter n",&n);
    scanf("%i",&n);
    //все числа случайные
    for (int i=0; i<n; i++) ar[i]=rand()%1000000;
    //сортируем массив разними методами
    //при этом происходит проверка контрольных сумм
    memcpy(br,ar,sizeof(ar)); memcpy(cr,ar,sizeof(ar)); memcpy(dr,ar,sizeof(ar));
    //сортируем и выводим количество пересылок и сравнений
    prv(n,br); printf("m=%i c=%i\n",kolm,kolc);
    puz(n,cr); printf("m=%i c=%i\n",kolm,kolc);
    sheiker(n,dr); printf("m=%i c=%i\n",kolm,kolc);
    //делаем проверку по контрольным суммам
    if (consum(n,ar)==consum(n,br) && consum(n,ar)==consum(n,cr) && consum(n,ar)==consum(n,dr)) printf("Kontrolnie summi sovpadaut\n");
    else printf("Kontrolnie summi ne sovpadaut\n");
    //делаем подсчет количества серий в отсортированных массивах и сравниваем их
    if (kolser(n,br)==kolser(n,cr) && kolser(n,br)==kolser(n,dr)) printf("Kol-vo seriy sovpadaet\n");
    else printf("Kol-vo seriy ne sovpadaet\n");
    return 0;
}

aikidzin

Дата 5.9.2009, 11:37 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

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

Ну не знаю, почему у Вас не запускается. У меня на MVS2008 запустилась сразу. а за анализами алгоритмов вам батенька лучше обратиться к Дональду Кнуту. Он по полочкам разложил сортировки и их стоимость.

Best regards.

Это сообщение отредактировал(а) aikidzin - 5.9.2009, 11:38

ISergeyN

Дата 5.9.2009, 11:46 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

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

Цитата(aikidzin @ 5.9.2009, 11:37

)

Ну не знаю, почему у Вас не запускается. У меня на MVS2008 запустилась сразу

Разницу между С и С++ находите?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »