Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.59/49: Рейтинг темы: голосов - 49, средняя оценка - 4.59
paradox92
0 / 0 / 1
Регистрация: 27.02.2010
Сообщений: 38
#1

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

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

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

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

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

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

Блочная сортировка массива. Не выходит
Суть такова-есть массив, который генерируется рандомно, и размер которого...

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

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

Блочная сортировка с++
Приветствую,можете мне помочь решить данное задание? В массиве содержится не...

11
Евгений М.
1051 / 989 / 100
Регистрация: 28.02.2010
Сообщений: 2,874
Завершенные тесты: 2
03.03.2010, 13:32 #2
1. Самый простой и медленный алгоритм - метод пузырка. Для быстрый алгоритм имеет соответсвующее название - быстрая сортировка. Если не знаете, что за "пузырь" - погуглите.
2. В цикле проверяем текущий массив с заданым.
0
paradox92
0 / 0 / 1
Регистрация: 27.02.2010
Сообщений: 38
03.03.2010, 20:04  [ТС] #3
тут нужна сортировка именно блочным методом
0
CyBOSSeR
Эксперт С++
2309 / 1682 / 148
Регистрация: 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
Евгений М.
1051 / 989 / 100
Регистрация: 28.02.2010
Сообщений: 2,874
Завершенные тесты: 2
03.03.2010, 20:18 #5
Цитата Сообщение от paradox92 Посмотреть сообщение
тут нужна сортировка именно блочным методом
Поисковик в помощь
0
gorin
209 / 16 / 4
Регистрация: 18.08.2009
Сообщений: 571
24.10.2011, 19:56 #6
Евгений М., здравствуйте, на картинках все понятно как оно все работает, но вот как реализовать, искал в НЕТЕ, так и не понял как реализовать!
0
Thinker
24.10.2011, 20:09
  #7

Не по теме:

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

0
gorin
209 / 16 / 4
Регистрация: 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
209 / 16 / 4
Регистрация: 18.08.2009
Сообщений: 571
25.10.2011, 21:43 #9
Подскажите где ошибка, я просмотрел все нормально, а при выполнении не работает!
0
gorin
209 / 16 / 4
Регистрация: 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 / 1
Регистрация: 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

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

блочная сортировка, не работает
Добрый день, не работает сортировка блочная, выдает ошибку (скрин во вложении)...

Блочная сортировка строк матрицы, изменить направление сортировки
Эта программа сортирует строки,с помощью блочной сортировки в порядке...


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

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

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