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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 51, средняя оценка - 4.88
almostclever
1 / 1 / 0
Регистрация: 04.03.2012
Сообщений: 101
#1

Сортировка бинарными вставками - C++

15.04.2012, 16:36. Просмотров 7689. Ответов 4
Метки нет (Все метки)

Если у кого нибудь есть, выложите рабочий код сортировки бинарными вставками. Просто Си.Буду благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.04.2012, 16:36     Сортировка бинарными вставками
Посмотрите здесь:

Сортировка бинарными вставками - C++
Сортировка бинарными вставками работает неправильно. Помогите найти ошибку. Вот код: template <class T> void swap(T& a, T& b){ ...

Сортировка бинарными вставками - C++
Имеется функция сортировки бинарными вставками, нужна программа, в которой она будет использоваться. Помогите написать void...

Сортировка вставками - C++
template< class T > void insertSort(T* a, int size) { T tmp; for (int i = 1, j; i < size; ++i) // цикл проходов, i - номер...

Сортировка вставками c++ - C++
Помогите пожалуйста как в С++ сортировать вставками в оконном виде ? Скиньте код.

Сортировка вставками - C++
Доброго времени суток, форумчане. Подскажите, пожалуйста, почему при первой реализации алгоритма массив упорядочивается, а при второй -...

Сортировка вставками - C++
Где-то ошибка в цикле... помогите) ... int array = {3, 2, 1}, min = 0, a = 0, b = 0; ... for(a = 1; a < size; ++a); ...

сортировка вставками - C++
Начал изучать Кормена. Написал первый алгоритм. Не сортируется первый элемент массива. Код написан по книге. #include<iostream> using...

Сортировка вставками - C++
Необходимо отсортировать весь массив методом вставками парных чисел на возрастание const int N = 4; int mas; void fill(){ ...

Сортировка вставками - C++
Сортировка вставками: пусть первые k элементов упорядочены по возростанию. Берется (k+1)-ый элемент и размещается среди первых k...

Сортировка вставками - C++
#include <iostream> #include <ctime> #include <iomanip> using namespace std; void insertionSort(int *, int); // прототип...

Сортировка вставками - C++
#include <stdio.h> #include <iostream> #include <ctime> using namespace std; const int n = 1000; int size; void...

Сортировка вставками. - C++
Пожалуйста помогите написать программу на языке "си" Дана последовательность чисел a1, a2, …, an . Требуется представить числа в...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
panicwassano
591 / 559 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
15.04.2012, 19:23     Сортировка бинарными вставками #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
/*Бинарными вставками*/
int sort_bin (int* data, int size) 
{
        int i;
        for (i = 0; i < size; i++) {
                int pos = -1;
                int start = 0;
                int end = i - 1;
                int numToInsert = data[i];
                // Находим место вставки с помощью бинарного поиска
                while (start <= end && !(pos != -1)) {
                        int middle = (start + end) / 2;
                        if (numToInsert > data[middle]) {
                                start = middle + 1;
                        } else if (numToInsert < data[middle]) {
                                end = middle - 1;
                        } else {
                                pos = middle;
                        }
                }
                if(end < 0){
                        // определяем позицию в случае если элемент меньше всех отсортированных
                        pos = 0;
                } else if(start >= i){
                        // определяем позицию в случае если элемент больше всех отсортированных
                        pos = i;
                }
                if (pos < i) {
                        // сдвигаем элементы вправо на одну позицию
                        int j;
                        for (j = i; j > pos; j--) {
                                data[j] = data[j - 1];
                        }
                        data[pos] = numToInsert;
                }
        }
        return *data;
}
/*-=End-=*/
работает лишь в отсортированном массиве, код нашел гугл, так что проверяйте
almostclever
1 / 1 / 0
Регистрация: 04.03.2012
Сообщений: 101
20.04.2012, 17:59  [ТС]     Сортировка бинарными вставками #3
может быть все таки есть у кого еще?
OasisKharkov
1 / 1 / 0
Регистрация: 28.07.2012
Сообщений: 35
06.06.2013, 13:28     Сортировка бинарными вставками #4
Делал лабу в институте, вот что получилось:
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
#include <iostream>
#include <ctime>
using namespace std;
 
void input_array(short* A, unsigned short n);
void output_array(short* A, unsigned short n);
void sort_array(short* A, unsigned short n);
 
void main()
{
    unsigned short n;
    cout << "Enter the number of elements: ";
    cin >> n;
    short* A = new short[n];
    input_array(A,n);
    output_array(A,n);
    sort_array(A,n);
    output_array(A,n);
}
 
void input_array(short* A, unsigned short n)
{
    srand((unsigned)time(NULL));
    for (unsigned short i = 0; i < n; i++)
        A[i] = rand()%200 - 100;
}
 
void output_array(short* A, unsigned short n)
{
    for (unsigned short i = 0; i < n; i++)
        cout << A[i] << " ";
    cout << "\n";
}
 
void sort_array(short* A, unsigned short n)
{
    short x;
    short left;
    short right;
    short sred;
    for (short i = 1;  i < n; i++) 
        if (A[i-1] > A[i]){
            x = A[i];
            left = 0;  
            right = i-1;  
            do {
                sred = (left + right)/2;    
                if  (A[sred] < x ) left = sred + 1;  
                else  right = sred - 1;      
            } while (left <= right);
            for (short j = i-1; j>=left; j--)
                A[j+1] = A[j];  
            A[left] = x;
      }
}
Сам алгоритм и объяснения нашел здесь: http://learnprogramm.ucoz.ru/index/b...vstavkami/0-71
lirik__
0 / 0 / 0
Регистрация: 21.03.2016
Сообщений: 1
21.03.2016, 02:14     Сортировка бинарными вставками #5
Бинарные вставки через рекурсию.
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
77
78
79
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <time.h>
 
using namespace std;
 
void out(int arr[], int size);
void in_rand(int arr[], int size);
 
int bin_insert(int arr[], int left, int right, int i, int& num_of_cmp)
{
    if (left > right)
        return left;    
 
    int mid = (left + right) / 2;
 
    if (arr[i] > arr[mid]){
        num_of_cmp++;
        bin_insert(arr, mid + 1, right, i, num_of_cmp);
    }
 
    else{
        num_of_cmp++;
        bin_insert(arr, left, mid - 1, i, num_of_cmp);
    }
}
 
void shift_right(int arr[], int i, int index, int& num_of_swap)
{
    int var_to_swap = arr[i];
    for (int k = i; k > index; k--){
        arr[k] = arr[k - 1];
        num_of_swap++;
    }
    arr[index] = var_to_swap;
    num_of_swap++;
}
 
int main()
{
    const int size = 10000;   // SIZE
    int arr[size];
    int num_of_cmp = 0, num_of_swap = 0;
    int index = 0;
 
    in_rand(arr, size);
    
    int time = clock();
    for (int i = 1; i < size; i++){
        if (arr[i] < arr[i - 1]){
            shift_right(arr, i, bin_insert(arr, 0, i - 1, i, num_of_cmp), num_of_swap);
        }
    }
    time = clock() - time;
    cout << endl << "Array with " << size << " elements was sorted for " << time << "ms" << endl << num_of_cmp << " compare and " << num_of_swap << " swap.\n\nPress the Enter to show sorted array." << endl;
 
 
    cout << endl << endl;
    _getch();
    out(arr, size);
 
    _getch();
    return 0;
}
 
void in_rand(int arr[], int size)
{
    srand(time(0));
 
    for (int i = 0; i < size; i++)
        arr[i] = rand() % 100;
}
 
void out(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << "  ";
}
Yandex
Объявления
21.03.2016, 02:14     Сортировка бинарными вставками
Ответ Создать тему
Опции темы

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