Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Ziberman
1 / 1 / 3
Регистрация: 23.09.2014
Сообщений: 45
#1

Сортировку вставками меняем на Пирамидальную сортировку и на Сортировку подсчётом - C++

07.11.2014, 20:53. Просмотров 316. Ответов 1
Метки нет (Все метки)

Здравствуйте. Я не как не могу разобраться.Помогите. У меня есть листинг сортировки вставками:
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
#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;
 void insertSort(int *, int); // прототип функции сортировки вставками
 
int main(int argc, char* argv[])
{
   
// Заповнення массиву рандомними числами
 srand(time(NULL));
    setlocale(LC_ALL, "rus");
    cout << "Введите размер массива: ";
    int size_array; // длинна массива
    cin >> size_array;
 
    int *sorted_array = new int [size_array]; // одномерный динамический массив
    for (int counter = 0; counter < size_array; counter++)
    {
        sorted_array[counter] = rand() % 100; // заполняем массив случайными числами
        cout << setw(2) << sorted_array[counter] << "  "; // вывод массива на экран
    }
    cout << "\n\n";
 
 //Визначення часу роботи алгоритму
    unsigned int start_time =  clock(); 
    selectSort(sorted_array, size_array); // вызов функции сортировки пузырьком
 
    unsigned int end_time =  clock(); 
    
for (int counter1 = 0; counter1 < size_array; counter1++)
    {
        cout << setw(2) << sorted_array[counter1] << "  "; // печать отсортированного массива
    }
    cout << "\n";
 
    unsigned int search_time = end_time - start_time;
 
    cout << "Time of performing the sort: "<< search_time;
  
    system("pause");
    return 0;
}
 
 
void selectSort(int* arr, int size) 
{
    int tmp, i, j, pos;
    for(i = 0; i < size; ++i) // i - номер текущего шага
    { 
        pos = i; 
        tmp = arr[i];
        for(j = i + 1; j < size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] < tmp) 
            {
               pos = j; 
               tmp = arr[j]; 
            }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}
Я хочу сделать Пирамидальную сортировку:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void heapify (int pos, int n) {
    while (2 * pos + 1 < n) {
    //пока не вышли за грань массива   
        int t = 2 * pos +1;// находим первого сына
        if (2 * pos + 2 < n && arr[2 * pos + 2] >= arr[t])
                //если второй сын существует и больше чем первый
        {
            t = 2 * pos + 2;//берем его
        }
        if (arr[pos] < arr[t])
                {
                // если наибольший из сыновей больше
                // чем предок, то меняем их местами
            swap(arr[pos], arr[t]);
            pos = t;// теперь предком является следующий элемент
        } 
        else break;
        //иначе куча с головой в pos построена.
    }
}
Надо вставить в первый пример (с сортировкой вставками) алгоритм Пирамидальной сортировки. Я как не пытался выбивало ошибки.
И еще я хотел попробовать вставить в первый пример вместо алгоритма вставками алгоритм Сортировки подсчётом:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void counting_sort(int* vec, int len, int min, int max)
{
    assert(len > 0);
    assert(min <= max);
    assert(vec != NULL);
 
    int cnt[max-min+1];
 
    for (int i = min; i <= max; ++i) {
        cnt[i - min] = 0;
    }
 
    for (int i = 0; i < len; ++i) {
        ++cnt[vec[i] - min];
    }
 
    for (int i = min; i <= max; ++i) {
        for(int j = cnt[i - min]; j--;) {
            *vec++ = i;
        }
    }
}
Но тоже выбивает ошибки.Прошу подскажите как правильно.

Добавлено через 8 часов 48 минут
Вот попробовал ну чет не хочет правильно работать. Помогите кто в курсе.
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
#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;
void heapify(int *, int); // прототип функции сортировки 
 
int main(int argc, char* argv[])
{
   
// Заповнення массиву рандомними числами
 srand(time(NULL));
    setlocale(LC_ALL, "rus");
    cout << "Введите размер массива: ";
    int size_array; // длинна массива
    cin >> size_array;
 
    int *sorted_array = new int [size_array]; // одномерный динамический массив
    for (int counter = 0; counter < size_array; counter++)
    {
        sorted_array[counter] = rand() % 100; // заполняем массив случайными числами
        cout << setw(2) << sorted_array[counter] << "  "; // вывод массива на экран
    }
    cout << "\n\n";
 
 
    unsigned int start_time =  clock(); 
    heapify(sorted_array, size_array); // вызов функции сортировки 
 
    unsigned int end_time =  clock(); 
    
for (int counter1 = 0; counter1 < size_array; counter1++)
    {
        cout << setw(2) << sorted_array[counter1] << "  "; // печать отсортированного массива
    }
    cout << "\n";
 
    unsigned int search_time = end_time - start_time;
 
    cout << "Time of performing the sort: "<< search_time;
  
    system("pause");
    return 0;
}
 
 
void heapify(int* arr, int pos, int n)
{
    while (2 * pos + 1 < n) {
    //пока не вышли за грань массива   
        int t = 2 * pos +1;// находим первого сына
        if (2 * pos + 2 < n && arr[2 * pos + 2] >= arr[t])
                //если второй сын существует и больше чем первый
        {
            t = 2 * pos + 2;//берем его
        }
        if (arr[pos] < arr[t])
                {
                // если наибольший из сыновей больше
                // чем предок, то меняем их местами
            swap(arr[pos], arr[t]);
            pos = t;// теперь предком является следующий элемент
        } 
        else break;
        //иначе куча с головой в pos построена.
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.11.2014, 20:53
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Сортировку вставками меняем на Пирамидальную сортировку и на Сортировку подсчётом (C++):

Сортировку вставками меняем на сортировку слиянием
Код программы выполняет сортировку массива вставками. Как сюда вставить код...

Как ускорить пирамидальную сортировку?
Второй цикл for в пирамидальной сортировке можно было бы сократить, добавив...

Подскажите как эту сортировку переделать в сортировку по алфавиту?
Подскажите как эту сортировку переделать в сортировку по алфавиту?? ...

Реализовать сортировку вставками
задание: Написать программу, реализующую один из простых методов сортировки...

Реализовать сортировку вставками
Реализовать сортировку вставками (в порядке возрастания значений) для...

Как реализовать сортировку вставками?
Дорогие форумчане. на учебе дали задание по сортировки вставками. Берется...

1
Lateralus
8 / 8 / 0
Регистрация: 05.11.2011
Сообщений: 78
08.11.2014, 16:09 #2
Мой друг,я ещё новичок в C++ и могу ошибаться,но-помоему, у тебя 2 ошибки:
1.Ты забыл подключить stdlib.h для функции rand();
2.У тебя в прототипе функции 2 параметра, а в определении(описании) функции-3 параметра, т.е.несоответствие параметров.
С уважением от начинающего C++ программиста.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2014, 16:09
Привет! Вот еще темы с решениями:

Как осуществить сортировку вставками в списках?
Необходимо отсортировать список по алфавиту, помогите пожалуйста. Добавлено...

Нужно применить сортировку вставками, к этому коду
#include &lt;iostream&gt; using namespace std; int main() { int n, *arr1,...

Задача на сортировку
Не понимаю в чем дело( Прошу помочь с кодом) #include &lt;iostream&gt; using...

Выполнить сортировку
Выполнить сортировку целочисленного массива (поиск в массиве) из n элементов....


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

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

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