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

Информация о карманной сортировке - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
forlan
 Аватар для forlan
1 / 1 / 0
Регистрация: 26.07.2010
Сообщений: 23
04.10.2010, 18:07     Информация о карманной сортировке #1
вот никак не могу найти о "карманной сортировке с неповторяющимися ключами с использованием допол.масивов и без них" немогли бы вы найти что нить по этой теме)))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.10.2010, 18:07     Информация о карманной сортировке
Посмотрите здесь:

Счетчик в сортировке C++
C++ Ошибка в порязрядной сортировке?!
C++ вывод массива в сортировке
C++ Ошибка в сортировке
C++ Помощь в сортировке
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
04.10.2010, 19:25     Информация о карманной сортировке #2
а гугл на что?

http://ru.wikipedia.org/wiki/Блочная_сортировка
forlan
 Аватар для forlan
1 / 1 / 0
Регистрация: 26.07.2010
Сообщений: 23
28.10.2010, 20:53  [ТС]     Информация о карманной сортировке #3
мало в гугле

Добавлено через 7 минут
помогите сделать прогу с оптимальным поиском
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
29.10.2010, 01:26     Информация о карманной сортировке #4
решил для себя написать блочную сортировку (ну пока что это наброски, работает с числами до 100),:


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
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
 
using namespace std;
 
// получить номер корзины
inline int getblock(int number){ 
    const int DENOMINATOR = 10;
    return number / DENOMINATOR;
}
 
/*
[url]http://ru.wikipedia.org/wiki/Блочная_сортировка[/url]
*/
 
 
int main()
{
    int mas[] = {29, 25, 3, 49, 9, 37, 21, 43}; //сортируемый массив
    int sizemas = sizeof(mas)/sizeof(int);
 
    const int row = 10;
    const int col = 10;
    vector<vector<int> > arr(row,vector<int>(col)); //корзины(карманы)
 
 
    //распределение по корзинам
    for (int i = 0; i < sizemas; ++i){
        int blocknumb = getblock(mas[i]);
        for (int j = 0; j < row; ++j){
            if (!arr[j][blocknumb]){
                 arr[j][blocknumb] = mas[i];
                 break;
            }
        }
    }
 
 
    //вывод корзин на экран
    for (int i = 0; i < row; ++i){
        for (int j = 0; j < col; ++j)
            cout <<  setw(4) << arr[i][j] ;
        cout<<endl;
    }
 
 
    //сортируем каждую корзину
 
    //вывод отсортированного массива
 
 
    return 0;
}

номер корзины, в которую надо поместить элемент массива, определяю как
формула1: [элемент_массива/10]

и возникла парочка вопросов:
1) Как получить количество корзин? Нужно сначала найти максимальный элемент в сортируемом, массиве а потом применить формулу1?
2) если в массиве, который надо отсортировать, всего 2 элемента, например mas = {7, 6954}
то, получается мне нужно на 2 элемента создать (6954/10) 695 корзин?

может я впринципе не правльно делаю эту сортировку?
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
01.11.2010, 23:43     Информация о карманной сортировке #5
forlan, вот что нашел по карманной

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
135
136
// To compile: mpicc -lm -o bucket bucket.c
 
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
#include "mpi.h"
 
/*****************************************************************************/
// Routines used in the sequential implementation of the bucket sort
float* create_buckets(int nbuckets, int nitems);
void bucket_sort(float *data, int ndata, float x1, float x2, int nbuckets,
         float* bucket);
 
int check(float *data,int nitems) {
  double sum=0;
  int sorted=1;
  int i;
 
  for(i=0;i<nitems;i++) {
     sum+=data[i];
     if(i && data[i]<data[i-1]) sorted=0;
  }
  printf("sum=%f, sorted=%d\n",sum,sorted);
}
 
int compare(const void* x1, const void* x2);
/*****************************************************************************/
 
int main(int argc,char *argv[]) {
  // Specify here the full range that the data numbers can cover. We
  // may assume that all the numbers are positive definite
  const float xmin = 10.0;
  const float xmax = 250000;
  int nbuckets=1000;
  int nitems=100000;
  int i;
 
  if(argc==2) nitems=atoi(argv[1]);
 
  float *data=malloc(nitems*sizeof(float));
 
  for(i=0;i<nitems;i++)
    data[i]=drand48()*(xmax-xmin-1)+xmin;
 
  check(data,nitems);
 
  float *buckets=create_buckets(nbuckets,nitems);
  bucket_sort(data,nitems,xmin,xmax,nbuckets,buckets);
 
  check(data,nitems);
 
}
/*****************************************************************************/
 
// Sequential implementation of the bucket sort routine. The full
// range x1 to x2 will be divided into a number of equally spaced
// subranges according to the number of buckets. All the buckets are
// contained in the single one dimensional array "bucket".
void bucket_sort(float *data, int ndata, float x1, float x2, int nbuckets,
         float *bucket) 
{
  int i, count;
 
  // The range covered by one bucket
  float stepsize = (x2 - x1) / nbuckets;
 
  // The number of items thrown into each bucket. We would expect each
  // bucket to have a similar number of items, but they won't be
  // exactly the same. So we keep track of their numbers here.
  int* nitems = malloc(nbuckets * sizeof(int));
  for (i = 0; i < nbuckets; ++i) nitems[i] = 0;
 
  // Toss the data items into the correct bucket
  for (i = 0; i < ndata; ++i) {
 
    // What bucket does this data value belong to?
    int bktno = (int)floor((data[i] - x1) / stepsize);
    int idx = bktno * ndata + nitems[bktno];
 
    //printf("DATA %d %f %d %d\n", i, data[i], bktno, idx);
 
    // Put the data value into this bucket
    bucket[idx] = data[i];
    ++nitems[bktno];
  }
  
  // Sort each bucket using the standard library qsort routine. Note
  // that we need to input the correct number of items in each bucket
  count = 0;
  for (i = 0; i < nbuckets; ++i) {
    if(nitems[i]) {
      qsort(&bucket[i*ndata], nitems[i], sizeof(float), compare);
      memcpy(data,&bucket[i*ndata],nitems[i]*sizeof(float));
      data+=nitems[i];
    }
  }
 
  // Don't need the number of items anymore
  free(nitems);
  
}
 
/*****************************************************************************/
 
// Create a data array to hold the given number of buckets for the
// given number of total data items. All buckets are held contiguously
// in the
float* create_buckets(int nbuckets, int nitems)
{
  int i;
 
  int ntotal = nbuckets * nitems;
 
  // Pointer to an array of more pointers to each bucket
  float* bucket = calloc(ntotal, sizeof(float*));
  for (i=0; i<ntotal; ++i) bucket[i] = 0;
 
  // return the address of the array of pointers to float arrays
  return bucket;
}
 
/*****************************************************************************/
 
// The comparison function to use with the library qsort
// function. This will tell qsort to sort the numbers in ascending
// order.
int compare(const void* x1, const void* x2) {
  const float* f1 = x1;
  const float* f2 = x2;
  float diff = *f1 - *f2;
 
  return (diff < 0) ? -1 : 1;
}
Добавлено через 26 минут
++++++++++++++++++++++++++++++++++++++
СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ

АЛЬФРЕД АХО
Bell Laboratories
Муррей-Хилл, Нью-Джерси

Глава 8, стр 247 "Карманная сортировка"
rita-zaya123
0 / 0 / 0
Регистрация: 15.02.2012
Сообщений: 29
22.04.2012, 16:55     Информация о карманной сортировке #6
а по поводу блочной сортировки. мне она нужна. я не могу понять,почему у меня ошибка ещё на первой строчке,то есть даже библиотеки не подключает?
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
22.04.2012, 17:00     Информация о карманной сортировке #7
Цитата Сообщение от rita-zaya123 Посмотреть сообщение
а по поводу блочной сортировки. мне она нужна. я не могу понять,почему у меня ошибка ещё на первой строчке,то есть даже библиотеки не подключает?
телепаты в отпуске. какой код не работает?
rita-zaya123
0 / 0 / 0
Регистрация: 15.02.2012
Сообщений: 29
22.04.2012, 17:19     Информация о карманной сортировке #8
вот есть блочная сортировка но ошибки начинаются ещё с подключения библиотек

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <iostream>
#include <iomanip>
using namespace std;
 
#define NARRAY 8  /* array size */
#define NBUCKET 5 /* bucket size */
#define INTERVAL 10 /* bucket range */
 
struct Node 
{ 
    int data;  
    struct Node *next; 
};
 
void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);
 
void BucketSort(int arr[])
{   
    int i,j;
    struct Node **buckets;  
 
    /* allocate memory for array of pointers to the buckets */
    buckets = (struct Node **)malloc(sizeof(struct Node*) * NBUCKET); 
 
    /* initialize pointers to the buckets */
    for(i = 0; i < NBUCKET;++i) {  
        buckets[i] = NULL;
    }
 
    /* put items into the buckets */
    for(i = 0; i < NARRAY; ++i) {   
        struct Node *current;
        int pos = getBucketIndex(arr[i]);
        current = (struct Node *) malloc(sizeof(struct Node));
        current->data = arr[i]; 
        current->next = buckets[pos];  
        buckets[pos] = current;
    }
 
    /* check what's in each bucket */
    for(i = 0; i < NBUCKET; i++) {
        cout << "Bucket[" << i << "] : ";
        printBuckets(buckets[i]);
        cout << endl;
    }
 
    /* sorting bucket using Insertion Sort */
    for(i = 0; i < NBUCKET; ++i) {  
        buckets[i] = InsertionSort(buckets[i]); 
    }
 
    /* check what's in each bucket */
    cout << "-------------" << endl;
    cout << "Bucktets after sorted" << endl;
    for(i = 0; i < NBUCKET; i++) {
        cout << "Bucket[" << i << "] : ";
        printBuckets(buckets[i]);
        cout << endl;
    }
 
    /* put items back to original array */
    for(j =0, i = 0; i < NBUCKET; ++i) {    
        struct Node *node;
        node = buckets[i];
        while(node) {
            arr[j++] = node->data;
            node = node->next;
        }
    }
    
    /* free memory */
    for(i = 0; i < NBUCKET;++i) {   
        struct Node *node;
        node = buckets[i];
        while(node) {
            struct Node *tmp;
            tmp = node; 
            node = node->next; 
            free(tmp);
        }
    }
    free(buckets); 
    return;
}
 
/* Insertion Sort */
struct Node *InsertionSort(struct Node *list)
{   
    struct Node *k,*nodeList;
    /* need at least two items to sort */
    if(list == 0 || list->next == 0) { 
        return list; 
    }
    
    nodeList = list; 
    k = list->next; 
    nodeList->next = 0; /* 1st node is new list */
    while(k != 0) { 
        struct Node *ptr;
        /* check if insert before first */
        if(nodeList->data > k->data)  { 
            struct Node *tmp;
            tmp = k;  
            k = k->next; 
            tmp->next = nodeList;
            nodeList = tmp; 
            continue;
        }
 
        for(ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
            if(ptr->next->data > k->data) break;
        }
 
        if(ptr->next!=0){  
            struct Node *tmp;
            tmp = k;  
            k = k->next; 
            tmp->next = ptr->next;
            ptr->next = tmp; 
            continue;
        }
        else{
            ptr->next = k;  
            k = k->next;  
            ptr->next->next = 0; 
            continue;
        }
    }
    return nodeList;
}
 
int getBucketIndex(int value)
{
    return value/INTERVAL;
}
 
void print(int ar[])
{   
    int i;
    for(i = 0; i < NARRAY; ++i) { 
        cout << setw(3) << ar[i]; 
    }
    cout << endl;
}
 
void printBuckets(struct Node *list)
{
    struct Node *cur = list;
    while(cur) {
        cout << setw(3) << cur->data;
        cur = cur->next;
    }
}
 
int main(void)
{   
    int array[NARRAY] = {29,25,3,49,9,37,21,43};
 
    cout << "Initial array" << endl;
    print(array);
    cout << "-------------" << endl;
 
    BucketSort(array); 
    cout << "-------------" << endl;
    cout << "Sorted array"  << endl;
    print(array); 
    return 0;
}
вот такой должен быть ответ. ссылка на прогу и на ответ
http://www.bogotobogo.com/Algorithms/bucketsort.php

Добавлено через 10 минут
так же и код с этой темы тоже с ошибками и тот и другой. не пойму в чем дело.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
22.04.2012, 18:22     Информация о карманной сортировке #9
Цитата Сообщение от rita-zaya123 Посмотреть сообщение
но ошибки начинаются ещё с подключения библиотек
то есть у тебя даже не запускается?
Не знаю, у меня скомпилировалось и построилось без ошибок
rita-zaya123
0 / 0 / 0
Регистрация: 15.02.2012
Сообщений: 29
22.04.2012, 18:28     Информация о карманной сортировке #10
в с ++ ????
может у меня С не такой. а Вы какую именно программу пробовали???
и если можете ,скажите какой именно у Вас С ???? версия?? или ссылку дайте на него в интернете,пожалуйста.
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
22.04.2012, 18:56     Информация о карманной сортировке #11
может у меня С не такой
Так С или С++? Языки разные как бы) Если С, то естественно, что компилятор будет ругаться на включаемые заголовочные файлы C++.
C++
1
2
#include <iostream>
#include <iomanip>
- это С++;
C++
1
using namespace std;
- и это;
C++
1
cout << endl;
- и это.
Если вам нужны функции вывода С, то это printf, fprintf и пр., они объявлены в stdio.h
rita-zaya123
0 / 0 / 0
Регистрация: 15.02.2012
Сообщений: 29
22.04.2012, 21:36     Информация о карманной сортировке #12
да,у меня ошибки выдает именно в этих местах
то есть верхнее 2 сточки заменить на #include<stdio.h>???
а на что поменять вот это

using namespace std;
????
и что написать вместо
cout << endl;
?????

Добавлено через 8 минут
пожалуйста,пришлите ссылку на тот С++ ,благодаря которому у Вас эта программа работает.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
22.04.2012, 21:45     Информация о карманной сортировке #13
Я считаю, вредно изучать всякие экзотические сортировки, если до этого ни разу не писал програм на Си.
rita-zaya123
0 / 0 / 0
Регистрация: 15.02.2012
Сообщений: 29
22.04.2012, 23:45     Информация о карманной сортировке #14
я писала на турбо С пять программ,но они никак не были связаны с этими сортировками.
А данная сортировка-это одна из задач моей ргр, я тоже считаю странным ,что мне задали три сортировки ,ещё и такие , а кому-то одну программу по рекурсии,но выбора нет и мне нужно длеть . Ещё и реализовать нужно на 2-х языках программирования с расчётом времени работы. Грубо говоря нужно шесть программ...
Вы говорите вредно,но что же делать? жизнь такая. Я учусь:что задают,то и делаю.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2012, 00:58     Информация о карманной сортировке
Еще ссылки по теме:

Ошибка в сортировке C++
C++ Написать программу- вводная информация в файле in.txt, выходная информация в out.txt
Структыру.Ошибка в сортировке C++

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

Или воспользуйтесь поиском по форуму:
rita-zaya123
0 / 0 / 0
Регистрация: 15.02.2012
Сообщений: 29
24.04.2012, 00:58     Информация о карманной сортировке #15
скажите,какой у Вас С ????
ссылку скиньте пожалуйста
Yandex
Объявления
24.04.2012, 00:58     Информация о карманной сортировке
Ответ Создать тему
Опции темы

Текущее время: 08:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru