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

Всем здрасте.Можете рассказать(кратко и главн.),как выполн.двоичная быстрая сортировка?!я не профф...просто мне нужно ответ одну. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Если в нем есть цифра a и b, то определить, какая из них расположена в числе правее http://www.cyberforum.ru/cpp-beginners/thread261499.html
??? ((( Дано натуральное число. Если в нем есть цифра a и b, то определить, какая из них расположена в числе правее. Если одна или обе эти цифры встречаются в числе несколько раз, то должны быть...
C++ Квадрат из звездочек Как сделать правую сторону квадрата.Число вводится пользователем и какое число он введет из такого количества звездочек строится квадрат.Можно использовать while ,if else и символы табуляции. Вот... http://www.cyberforum.ru/cpp-beginners/thread261498.html
Массивы структур C++
Помогите с программкой, вообще не понимаю я это((( Дан массив записей, содержащий номера телефонов сотрудников учреждения: фамилия и инициалы сотрудника и номер телефона. Найти и вывести на экран...
Строки С++ C++
1) В строке имеются только две одинаковых буквы. Найти их. 2) Преобразование символов в числа. Дан текст, имеющий вид: d1 +- d2 +- ... +- dn, где di - цифры. Вычислить значение данного выражение. ...
C++ Поменять местами первую из букв а и последнюю из букв о http://www.cyberforum.ru/cpp-beginners/thread261487.html
Решите задачку, пожалуйста. Дано слово. Поменять местами первую из букв а и последнюю из букв о. Учесть возможность того, что таких букв в слове может не быть.
C++ Открытие лотка DVD-привода Очень Хочу написать программу которая бы открывала привод. Все в интернете перечитал использую dev c++. Ничего не помагает. Может кто-то встречался с этим? подробнее

Показать сообщение отдельно
aleksandr_00
0 / 0 / 0
Регистрация: 02.10.2010
Сообщений: 48

Всем здрасте.Можете рассказать(кратко и главн.),как выполн.двоичная быстрая сортировка?!я не профф...просто мне нужно ответ одну. - C++

21.03.2011, 22:02. Просмотров 359. Ответов 0
Метки (Все метки)

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
[SIZE="1"]#include<conio.h>
#include<iostream.h>
#include<fstream.h>
#include <time.h>
//алфавит букв
enum Alhabit{a=1,b,c,d,e,
             f,g,h,i,j,k,
             l,m,n,o,p,q,
             r,s,t,u,v,w,
             x,y,z};
 
char * mas = new char[1048576];     //массив
int mas_count=0;                //количество элементов в массиве
 
//прототипы функций
char * in_binary(int i, int ch, char * massiv);
char get_bit(int elem, int number_byte);
void load_mas();
void exch(int i, int j);
void quicksortbinary(int l, int r, int d);
 
 
 
int main()
{
  load_mas();
 
  //выводим исходный массив
  for(int i = 0 ; i < mas_count ; i ++)
    cout << mas[i];
 
  cout<<endl;
 
/*
  // вывод массива в двоичном виде
  for(int a = 0 ; a < mas_count; a ++)
  {
    cout<<mas[a] <<" - ";
    for(int i = 0 ; i < 5 ; i ++)
      cout << get_bit(mas[a],i);
      cout<<endl;
  }
*/
  clock_t start, end;
 
  start = clock();
 
  //сортировка
  quicksortbinary(0,mas_count-1, 0);
 
  end = clock();
  cout << "time = " << (end - start) / CLK_TCK  << endl;
 
/*
  //вывод отсортированного массива
  for(int a = 0 ; a < mas_count; a ++)
  {
    if ( a != 0 && a - 1 != mas_count) cout<<" - ";
    cout<<mas[a];
  }
*/
 getch();
 return 0;
}
 
 
//------------------------------------------------------
// перевод в бинарный вид
char * in_binary(int i, int ch, char * massiv)
{
  if (i < 0 )return massiv;
  if (ch % 2 == 1 ) massiv[i] = '1';
  else massiv[i] = '0';
 
  in_binary(--i, ch /2, massiv);
  return massiv;
}
 
 
// в указанном номере элемента массива (elem)
// возвращает указанный номер бита (number_byte)
char get_bit(int elem, int number_byte)
{
  char * tmp = new char[4];
 
  in_binary(4, elem, tmp);
 
  return tmp[number_byte];
 
};
 
 
 
//------------------------------------------------------
// загрузить массив в mas
void load_mas()
{
   char in_char;
  ifstream inf ("infile.txt");
  inf.seekg(0);
 
  while(inf.get(in_char))
  {
    if(!char_traits<char>::eq(in_char,' '))
    {
      mas[mas_count] = in_char;
      mas_count++;
    }
  }
};
 
 
//------------------------------------------------------
// замена в mas i-го и j-го элементов
void exch(int i, int j)
{
  char tmp;
  tmp = mas[i];
  mas[i] = mas[j];
  mas[j] = tmp;
};
 
//------------------------------------------------------
// сортировка
void quicksortbinary(int l, int r, int d)
{
  int i = l, j = r;
  if (r<= l || d > 5) return;
  while(j != i)
  {
    while((get_bit(mas[i], d) == '0') && (i < j)) i++;
    while((get_bit(mas[j], d) == '1') && (j > i)) j--;
    if(mas[i] == mas[j]  && i != j) i++;
    exch(i,j);
  }
  if(get_bit(mas[i], d) == '0') j++;
 
  quicksortbinary(l, j-1, d+1);
  quicksortbinary(j, r, d+1);
 
  //cout << ".";
};
[/SIZE]
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru