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

Сортировка массива с ограниченным количеством сравнений - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
roman ua
1 / 1 / 0
Регистрация: 06.03.2009
Сообщений: 25
25.11.2010, 15:51     Сортировка массива с ограниченным количеством сравнений #1
Задача состоит в следуещем:
" Ввести пять попарно различных целых чисел a, b, c, d, e. Упорядочить их по возрастанию, используя не более 7 сравнений. Предложить обобщенный алгоритм сортировки таких последовательностей, сохраняя пропорцию количества сравнений."

Основные алгоритмы сортировки я знаю , но у меня сильное ограничение на количество сравнений , тоесть если масив размерностю N то количество сравнений не больше N+2!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2010, 15:51     Сортировка массива с ограниченным количеством сравнений
Посмотрите здесь:

C++ Сортировка 5 чисел не более чем за 7 сравнений
C++ График зависимость количества перестановок и сравнений от размерности массива для алгоритмов сортировки
Шаблон с ограниченным кол-вом типов C++
C++ Два счетчика для обмена и сравнений для сортировки массива
Вычислить разность между количеством отрицательных и количеством положительных элементов одномерного массива C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
25.11.2010, 16:36     Сортировка массива с ограниченным количеством сравнений #2
Не совсем понятно, что значит "пять попарно различных" ?
roman ua
1 / 1 / 0
Регистрация: 06.03.2009
Сообщений: 25
25.11.2010, 16:51  [ТС]     Сортировка массива с ограниченным количеством сравнений #3
Цитата Сообщение от Kastaneda Посмотреть сообщение
Не совсем понятно, что значит "пять попарно различных" ?
Ето значит пара чисел a и b отличаются от пары c и d. Но может быть a=b или c=d ! Другими словами ето должны бить совсем разные целые числа!

Добавлено через 9 минут
Если ето поможет то вот код который у меня есть где реализрованы 3 метода сортировки , но количество сравнений в них явно превишает норму поставленную в задаче
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
 main.cpp
#include <iostream>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
#include "functions.h"
using namespace std;
 
void quickSortR(int* a, long N,int &Ctr1);
void bubbleSort(int* a, long N);    
void qSortI(int* a, long size);
long Print(int* a, long size);
int main()
{
    int * a, k,ki,  l;
    long N=0; int li=0;
    srand((NULL));
    int Selector=0;
    clock_t time;
    int i;
    //  time = clock();
    //  time = clock() - time;
    //  printf("%f\n", (double)time/CLOCKS_PER_SEC); //время выполнения "каких-то действий"*/
loop5:
    cout<<"Vvedit' rozmir masyvu\n";
    cin>>k;
    a=new int[k];
    cout<< "Vvid danyh:\n 1 - klaviatury \n 2 - generacija\n";
    cin>>ki;
    if(ki==1)
    {
        for ( l = 0; l < k; l++){
        cout<< "a["<<l<<"] =";
        cin>> a[l];
        cout<<"\n";
    }
    }
    if(ki==2)
    {
    for(l=0;l<k;l++)
    {
        a[l]=rand()%100+1;
    }
    }
    N=l-1;
    
    /*for( i=0;i<=N;i++){
    cout<<a[i]<<" ";
}*/
    cout<<"\n";
    cout<<"\n 1 - metod bul'bashky;\n 2 - QuickSort(metod Hoara);\n 3 - interaktyvnyj QuickSort;\n 0 - Vyhid\n 4 - Provesty zminy z masyvom\n\n";   
loop:
    cout<<"Vyberit' potribne\n";
    cin>>Selector;
    if(Selector==1){
        goto loop1;
    }
    if(Selector==2)
    {
        goto loop2;
    }
    if(Selector==3)
    {
        goto loop3;
    }
    if(Selector==0)
    {
        goto loop4;
    }
    
    if(Selector==4)
    {
        goto loop5;
    }
loop2:
    time = clock();
    quickSortR((int*) a, N,li); // Сортування Хоара
    time = clock() - time;
    Print((int*) a,  N+1);
    cout<<"Kilkist' perestvljan' ---> "<<li<<"\n";
    printf("\nChas vykonannja:%f sek.\n", (double)time/CLOCKS_PER_SEC);
    /*for(i=0;i<=N;i++)
    {
    cout<<a[i]<<" ";
    }
    cout<<"\n\n";*/
    goto loop; 
loop1:
    bubbleSort((int*) a, N+1);// Сортування методом бульбашки   
    /*for(i=0;i<=N;i++)
    {
    cout<<a[i]<<" ";
    }
    cout<<"\n\n";*/
 
    goto loop;
loop3:
    qSortI((int*) a, N+1);
    /*for(i=0;i<=N;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n\n";*/
    goto loop;
    getch();
loop4:
    return 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
132
133
134
135
136
137
138
139
 functions.h
#include <iostream>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
using namespace std;
int Ctr1=0;
long Print(int* a, long size);
/*****************************Швидке сортування Quick Sort****************************************/
void quickSortR(int* a, long N,int &Ctr1) {
    clock_t time;
    // На входе - массив a[], a[N] - его последний элемент.
    long i = 0, j = N;      // поставить указатели на исходные места
    int temp, p;
        time = clock();
    p = a[ N>>1 ];      // центральный элемент N>>1 --> N/2
    
    // процедура разделения
    do {
        while ( a[i] < p ) i++;
        while ( a[j] > p ) j--;
        
        if (i <= j) {
            temp = a[i]; a[i] = a[j]; a[j] = temp;
            Ctr1++;
            i++; j--;
        }
    } while ( i<=j );
    
    // рекурсивные вызовы, если есть, что сортировать 
    
        if ( j > 0 )quickSortR(a, j,Ctr1);
        if ( N > i )quickSortR(a+i, N-i,Ctr1);
 
        
}
 
 
 
 
/************************************Метод бульбашки**********************************************/
void bubbleSort(int* a, long size) {
    int Ctr2=0;
    clock_t time;
    long i, j;
    int x;
        time = clock();
    for( i=0; i < size; i++) {            // i - номер прохода
        for( j = size-1; j > i; j-- ) {     // внутренний цикл прохода
            if ( a[j-1] > a[j] ) {
                x=a[j-1]; a[j-1]=a[j]; a[j]=x;
               Ctr2++;
            }
        }
    }
     time = clock() - time;
    Print((int*) a, size);
    printf("\nChas vykonannja:%f sek.\n", (double)time/CLOCKS_PER_SEC);
    cout<<"Kilkist' perestvljan' --->"<< Ctr2<<"\n";
}
 
/*************************************Інтерактивний Quick sort********************************************/
 
#define MAXSTACK 2048 // максимальный размер стека
void qSortI(int* a, long size) {
 
    int  Ctr3=0; 
    clock_t time;
    long i, j; // указатели, участвующие в разделении
    long lb, ub; // границы сортируемого в цикле фрагмента
    
    long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
    // каждый запрос задается парой значений,
    // а именно: левой(lbstack) и правой(ubstack)
    // границами промежутка
    long stackpos = 1; // текущая позиция стека
    long ppos; // середина массива
    int pivot; // опорный элемент
    int temp;
        time = clock();
    lbstack[1] = 0;
    ubstack[1] = size-1;
    do {
        // Взять границы lb и ub текущего массива из стека.
        lb = lbstack[ stackpos ];
        ub = ubstack[ stackpos ];
        stackpos--;
        do {
            // Шаг 1. Разделение по элементу pivot
            ppos = ( lb + ub ) >> 1;
            i = lb; j = ub; pivot = a[ppos];
            do {
                while ( a[i] < pivot ) i++;
                while ( pivot < a[j] ) j--;
                if ( i <= j ) {
                    temp = a[i]; a[i] = a[j]; a[j] = temp;
                    Ctr3++;
                    i++; j--;
                }
            } while ( i <= j );
            
            // Сейчас указатель i указывает на начало правого подмассива,
            // j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
            // Возможен случай, когда указатель i или j выходит за границу массива
            
            // Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub
            if ( i < ppos ) { // правая часть больше
                if ( i < ub ) { // если в ней больше 1 элемента - нужно
                    stackpos++; // сортировать, запрос в стек
                    lbstack[ stackpos ] = i;
                    ubstack[ stackpos ] = ub;
                }
                ub = j; // следующая итерация разделения
                // будет работать с левой частью
            } else { // левая часть больше
                if ( j > lb ) {
                    stackpos++;
                    lbstack[ stackpos ] = lb;
                    ubstack[ stackpos ] = j;
                }
                lb = i;
            }
        } while ( lb < ub ); // пока в меньшей части более 1 элемента
    } while ( stackpos != 0 ); // пока есть запросы в стеке
    time = clock() - time;
    printf("\nChas vykonannja:%f sek.\n", (double)time/CLOCKS_PER_SEC);
    cout<<"Kilkist' perestvljan' --->"<< Ctr3<<"\n";
    Print((int*) a,  size);
}
long Print(int* a, long size)
{
    long i;
    cout << "   \nVidsortovanyj masyv \n";
for( i=0; i < size; i++) {            
    cout << a[i]<<" ";
}
cout<<endl;
return 0;
}
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
25.11.2010, 16:54     Сортировка массива с ограниченным количеством сравнений #4
Цитата Сообщение от roman ua Посмотреть сообщение
Другими словами ето должны бить совсем разные целые числа!
а судя по
Цитата Сообщение от roman ua Посмотреть сообщение
Предложить обобщенный алгоритм сортировки таких последовательностей
можно предположить, что парные числа всегда равны. Т.к. по-моему не реально рассортировать массив из 5 элементов, используя всего 7 сравнений.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.11.2010, 16:59     Сортировка массива с ограниченным количеством сравнений #5
roman ua, Для Вашего случая (когда 5 чисел), используя не более 7 сравнений можно реализовать так:
разбиваем на 2 части числа (в одной части будет 3 числа, во второй 2).
В этих частях делаем сортировку вставкой.
А потом обе части сортируем слиянием.
У вас получится не более 7 сравнений.
roman ua
1 / 1 / 0
Регистрация: 06.03.2009
Сообщений: 25
25.11.2010, 17:04  [ТС]     Сортировка массива с ограниченным количеством сравнений #6
Цитата Сообщение от Kastaneda Посмотреть сообщение
а судя по

можно предположить, что парные числа всегда равны. Т.к. по-моему не реально рассортировать массив из 5 элементов, используя всего 7 сравнений.
Но если предположить что парные числа всегда равны, возможно ли укластся в ети 7 сравнений??? Или еще один вопрос : какой из методов сортировки имеет наименшое количество сравнений ! Если можно виложы код ! Спасибо!

Добавлено через 5 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
roman ua, Для Вашего случая (когда 5 чисел), используя не более 7 сравнений можно реализовать так:
разбиваем на 2 части числа (в одной части будет 3 числа, во второй 2).
В этих частях делаем сортировку вставкой.
А потом обе части сортируем слиянием.
У вас получится не более 7 сравнений.
Спасибо конечно! И еще 1 вопрос , етот алгоритм можно использовать как обобщенный алгоритм сортировки таких последовательностей?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2010, 17:13     Сортировка массива с ограниченным количеством сравнений
Еще ссылки по теме:

C++ Сортировка одномерного массива методом слияния с минимальным количеством сравнений
Найти количество сравнений после сортировки массива C++
Быстрая сортировка, неправильный подсчет количества сравнений и перестановок C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.11.2010, 17:13     Сортировка массива с ограниченным количеством сравнений #7
Цитата Сообщение от roman ua Посмотреть сообщение
И еще 1 вопрос , етот алгоритм можно использовать как обобщенный алгоритм сортировки таких последовательностей?
Конечно можно.
Yandex
Объявления
25.11.2010, 17:13     Сортировка массива с ограниченным количеством сравнений
Ответ Создать тему
Опции темы

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