0 / 0 / 0
Регистрация: 03.10.2016
Сообщений: 7
1

Найти k-ое по порядку число среди элементов массива(Древесная сортировка)

14.02.2017, 11:49. Показов 720. Ответов 0
Метки нет (Все метки)

Есть готовая лабораторная работа
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
using namespace std;
#include <clocale>
#include <conio.h>
#include <time.h>
int counter1;
int counter2;
int seach_medium(int L, int R, int mas[])
{
    int left, right, medium, ind_med;
    left=mas[L];
    right=mas[R];
    ind_med=(L+R+1)/2;
    medium=mas[ind_med];
    counter1++;
    if ((left==medium) && (medium==right))
    {
        int i=L;
        counter1++;
        while ((mas[i]==medium) && (i<R))
            i++;
        counter1++;
        if (mas[i]!=medium)
        {
            ind_med=i;
            medium=mas[ind_med];
        }
    }
    counter1++;
    if ((left==medium) && (medium==right))
        return -1;
    else 
    {
        counter1++;
        if (left<=medium)
        {
            counter1++;
            if (medium<=right)
                return ind_med;
            else 
            {
                counter1++;
                if (left<=right)
                    return R;
                else return L;
            }
        }
        else 
        {
            counter1++;
            if (left>=right)
            {
                counter1++;
                if (medium>=right)
                    return ind_med;
                    else return R;
            }
                else return L;
        }
    }
}
void sort(int mas[], int L, int R)
{
    int med_item, med_ind, t, i, j;
    med_ind=seach_medium(L,R,mas);
    if (med_ind!=-1)
    {
        med_item=mas[med_ind];
        i=L;
        j=R;
        while (i<=j)
        {
            counter1++;
            while (mas[i]<med_item)
                i++;
            counter1++;
            while (mas[j]>med_item)
                j--;
            if (i<=j)
            {
                t=mas[i];
                mas[i]=mas[j];
                mas[j]=t;
                i++;
                j--;
                counter2++;
            }
        }
        if (L<j)
            sort(mas,L,j);
        if (i<R)
            sort(mas,i,R);
    }
}
void main()
{
    setlocale(LC_ALL,"rus");
    counter1=0;
    counter2=0;
    cout<<"Введите количество элементов: ";
    int n;
    cin>>n;
    cout<<endl;
    int *mas=new int [n];
    //srand(time(NULL));
    for (int i=0;i<n;i++)
    {
        cout<<"Введите элемент "<<i+1<<": ";
        cin>>mas[i];
        cout<<endl;
    }
    cout<<"Исходный массив:"<<endl;
    for (int i=0;i<n;i++)
    {
        //mas[i]=rand()%100;
        cout<<mas[i]<<" ";
    }
    cout<<endl;
    sort(mas,0,n-1);
    cout<<"Отсортированный массив: "<<endl;
    for (int i=0;i<n;i++)
        cout<<mas[i]<<" ";
    cout<<endl;
    cout<<"Число сравнений: "<<counter1<<endl;
    cout<<"Число перестановок: "<<counter2<<endl;
    cout<<"Введите номер элемента 'k', который нужно найти: ";
    int k;
    cin>>k;
    cout<<"Элемент k: "<<mas[k-1]<<endl;
    getch();
}
подскажите, пожалуйста как в ней реализовать древесную сортировку
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.02.2017, 11:49
Ответы с готовыми решениями:

Найти k-ое по порядку число среди элементов массива шейкерской сортировкой
Найти k-ое по порядку число среди элементов массива это вроде получается, а как реализовать в коде...

Найти k-ое по порядку число среди элементов массива шейкерской сортировкой
Найти k-ое по порядку число среди элементов массива(шейкерской сортировкой)

Найти минимальное число среди положительных элементов массива
Найти минимальное число среди положительных элементов массива А(1:70)

Найти максимальное число среди повторяющихся элементов массива
Помогите решить задачку всем заранее спасибо 8-)! Дан двумерный массив 6,6 нужно найти...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.02.2017, 11:49
Помогаю со студенческими работами здесь

Найти максимальное число среди нечетных элементов массива
Разработать программу, которая будет состоять из нескольких функций: главная функция, функция...

Найти минимальное положительное число среди 14 элементов массива
Вот характеристика последовательности: Минимальное положительное число; n=14; Сделать нужно в...

Найти минимальное число среди элементов массива с индексом, кратным 3
1.Найти минимальное число среди элементов массива Е, индекс которых кратный 3 ( N -количество...

Найти среднее арифметическое число среди элементов отсортированного массива
(Помогите) Я просто пока не понял что такое типизированная константа. Задан одномерный массив...

Массив: Найти среди элементов массива число, квадрат которого имеет максимальное значение.
Даны целые числа х1, х2, х3,....х12. Найти среди них число, квадрат которого имеет максимальное...

Найти наибольший среди элементов кратных 6 и наименьший среди нечетных элементов массива
помогите с задачкой пожалуйста Задан массив Х(N). Найти наибольший среди элементов кратных 6 и...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru