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

Сорировка Хоара как метод класса. - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ подскажите: как вывести на экран числа от 0 до 20.... и еще одна: вывести все четные числа от 0 до 20... http://www.cyberforum.ru/cpp-beginners/thread311009.html
подскажите: как вывести на экран числа от 0 до 20.... и еще одна: вывести все четные числа от 0 до 20... эт надо очень срочно....
C++ Посчитать количество букв и найти самое длинное слово Прошу помощи. Никак не могу написать прогу по следующим задачам. 1. Написать программу, которая будет подсчитывать количество согласных букв в строке, введенной с клавиатуры. 2. Написать программу, которая будет находить самое длинное слово в строке, введенной с клавиатуры, и подсчитывать, сколько раз оно встретилось в тексте. Если у кого есть что-нить похожее, выложите, я попробую сам... http://www.cyberforum.ru/cpp-beginners/thread310991.html
C++ Множественное наследование
Друзья прошу помочь разобраться, как получить доступ из массива J, к методу (O) из класса (С) #include <iostream> using namespace std; class A { public: virtual void M(){cout<<"Class A"<<endl;}
C++ Ввод вывод, факториал
Дано вещественное число W и целое число K (> 0). Вывести -W + W2/2! - W3/3! – ... + (–1)KXK/(K)! (K! = 1•2•...•N)
C++ Дан текст каждый символ которого может быть малой буквой http://www.cyberforum.ru/cpp-beginners/thread310940.html
Дан текст каждый символ которого может быть малой буквой,цифрой или одним из знаков +,-,*.Группой букв будем называть такую совокупность последовательно расположенных букв, который непосредственно не предшествует и за который непосредственно не следует буква.Аналогично определим группу цифр и группу знаков а)Выяснить встречается ли в данном тексте группа букв one б)Выяснить верно ли что в...
C++ Классы и наследники Доброго времени суток, я наверное уже достал этим вопросом, но помогите разобраться. По условию задания, у меня есть 2 класса: Sensor и Systema. У класса Sensor есть подклассы как вы уведите в листинге ниже. По условию, класс Systema знает о существовании только класса Sensor, а про существования подклассов он ничего не знает. Вопрос: как вложить в Systema подклассы и выдать их значения???(P.S.... подробнее

Показать сообщение отдельно
adico
13 / 13 / 1
Регистрация: 24.02.2011
Сообщений: 64
02.06.2011, 18:57     Сорировка Хоара как метод класса.
Столкнулся с интересной задачей. Написать сортировку Хоара, как метод к контейнеру вектор. И сразу взялся за дело. Но
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
#include "stdafx.h"
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
 
template<class T>class cvector{
    T* pv;
    unsigned size;
public:
    cvector(){size=NULL; pv=new T[size];}
    cvector(unsigned size){this->size=size; pv=new T[size];}    
    void set(unsigned pos,T val){ pv[pos]=val;}
    T get(unsigned pos){return pv[pos];}
    void ins(unsigned pos,T val)
    {
        if(pos>size){return;}
        T* ptmp=new T[size+1];
        for(int i=0;i<pos;i++){ptmp[i]=pv[i];}
        ptmp[pos]=val;
        for(int i=pos+1;i<size+1;i++){ptmp[i]=pv[i-1];}
        pv=ptmp;
        delete [] pv;
        size++;
    }
    void del(unsigned pos)
    {
        if(pos>size){return;}
        T* ptmp=new T[size-1];
        for(int i=0;i<pos;i++){ptmp[i]=pv[i];}
        for(int i=pos+1;i<size-1;i++){ptmp[i]=pv[i+1];}
        pv=ptmp;
        delete [] pv;
        size--;
    }
    void insertSort(int size) {
          T x;
          int i, j;
          for(i=0; i < size; i++) {  // цикл проходов, i - номер прохода
            x = this->pv[i];   
                // поиск места элемента в готовой последовательности 
            for(j=i-1; j>=0 && this->pv[j] > x; j--)
              this->pv[j+1] = this->pv[j];    // сдвигаем элемент направо, пока не дошли
                // место найдено, вставить элемент
            this->pv[j+1] = x;
          }
   }
    void XoarSort(cvector<T> *a,int sizee) {
            long i = 0, j = sizee;            
            T temp, p=0;
            p = a->get(sizee>>1);                
            do{
                while(a->get(i)<p) i++;
                while(a->get(j)>p) j--;
            if(i<=j) {
                temp = a->get(i); a->set(i,a->get(j)); a->set(j,temp);
                i++; j--;
            }
            }while(i<=j);
 
            if (j>0){
                a->XoarSort(a,j);
            }
            if (sizee>i){
                a->XoarSort(a+i, sizee-i);
            }
    }
    void print(){
            for(unsigned i=0;i<size;i++)
                printf(" %d ",(int)this->pv[i]);
            printf("\r\n");
    }
    ~cvector(){size=0;delete [] pv;}
};
unsigned __int64 rdtsc()
{
    __asm rdtsc;
}
int _tmain(int argc, _TCHAR* argv[])
{
    srand(time(NULL));
    const int sizemas=10000;
    cvector<int>qwe(sizemas),qwe1(sizemas);
 
    for(int i=0;i<sizemas;i++){
        qwe.set(i,rand()%100);
        qwe1.set(i,qwe.get(i));
    }
    unsigned __int64 time0,time1,timetemp;
    timetemp=rdtsc();
    qwe.XoarSort(&qwe,sizemas-1);
    time0=rdtsc()-timetemp;
    qwe.print();
    timetemp=rdtsc();
    qwe1.insertSort(sizemas);
    time1=rdtsc()-timetemp;
    qwe.print();
    qwe1.print();
    printf("\n\rxoar    %d ",time0);
    printf("\n\rvstavka %d ",time1);
    getchar();
    return 0;
}
Как же ее правильно написать? Достаточно идеи.

Добавлено через 54 минуты
Нашел решение, но только с использованием еще одной переменной.
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
#include "stdafx.h"
#include <locale.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
 
template<class T>class cvector{
    T* pv;
    unsigned size;
public:
    cvector(){size=NULL; pv=new T[size];}
    cvector(unsigned size){this->size=size; pv=new T[size];}    
    void set(unsigned pos,T val){ pv[pos]=val;}
    T get(unsigned pos){return pv[pos];}
    void ins(unsigned pos,T val)
    {
        if(pos>size){return;}
        T* ptmp=new T[size+1];
        for(int i=0;i<pos;i++){ptmp[i]=pv[i];}
        ptmp[pos]=val;
        for(int i=pos+1;i<size+1;i++){ptmp[i]=pv[i-1];}
        pv=ptmp;
        delete [] pv;
        size++;
    }
    void del(unsigned pos)
    {
        if(pos>size){return;}
        T* ptmp=new T[size-1];
        for(int i=0;i<pos;i++){ptmp[i]=pv[i];}
        for(int i=pos+1;i<size-1;i++){ptmp[i]=pv[i+1];}
        pv=ptmp;
        delete [] pv;
        size--;
    }
    void VstavkaSort(int size) {
          T x;
          int i, j;
          for(i=0; i < size; i++) {  // цикл проходов, i - номер прохода
            x = this->pv[i];   
                // поиск места элемента в готовой последовательности 
            for(j=i-1; j>=0 && this->pv[j] < x; j--)
              this->pv[j+1] = this->pv[j];    // сдвигаем элемент направо, пока не дошли
                // место найдено, вставить элемент
            this->pv[j+1] = x;
          }
   }
    void XoarSort(cvector<T> &array, int top, int bottom)
    {
        int middle;
        if(top<bottom)
        {
              middle=partition(array, top, bottom);
              XoarSort(array, top, middle);  
              XoarSort(array, middle+1, bottom);  
         }
         return;
    }
    int partition(cvector<T> &array, int top, int bottom)
    {
        int x=array.get(top);
        int i=top-1;
        int j=bottom+1;
        int temp;
        do
        {     
            do     
            {
                j--;
            }while(x>array.get(j));
            do  
            {    
                i++;
            }while(x<array.get(i));
 
            if(i<j)
            { 
                temp = array.get(i);   
                array.set(i, array.get(j));
                array.set(j, temp);
            }
         
        }while (i<j);    
        return j;     
    }
    void print(){
            for(unsigned i=0;i<size;i++)
                printf(" %d ",(int)this->pv[i]);
            printf("\r\n");
    }
    ~cvector(){size=0;delete [] pv;}
};
unsigned __int64 rdtsc()
{
    __asm rdtsc;
}
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL,"rus");
    srand((unsigned)time(NULL));
    const int sizemas=10000;
    cvector<int>qwe(sizemas),qwe1(sizemas);
 
    for(int i=0;i<sizemas;i++){
        qwe.set(i,rand()%100);
        qwe1.set(i,qwe.get(i));
    }
    unsigned __int64 time0,time1,timetemp;
    timetemp=rdtsc();
    qwe.XoarSort(qwe,0,sizemas-1);
    time0=rdtsc()-timetemp;
    timetemp=rdtsc();
    qwe1.VstavkaSort(sizemas);
    time1=rdtsc()-timetemp;
    qwe.print();
    qwe1.print();
    printf("\n\rМетод   |Время");
    printf("\n\rХоар    |%d",time0);
    printf("\n\rВставка |%d",time1);
    getchar();
    return 0;
}
Но ту тоже хочу исправить.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 01:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru