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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Очень трудно. http://www.cyberforum.ru/cpp-beginners/thread172250.html
Написать таблицу 3х6 (столбцы и строки соответственно). Что бы при запуске программы в ячейках таблицы появлялись 5 слов(одновременно в разных ячейках): Process 1, Process 2, Process 3, Process 4, Process 5.(в случайном порядке). И чтобы при запуске программы переходили с ячейки на ячейку.
C++ Ищу третье издание Язык программирования С++ в отличном от DJVU формате Даже стыдно как-то создавать тему... НО... . Ищу третье издание Язык программирования С++ в отличном от DJVU формате. Нужно, дабы читать на плеере. А то на компе третье издание, а на плеере читаю 2-е.. Не коммильфо. Если такого не имеется на русском - подойдет на английском. Если не имеется и на английском - посоветуйте как конвертнуть DJVU в txt... Естесно не напрямую, через PDF и т.д.... http://www.cyberforum.ru/cpp-beginners/thread172240.html
Для каждого слова первого предложения определить, входит ли оно во второе предложение C++
Здравствуйте. Я нуб в программировании, только начинаю осваивать. Помогите пожалуйста составить программу по следующим критериям: Даны два предложения. Для каждого слова первого предложения определить, входит ли оно во второе предложение. Пройдено нами совсем немного, прошу помочь написать код. Если можно с пояснениями.
C++ Известны углы α и β у основания. Выяснить, если это возможно, тип трапеции
Известны углы α и β у основания трапеции. Выяснить, если это возможно,тип трапеции (прямоугольная, равнобедренная, прямоугольник).
C++ найдите ошибку в лабораторке пример 2 http://www.cyberforum.ru/cpp-beginners/thread172182.html
#include <iostream> using namespace std; struct Worker { char fio;
C++ найдите ошибку в лабораторке #include "stdafx.h" #include <iostream> using namespace std; int sum(int а, int b); // оголошення функції int main(){ подробнее

Показать сообщение отдельно
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
01.11.2010, 23:43     Информация о карманной сортировке
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 "Карманная сортировка"
 
Текущее время: 21:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru