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

@adico · Регистрация: 24.02.2011

Author24 — интернет-сервис помощи студентам

Столкнулся с интересной задачей. Написать сортировку Хоара, как метод к контейнеру вектор. И сразу взялся за дело. Но

C++

#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++

#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;
}

Но ту тоже хочу исправить.

Вернуться к обсуждению:
Сорировка Хоара как метод класса. C++

Другие темы раздела
C++ подскажите: как вывести на экран числа от 0 до 20.... и еще одна: вывести все четные числа от 0 до 20... https://www.cyberforum.ru/ cpp-beginners/ thread311009.html подскажите: как вывести на экран числа от 0 до 20.... и еще одна: вывести все четные числа от 0 до 20... эт надо очень срочно....	Посчитать количество букв и найти самое длинное слово C++ Прошу помощи. Никак не могу написать прогу по следующим задачам. 1. Написать программу, которая будет подсчитывать количество согласных букв в строке, введенной с клавиатуры. 2. Написать программу, которая будет находить самое длинное слово в строке, введенной с клавиатуры, и подсчитывать, сколько раз оно встретилось в тексте. Если у кого есть что-нить похожее, выложите, я попробую сам...
C++ Множественное наследование Друзья прошу помочь разобраться, как получить доступ из массива J, к методу (O) из класса (С) #include <iostream> using namespace std; class A { public: virtual void M(){cout<<"Class A"<<endl;} https://www.cyberforum.ru/ cpp-beginners/ thread310988.html	C++ Ввод вывод, факториал Дано вещественное число W и целое число K (> 0). Вывести -W + W2/2! - W3/3! – ... + (–1)KXK/(K)! (K! = 1•2•...•N) https://www.cyberforum.ru/ cpp-beginners/ thread310960.html
C++ Дан текст каждый символ которого может быть малой буквой Дан текст каждый символ которого может быть малой буквой,цифрой или одним из знаков +,-,*.Группой букв будем называть такую совокупность последовательно расположенных букв, который непосредственно не предшествует и за который непосредственно не следует буква.Аналогично определим группу цифр и группу знаков а)Выяснить встречается ли в данном тексте группа букв one б)Выяснить верно ли что в...	C++ Классы и наследники https://www.cyberforum.ru/ cpp-beginners/ thread310925.html Доброго времени суток, я наверное уже достал этим вопросом, но помогите разобраться. По условию задания, у меня есть 2 класса: Sensor и Systema. У класса Sensor есть подклассы как вы уведите в листинге ниже. По условию, класс Systema знает о существовании только класса Sensor, а про существования подклассов он ничего не знает. Вопрос: как вложить в Systema подклассы и выдать их значения???(P.S....
C++ не Компилируется [Linker Error] https://www.cyberforum.ru/ cpp-beginners/ thread310919.html Ув.Программисты В общем я компилирую программу а она мне выдает одну ошибку вот она: Unresolved external'_main'referenced from c:\PROGRAM FILES\BORLAND\CBUILDER6\LIB\C0X32OBJ Вот Программа ,что нужно что бы она заработала? уже все перепробывал #include<stdio.h> #include<string.h> #include<conio.h>	STL__Графы C++ Граф задан набором дуг (неориентированных) и набором вершин. Найти все изолированные вершины, т.е. вершины, из которых не исходит ни одной дуги. ДУГА ЗАДАЁТСЯ ДВУМЯ ТОЧКАМИ пожалуйста с комментариями
C++ Найти номер строки матрицы, наиболее отдаленный от первой строки И опять и снова. Я так понимаю необходимо подключение библиотеки <cmath>,чтобы реализовать формулу? Помогите пожалуйста. Я конечно понимаю,что я постепенно скатилась до халявщины, сии но мат. вычисления в c++ пока для меня сложны. А начинать с чего попроще не ко времени. Спасибо большое. https://www.cyberforum.ru/ cpp-beginners/ thread310904.html	C++ Найти наибольший общий делитель всех элементов массива найти наибольший общий делитель всех элементов массива (на который они все делятся без остатка) https://www.cyberforum.ru/ cpp-beginners/ thread310902.html
Компиляция с заголовочным файлом C++ Стыдно спрашивать но все же. Никак не пойму как компилировать несколько файлов с заголовочным файлом. Вот что мне отвечает Dev-Cpp D:\...\main.cpp In function `int main()': 20 D:\...\main.cpp missing terminating " character 25 D:\...\main.cpp expected `)' before ';' token D:\...\Makefile.win Error 1 //main.cpp #include <iostream>	C++ метод половинного деления дана f(x). дан отрезок на котором расположены положительные корни дана точность E могу написать функцию, для нахождения одного корня на этом отрезке, а надо найти все. использовать нужно метод половинного деления. вот как выглядит эта функция int g(int a, int b, double E){ int c; for(b-a>E){ https://www.cyberforum.ru/ cpp-beginners/ thread310886.html

	02.06.2011, 18:57