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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 56, средняя оценка - 4.77
paradox92
 Аватар для paradox92
0 / 0 / 0
Регистрация: 27.02.2010
Сообщений: 38
02.03.2010, 20:35     Блочная сортировка массива #1
Помогите пожалуйста написать такую программу.

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

Добавлено через 2 часа 24 минуты
Есть желающие помочь?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 2
03.03.2010, 13:32     Блочная сортировка массива #2
1. Самый простой и медленный алгоритм - метод пузырка. Для быстрый алгоритм имеет соответсвующее название - быстрая сортировка. Если не знаете, что за "пузырь" - погуглите.
2. В цикле проверяем текущий массив с заданым.
paradox92
 Аватар для paradox92
0 / 0 / 0
Регистрация: 27.02.2010
Сообщений: 38
03.03.2010, 20:04  [ТС]     Блочная сортировка массива #3
тут нужна сортировка именно блочным методом
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 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;
}
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 2
03.03.2010, 20:18     Блочная сортировка массива #5
Цитата Сообщение от paradox92 Посмотреть сообщение
тут нужна сортировка именно блочным методом
Поисковик в помощь
gorin
 Аватар для gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
24.10.2011, 19:56     Блочная сортировка массива #6
Евгений М., здравствуйте, на картинках все понятно как оно все работает, но вот как реализовать, искал в НЕТЕ, так и не понял как реализовать!
Thinker
24.10.2011, 20:09
  #7

Не по теме:

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

gorin
 Аватар для 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);
, все компилируется но при нажатии "сортировать" ошибка!
gorin
 Аватар для gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
25.10.2011, 21:43     Блочная сортировка массива #9
Подскажите где ошибка, я просмотрел все нормально, а при выполнении не работает!
gorin
 Аватар для 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);
}
Zuck
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 5
16.12.2013, 21:30     Блочная сортировка массива #11
я в массивах не силен. можно по-лучше обьяснить?

Добавлено через 1 минуту
gorin, можно по подробней обьяснить?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2015, 17:27     Блочная сортировка массива
Еще ссылки по теме:

Сортировка массива. Ошибка после ввода размерности массива C++
C++ Блочная сортировка массива
Блочная сортировка массива. Не выходит C++

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

Или воспользуйтесь поиском по форуму:
System16v
 Аватар для 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;
        }
}
Yandex
Объявления
07.04.2015, 17:27     Блочная сортировка массива
Ответ Создать тему
Опции темы

Текущее время: 15:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru