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

Пирамидальная сортировка - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
maxim1994
0 / 0 / 0
Регистрация: 05.02.2014
Сообщений: 26
18.05.2014, 04:39     Пирамидальная сортировка #1
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int HeapSort (int *a, int n)
{ 
    int left = n/2+1, right=n-1, x;
    while (left>1)
        sift (a, --left, right);
    while (right>1)
    {
        x = a[1];
        a[1] = a[right];
        a[right] = x;
        sift (a, left, --right);
    }
    return 0;
}
Вот пример кода сортировка правильная !У меня такой вопрос мне нужно вывести через return кол во перестановок помогите пожалуйста а то на другом коде вылетает
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2014, 04:39     Пирамидальная сортировка
Посмотрите здесь:

Пирамидальная сортировка C++
C++ Пирамидальная сортировка
C++ Пирамидальная сортировка
Пирамидальная сортировка C++
C++ Пирамидальная сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Crast
 Аватар для Crast
70 / 70 / 1
Регистрация: 10.02.2013
Сообщений: 434
18.05.2014, 08:28     Пирамидальная сортировка #2
Если sift - это перестановка то как-то так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int HeapSort (int *a, int n)
{ 
    int left = n/2+1, right=n-1, x;
    int count = 0;
    while (left>1)
    {
        count++;
        sift (a, --left, right);
    }
    while (right>1)
    {
        x = a[1];
        a[1] = a[right];
        a[right] = x;
        count++;
        sift (a, left, --right);
    }
    return count;
}
maxim1994
0 / 0 / 0
Регистрация: 05.02.2014
Сообщений: 26
18.05.2014, 15:39  [ТС]     Пирамидальная сортировка #3
Crast, sifr просеивание через пирамиду вот посмотрите
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int sift (int *a, int left, int right) 
{
    int i, j, x=a[left];
    i = left; j = 2*left;
    if (j<right && a[j+1]<a[j]) 
        j++;        
    while (j<=right && a[j]<x)  
    {               
        a[i] = a[j];    
        i = j;      
        j *= 2;
        if (j<right && a[j+1]<a[j]) 
            j++;            
    }
    a[i] = x;
    return 0;
}
Gmails
5 / 5 / 2
Регистрация: 08.04.2014
Сообщений: 241
18.05.2014, 16:17     Пирамидальная сортировка #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
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
#include <iostream>
#include <conio.h>
#include <windows.h>
using namespace std;
void iswap(int &n1, int &n2)//обмен
{     
    int temp = n1;
    n1 = n2;
    n2 = temp;
}
 int main(){
    
    setlocale(0,"");
    puts("Пирамидальная сортировка:\n");{
    int countcompare=0; //счетчик сравнений
    int countswap=0; //счетчик обменов
    int const n = 100;
    int a[n];
    for ( int i = 0; i < n; ++i ) 
    a[i]=rand()%10;
 
    for ( int i = 0; i < n; ++i ) 
    cout<<a[i]<<" ";
    
    //-----------сортировка------------//
    
    int sh = 0; //смещение
    bool b = false;
    for(;;)
    {
    b = false;
    for ( int i = 0; i < n; i++ )
    {  
        if( countcompare++,i * 2 + 2 + sh < n )
        {
        if(countcompare++, ( a[i + sh] > /*<*/ a[i * 2 + 1 + sh] ) || ( a[i + sh] > /*<*/ a[i * 2 + 2 + sh] ) )
        {
            if (countcompare++, a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh] )
            {
            iswap( a[i + sh], a[i * 2 + 1 + sh] );countswap++;
            b = true;
            }
            else if (countcompare++, a[i * 2 + 2 + sh] < /*>*/ a[ i * 2 + 1 + sh])
                 {
                     iswap( a[ i + sh], a[i * 2 + 2 + sh]);countswap++;
                     b = true;
                 }
        }
        //дополнительная проверка для последних двух элементов
               
            if( countcompare++,a[i*2 + 2 + sh] < /*>*/ a[i*2 + 1 + sh] )
            {
            iswap( a[i*2+1+sh], a[i * 2 +2+ sh] );countswap++;
                        b = true;
            }
        }
        else if( countcompare++,i * 2 + 1 + sh < n )
             {
                 if( countcompare++,a[i + sh] > /*<*/ a[ i * 2 + 1 + sh] )
                 {
                     iswap( a[i + sh], a[i * 2 + 1 + sh] );countswap++;
                     b = true;
                 }
             }
    }
    if (!b) sh++; //смещение увеличивается, когда на текущем этапе
              //сортировать больше нечего
    if ( sh + 2 == n ) break;
    }  //конец сортировки
 
 
    cout << endl << endl;
    cout<<"\nсравнений:"<<countcompare<<endl;
    cout<<"\nОбменов"<<countswap<<endl;
    puts("После сортировки:\n");
    for ( int i = 0; i < n; ++i ) cout << a[i] << " ";}
    
    getch();
    return 0;
}
Yandex
Объявления
18.05.2014, 16:17     Пирамидальная сортировка
Ответ Создать тему
Опции темы

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