Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
mastar
0 / 0 / 0
Регистрация: 04.04.2010
Сообщений: 63
1

Реализовать алгоритмы сортировки для данных с последовательным доступом

13.02.2011, 07:17. Просмотров 1228. Ответов 2
Метки нет (Все метки)

Подмогните Уважаемые программисты! Есть прога сортировки для массивов (для данных с произвольным доступом)..
Необходимо реализовать алгоритмы сортировки для данных с последовательным доступом (для списков)

Как это сделать, помогите!

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
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <memory.h>
#pragma hdrstop
 
//максимальная длина массива
const int maxn=500;
//максимальная величина чисел в массиве
const int maxelement=99;
 
int ar[maxn+1],br[maxn+1],cr[maxn+1];
int temp[maxn+1];
int kolc,kolm;
int t;
 
//---------------------------------------------------------------------------
 
//метод цифровой сортировки
int digits(int size,int* arr)
{
 
    int i, j, k, r, w, uk2, ch;
    int MM[10][maxn];//массив для хранения чисел по одному числу
    int uk[10];//массив указателей на строки массива ММ
    w=maxelement; r=1;
    while (1)//цикл для нахождения МАХ разряда чисел исх. массива
        {w=(w-w%10)/10;
        if (w==0) break;
        r++;}
    for (k=1;k<=r;k++)//цикл для прогонки чисел по разрядам
        {memset(MM,0,sizeof(MM));//обнуляем промежуточный массив
        for (i=0;i<=9;i++) {uk[i]=1;}//ставим указатели на 1-е ячейки
        for (i=1;i<=size;i++)//в цикле проверяем все числа исх. массива и сортируем по цифре i разряда
            {ch=arr[i];
            for (j=1;j<k;j++) {ch=(ch-ch%10)/10;}
            w=ch%10; kolc++;// !!! считаем кол-во сравнений
            MM[w][uk[w]]=arr[i]; kolm++;// !!! считаем кол-во пересылок
            uk[w]++;}
        uk2=1;//указатель для записи в исходный массив
        for (i=0;i<=9;i++)//переписываем числа из промежуточного в исходный массив
            {for (j=1;j<uk[i];j++)
                {arr[uk2]=MM[i][j]; kolm++;// !!! считаем кол-во пересылок
                uk2++;}}}
 
    return 0;
}
//само слияние двух частей массива
int merge(int* arr,int l, int cer,int r)
{
 
    int i=l;
    int k=cer+1;
    int j=0;
    //обнуляем временный массив
    memset(temp,0,sizeof(temp));
    //сливаем из двух частей в темп наименьший
    while (i<=cer && k<=r)
    {
        kolm++;// !!! считаем кол-во пересылок
        kolc++;// !!! считаем кол-во сравнений
        if (arr[i]<arr[k]){temp[j]=arr[i]; j++; i++;}
        else {temp[j]=arr[k]; j++; k++;}
    }
    //дописываем из правой части
    while (k<=r) 
    {
        kolm++;// !!! считаем кол-во пересылок
        temp[j]=arr[k]; j++; k++;
    }
    //дописываем из левой части
    while (i<=cer)
    {                                 
        kolm++;// !!! считаем кол-во пересылок
        temp[j]=arr[i]; j++; i++;
    }
    //переписываем в массив
    for (j=0; j<r-l+1; j++) {arr[l+j]=temp[j]; kolm++;}// !!! считаем кол-во пересылок
    return 0;
}
//рекурсивная сортировка слиянием
int sort(int* arr,int l,int r)
{
    //l-левая граница , r-правая, она должна быть больше
    if (l>=r) return 0;
    int cer=(l+r)>>1;//середина отрезка
    //сортируем левую и правую чатси
    sort(arr,l,cer);
    sort(arr,cer+1,r);
    //сливаем их
    merge(arr,l,cer,r);
    return 0;
}
 
 
//метод слияния
int sli(int size,int* arr)
{
    int i,k,b,c,m;
    kolc=0; kolm=0;
    sort(arr,1,size);
    return 0;
}
 
 
#pragma argsused
int main(int argc, char* argv[])
{
 
    randomize();
 
    int n;
    //делаем ввод данных
    printf("Enter n= ",&n);
    scanf("%i",&n);
    //все числа случайные
    for (int i=1; i<=n; i++)
        {ar[i]=random(maxelement+1);
        //cout<<i<<"-el="<<ar[i]<<"   ";
        }
    cout<<"\n\n";
    //сортируем массив разними методами
    memcpy(br,ar,sizeof(ar)); memcpy(cr,ar,sizeof(ar)); 
    //сортируем и выводим количество пересылок и сравнений
    digits(n,br); printf("Digits Sort:  m=%i c=%i\n",kolm,kolc);
    //for (int i=1; i<=n; i++) {cout<<i<<"-el="<<br[i]<<"   ";}
    cout<<"\n\n";
    sli(n,cr); printf("Sli Sort:  m=%i c=%i\n",kolm,kolc);
    //for (int i=1; i<=n; i++) {cout<<i<<"-el="<<cr[i]<<"   ";}
 
    getchar(); getchar();
 
    return 0;
}
Добавлено через 17 часов 41 минуту
Неужели не поможете? Или слишком сложно?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.02.2011, 07:17
Ответы с готовыми решениями:

Алгоритмы сортировки массивов.Реализуйте алгоритмы сортировок данных массивов
Задания к лабораторной работе. Выполните приведенные ниже задания. 1. Даны два целочисленных...

Файлы с последовательным и прямым доступом
помогите пожалуйся, не понимаю я эти файлы с последовательным и прямым доступом Задание:...

Работа с нетипизированными файлами. Поиск с последовательным доступом
ЗАДАНИЕ: ПРИ РАБОТЕ С НЕТИПИЗОРОВАННЫМИ ФАЙЛА ОСУЩЕСТВИТЬ ВВОД ИНФОРМАЦИИ С КЛАВИАТУРЫ В ФАЙЛ И...

Реализовать алгоритмы сортировки методами пузырьки и включения (в прямом и обратном направлениях)
1. Реализовать алгоритмы сортировки методами пузырьки и включения (в прямом и обратном...

Реализовать все алгоритмы сортировки, оформив решение в виде функций ввода, вывода и обработки массивов
Здравствуйте народ,помогите в решении данной задачки с помощью подпрограммы: Дан массив из N...

2
mastar
0 / 0 / 0
Регистрация: 04.04.2010
Сообщений: 63
17.02.2011, 04:33  [ТС] 2
Сложная тема, однако!
0
mastar
0 / 0 / 0
Регистрация: 04.04.2010
Сообщений: 63
22.02.2011, 17:57  [ТС] 3
Неужели никто не поможет?
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.02.2011, 17:57

Реализовать гибкую проверку данных в книге с общим доступом
Доброго времени суток! Друзья, как известно в книге Excel 2007 c общим доступом есть ряд...

Алгоритмы сортировки больших объёмов данных
Здравствуйте, столкнулся со следующей проблемой: Имею бинарный файл, в котором хранится матрица из...

Рекурсивные функции и Алгоритмы сортировки данных в массиве
Уважаемые форумчане, помогите с поиском информации по этим двум вопросам Maple: 1. Рекурсивные...


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

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

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