С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 56, средняя оценка - 4.77
paradox92
0 / 0 / 0
Регистрация: 27.02.2010
Сообщений: 38
#1

Блочная сортировка массива - C++

02.03.2010, 20:35. Просмотров 8124. Ответов 11
Метки нет (Все метки)

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

Задание: Написать программу, которая реализует:
1. алгоритм блочной сортировки массива
2. поиск заданного элемента массива
Подробности: ввод массива случайным образом (rand), количество элементов массива вводится с клавиатуры.

Добавлено через 2 часа 24 минуты
Есть желающие помочь?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.03.2010, 20:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Блочная сортировка массива (C++):

Блочная сортировка массива - C++
В данный момент пытаюсь решить задачу, требуется помощь с пунктом "А)" (остальные попробую сам). Условие: Блочная сортировка требует...

Блочная сортировка массива. Не выходит - C++
Суть такова-есть массив, который генерируется рандомно, и размер которого варьеруется size. Вообще не понимаю, как написать для него...

Блочная сортировка массива (найти ошибку) - C++
Вобщем задача следующая: реализовать алгоритм блочной сортировки массива! Собственно реализовать - реализовал! =) когда количество...

Блочная сортировка массива и поиск заданного элемента - C++
Помогите пожалуйста написать такую программу. Задание: Написать программу, которая реализует: 1. алгоритм блочной сортировки...

Блочная сортировка с++ - C++
Приветствую,можете мне помочь решить данное задание? В массиве содержится не менее 100 записей (поля записи определить функцией random),...

блочная сортировка, не работает - C++
Добрый день, не работает сортировка блочная, выдает ошибку (скрин во вложении) Код ниже #include <iostream> #include...

11
Евгений М.
1036 / 977 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
03.03.2010, 13:32 #2
1. Самый простой и медленный алгоритм - метод пузырка. Для быстрый алгоритм имеет соответсвующее название - быстрая сортировка. Если не знаете, что за "пузырь" - погуглите.
2. В цикле проверяем текущий массив с заданым.
0
paradox92
0 / 0 / 0
Регистрация: 27.02.2010
Сообщений: 38
03.03.2010, 20:04  [ТС] #3
тут нужна сортировка именно блочным методом
0
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
03.03.2010, 20:10 #4
paradox92, вот тебе в помощь функция заполнения массива случайными числами:
C++
1
2
3
4
5
6
// Функция заполнения массива arr размера size случайными числами
void FillRandom(int* arr, int size)
{
  for(int i = 0; i < size; ++i)
    arr[i] = rand();
}
И функция поиска заданного элемента в массиве:
C++
1
2
3
4
5
6
7
8
9
10
11
12
// Поиск заданного элемента key в массиве arr размера size
//
// Возвращает индекс первого вхождения элемента key, или -1
// в случае его отсутствия
int Find(const int* arr, int size, int key)
{
  for(int i = 0; i < size; ++i)
    if(arr[i] == key)
      return i;
  
  return -1;
}
0
Евгений М.
1036 / 977 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
03.03.2010, 20:18 #5
Цитата Сообщение от paradox92 Посмотреть сообщение
тут нужна сортировка именно блочным методом
Поисковик в помощь
0
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
24.10.2011, 19:56 #6
Евгений М., здравствуйте, на картинках все понятно как оно все работает, но вот как реализовать, искал в НЕТЕ, так и не понял как реализовать!
0
Thinker
24.10.2011, 20:09
  #7

Не по теме:

gorin, как вижу вы любитель сортировок

0
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
24.10.2011, 20:29 #8
вроде нашол, выйдет выложу обязательно, не меня же одного это интересует, я не люблю программирование очень, учеба заставляет, но работа с массивами очень интересная штука.

Добавлено через 18 минут
Вот что то нашол, не работает, вроде все правильно
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
void bucketSort(int arrey[N])
{
 
    int buckets[hor][ver];
    int ostatok;
    for(int x = 1; x <= 100; x *= 10)
    {
        count = 0;
        for(int i = 0; i < N; i++)
        {
            temp = arrey[i] / x;
            ostatok = temp % 10;
            buckets[ostatok][i] = arrey[i];
        }
        for(int i = 0; i < hor; i++)
        {
            for(int j = 0; j < ver; j++)
            {
                if(buckets[i][j] != -1)
                {
                    arrey[count] = buckets[i][j];
                    count++;
                }
            }
            sm += IntToStr(arrey[i]) + "  ";
        }
    }
}
чтобы вызвать
C++
1
bucketSort(mas);
, все компилируется но при нажатии "сортировать" ошибка!
0
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
25.10.2011, 21:43 #9
Подскажите где ошибка, я просмотрел все нормально, а при выполнении не работает!
0
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
27.10.2011, 15:03 #10
Решение найдено

Глобальные переменные:
C++
1
2
3
4
#define N 20
int mas[N];
int k, x, count, l, v, i, j, temp, p, c, m0, find, mp;
AnsiString sm, sn, txt1 = "Кількість операці - ";
Рекурсивная функция:
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
void bucketSort(int ar[], const int sz)
{
    const int Rasryad = 10;
    const int Position = 20000;
    int TempArray[Rasryad][Position] = {0};
    int number = 1, Ras;
    for(int i = 0; i < N; i++)
    {
        count = 0;
        for(int j = 0; j < sz; j++)
        {
            Ras = ar[j] / number % 10;
            TempArray[Ras][j] = ar[j];
        }
        for(int a = 0; a < Rasryad; a++)
        {
            for(int b = 0; b < Position; b++)
            {
                if(TempArray[a][b] != 0)
                {
                    ar[count++] = TempArray[a][b];
                    TempArray[a][b] = 0;
                }
            }
        }
        number *= 10;
    }
    for(int i = 0; i < sz; i++)
        sm += IntToStr(mas[i]) + "  ";
}
Код подпрограммы:
C++
1
2
3
4
5
6
7
8
9
10
11
    sm = " ";
    Memo1 -> Lines -> Add(zagol);
    Memo1 -> Lines -> Add(nachzag);
    for (i = 0; i < N; i++)
    {
        mas[i] = 200 + random(300);
        sm += IntToStr(mas[i]) + "  ";
    }
    Memo1 -> Lines -> Add(sm);
    sm = " ";
    Memo1 -> Lines -> Add(kinczag);
Код кнопки:
C++
1
2
3
4
    PodProgram1("Сортування списком", "Початковий масив", "Результат");
    bucketSort(mas, N);
    Memo1 -> Lines -> Add(sm);
    Memo1 -> Lines -> Add(" ");
Добавлено через 6 минут
спс все!!!

Добавлено через 19 минут
подпрограмма:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void __fastcall TSortAndFind::PodProgram1(AnsiString zagol, AnsiString nachzag, AnsiString kinczag)
{
    sm = " ";
    Memo1 -> Lines -> Add(zagol);
    Memo1 -> Lines -> Add(nachzag);
    for (i = 0; i < N; i++)
    {
        mas[i] = 200 + random(300);
        sm += IntToStr(mas[i]) + "  ";
    }
    Memo1 -> Lines -> Add(sm);
    sm = " ";
    Memo1 -> Lines -> Add(kinczag);
}
0
Zuck
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 5
16.12.2013, 21:30 #11
я в массивах не силен. можно по-лучше обьяснить?

Добавлено через 1 минуту
gorin, можно по подробней обьяснить?
0
System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
07.04.2015, 17:27 #12
Дошел до этого задания по книге Дейтела. Вот может кому интересно выкладую код,насколько я понял, так и выполнил .Работает правильно,комментарии вставил чтоб более понятно было и специально сделал печать всех массивов на всех стадиях сортировки
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
#include <iostream>
#include <iomanip>
#include <vcl.h>
#include <cstdlib>
 
using namespace std;
 
void bucketSort(int[],int,int[][10]); // прототип функции
 
int main()
{
  const int size=10; // размер массивов
  int array[size]={5,8,19,12,97,3,45,23,77,100}; // массив который нужно отсортировать
  int array1[size][size]={0}; // массив в котором будут заноситься числа
  bucketSort(array,size,array1); // вызов функции
  cout <<endl;
  system("pause");
  return 0;
}
 
void bucketSort(int ar[],int x,int ar1[][10]) // передаем функции оба массива
{
    // t - индекс элемента,куда переносить с блочного массива
    // обратно в 1ый массив
   int t=0;
   // d - разряды чисел.
   int d=1;
        // выполняем цикл 3 раза.Т.к. у нас наибольшее число 100 с 3мя разрядами
        // 1-ый для d=1,2-ой для d=10, 3ий для d=100
        for(int z=0;z<3;z++)
        {
           t=0;  // сброс счетчика в 0 при каждом проходе цикла
           for(int i=0;i<x;i++)
           {
        // каждый элемент 1го массива, приваиваем 2ому массиву,где строка
        // которого получается путём деления i на d и остаток от деления
        // на 10, строка остается та же i
             ar1[(ar[i]/d)%10][i]=ar[i];
           }
        // присваеваем обратно элементы со 2го массива,не равные 0,
        // обратно в 1ый массив по порядку, в котором они распределились
           for(int i=0;i<x;i++)
           {
              for(int j=0;j<x;j++)
                if(ar1[i][j]!=0)
                {
                   ar[t]=ar1[i][j];
                   t++;
                }
           }
        // для наглядности - печать 2го блочного массива и 1го массива
        cout << setw(3) << "    0 " << "   1 " << "   2 "
             << "   3 " << "   4 "
             << "   5 " << "   6 "
             << "   7 " << "   8 "
             << "   9 " << endl << endl;
 
           for(int i=0;i<x;i++)
           {
              cout << i << " ";
              for(int j=0;j<x;j++)
                 cout << setw(3) << ar1[i][j] << "  ";
              cout << endl;
           }
           cout << endl << endl << "array[10] = ";
           for(int i=0;i<x;i++)
               cout << ar[i] << " ";
           cout << endl << endl;
        // обнуляем блочный массив
           for(int i=0;i<x;i++)
              for(int j=0;j<x;j++)
                 ar1[i][j]=0;
        // в конце каждого цикла умножаем d на 10 для следующего разряда
           d*=10;
        }
}
0
07.04.2015, 17:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2015, 17:27
Привет! Вот еще темы с ответами:

Блочная сортировка с пузырьком - C++
Необходимо написать блочную сортировку на с++. В блочном варианте алгоритма сортировки исходный массив разбивается на несколько ...

Блочная сортировка структур (Отсортировать массив структур по фамилии) - C++
Подскажите алгоритм блочной сортировки структур на языке С++. Мне нужно отсортировать массив структур по фамилии.

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

Сортировка массива: перенести положительные числа в начало, а отрицательные - в конец массива - C++
Дан вещественный массив A(N). Отсортировать его таким образом, чтобы все положительные числа находились в начале, а отрицательные - в конце...


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

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

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