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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Работа с файлами и одномерный массив http://www.cyberforum.ru/cpp-beginners/thread197344.html
Помогите написать программу на С, которая считывает английский текст из файла и выводит на экран слова, начинающиеся с гласных букв... Просто сейчас времени разобраться в синтаксисе нет... Также не могу решить: Сжать одномерный массив, удалив из него все элементы, модуль которых не превышает 1. Освободившиеся в конце массива элементы заполнить нулями...
C++ Народ подскажите де ошибка пожалуста! Немогу разобратса((( Создать функцию, любым методом упорядочивает целочисленных массив. Входящие параметры - указатель на первый элемент, а также размерность массива; результат - упорядоченный по возрастанию входной массив. #include <iostream.h> #include <algorithm> // for std::swap void gnomeSort( int *array, int size ) { for ( int i = 1; i < size; ) { if ( array <= array ) { http://www.cyberforum.ru/cpp-beginners/thread197335.html
C++ трабла с MessageBox
Вот такая вот задачка сначала задается текст в ANSI ,затем его конвертируем в UNICODE и должны вывести его 3 способами - через _tprintf , WriteConsole, MessageBox . Написал однако почему-то не срабатывает .. #include "stdafx.h" #include <tchar.h> #include <locale.h> #include <iostream> #include <Windows.h> using namespace std; int main()
Отображение матрицы симметрично относительно вертикальной оси C++
Привет всем. Ещё одна задача на С. Вобщем есть матрица с каким угодно размером, 5*5 например, неимеет важности. Надо зделать так, чтобы отобразить ёё симетрично относительно вертикальной оси сектора матрицы, которые розположены влево и вправо от головной и вспомагательной диалонали. Может комуто поможет этот рисунок:...
C++ Реализировать метод нахождения гепотенузы и площади триугольника . http://www.cyberforum.ru/cpp-beginners/thread197327.html
обект прямоугольный триугольник , задан длинами катетов.Конструктор должен розрешыть создавать обекты з иницыализацией и без.Реалезировать метод нахождения гепотенузы и площади триугольника . неlp неlp неlp
C++ Массивы 1) Найти максимальный по модулю массив. 2) Найти сумму элементов массива, расположенных между первым и вторым положительными элементами. 3) Преобразовать массив таким способом, чтобы элементы, равные нулю, располагались после всех остальных. подробнее

Показать сообщение отдельно
roman ua
1 / 1 / 0
Регистрация: 06.03.2009
Сообщений: 25
25.11.2010, 16:51  [ТС]     Сортировка массива с ограниченным количеством сравнений
Цитата Сообщение от 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;
}
 
Текущее время: 07:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru