Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++ Builder
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
ocehyet
0 / 0 / 0
Регистрация: 20.05.2018
Сообщений: 2
1

Сортировка Хоара (быстрая сортировка) по убыванию

20.05.2018, 18:33. Просмотров 526. Ответов 5

Помогите найти/написать/понять/отобразить как пишется код для данного задания или хотя бы часть кода в C++ Builder

Найти в заданной последовательности чисел наибольшее по мощности подмножество чисел сумма которых даёт число из множества {Ai=A(i-1)+3A(i-2), A0=1, A1=2, i=0,1,....}
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.05.2018, 18:33
Ответы с готовыми решениями:

Сортировка методом Шелла и быстрая сортировка
Помогите найти код для функций в виде кусков кода сортировок...

Быстрая сортировка
Добрый день. Задание такое : 1) Для “быстрой сортировки” получить зависимость затрат машинного...

Быстрая сортировка.!!!!
помогите написать программу быстрой сортировки массива из 12 чисел.!

Быстрая сортировка
Написал алгоритм точнее собрал его из выложенных кодов на просторах сети.... Но не пойму в чем...

Быстрая сортировка массива
Анализ процедуры "быстрой" сортировки. Получить временные данные по сортировке разновеликих...

5
lifeforce
252 / 200 / 86
Регистрация: 27.09.2010
Сообщений: 1,187
20.05.2018, 23:42 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
#include <stdio.h>
#include <stdlib.h>
// Функция быстрой сортировки
void quickSort(int *numbers, int left, int right)
{
  int pivot; // разрешающий элемент
  int l_hold = left; //левая граница
  int r_hold = right; // правая граница
  pivot = numbers[left];
  while (left < right) // пока границы не сомкнутся
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--; // сдвигаем правую границу пока элемент [right] больше [pivot]
    if (left != right) // если границы не сомкнулись
    {
      numbers[left] = numbers[right]; // перемещаем элемент [right] на место разрешающего
      left++; // сдвигаем левую границу вправо
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++; // сдвигаем левую границу пока элемент [left] меньше [pivot]
    if (left != right) // если границы не сомкнулись
    {
      numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
      right--; // сдвигаем правую границу вправо
    }
  }
  numbers[left] = pivot; // ставим разрешающий элемент на место
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива
    quickSort(numbers, left, pivot - 1);
  if (right > pivot)
    quickSort(numbers, pivot + 1, right);
}
int main()
{
  int a[10];
  // Заполнение массива случайными числами
  for (int i = 0; i<10; i++)
    a[i] = rand() % 20 - 10;
  // Вывод элементов массива до сортировки
  for (int i = 0; i<10; i++)
    printf("%d ", a[i]);
  printf("\n");
  quickSort(a, 0, 9); // вызов функции сортировки
            // Вывод элементов массива после сортировки
  for (int i = 0; i<10; i++)
    printf("%d ", a[i]);
  printf("\n");
  getchar();
  return 0;
}



Быстрая сортировка на основе библиотеки STL.

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
#include <functional>
#include <algorithm>
#include <iterator>
 
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
  if( first != last ) {
    BidirectionalIterator left  = first;
    BidirectionalIterator right = last;
    BidirectionalIterator pivot = left++;
 
    while( left != right ) {
      if( cmp( *left, *pivot ) ) {
         ++left;
      } else {
         while( (left != --right) && cmp( *pivot, *right ) )
           ;
         std::iter_swap( left, right );
      }
    }
 
    --left;
    std::iter_swap( first, left );
 
    quick_sort( first, left, cmp );
    quick_sort( right, last, cmp );
  }
}
// для вещественных
 
int partition (double *a, int p, int r)
 
 {
   double x = *(a+r);
   int i = p - 1;
   int j;
   double tmp;
   for (j = p; j < r; j++)
   {
     if (*(a+j) <= x)
     {
       i++;
       tmp = *(a+i);
       *(a+i) = *(a+j);
       *(a+j) = tmp;
     }
   }
   tmp = *(a+r);
   *(a+r) = *(a+i+1);
   *(a+i+1) = tmp;
   return i + 1;
 }
 
void quicksort (double *a, int p, int r)
 
 {
   int q;
   if (p < r)
   {
     q = partition (a, p, r);
     quicksort (a, p, q-1);
     quicksort (a, q+1, r);
   }
 }
template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
  quick_sort( first, last,
    std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
  );
можно и продолжить примеры.
1
gunslinger
случайный прохожий
1475 / 959 / 368
Регистрация: 20.07.2013
Сообщений: 2,798
21.05.2018, 00:19 3
Насколько я понимаю, наибольшее по мощности подмножество чисел - максимальное количество чисел (в данном случае).
Сортировку тебе дали, только не совсем пойму, для чего она тебе здесь нужна.

Добавлено через 22 минуты
Функция для расчета https://www.cyberforum.ru/cgi-bin/latex.cgi?A{i}_{}:
C++
1
2
3
4
5
6
7
8
9
unsigned __int64 func(unsigned __int64 n)
{
  if (n == 0)
    return 1;
  else if (n == 1)
    return 2;
  else
    return func(n - 1) + 3 * func(n - 2);
}
1
ocehyet
0 / 0 / 0
Регистрация: 20.05.2018
Сообщений: 2
21.05.2018, 01:55  [ТС] 4
давным давно перестала понимать что от меня хотят на программировании... Спасибо!
0
nick42
21.05.2018, 08:54
  #5

Не по теме:

а чего тут понимать... . Пристают мужики!

0
gunslinger
случайный прохожий
1475 / 959 / 368
Регистрация: 20.07.2013
Сообщений: 2,798
21.05.2018, 22:01 6
Насчет сортировки. Думаю, она нужна для более удобного определения подмножества чисел.
0
21.05.2018, 22:01
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.05.2018, 22:01

Сортировка по убыванию в ListBox
Подскажите пожалуйста как сделать сортировку списка по убыванию в ListBox в C++

Сортировка массива по убыванию
Здравствуйте. Есть код, благодаря которому сортируется массив по убыванию. А мне нужен по...

Сортировка. Упорядочить последовательность по убыванию.
Задана последовательность чисел имеющая равные между собой элементы. Упорядочить последовательность...


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

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

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