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

Алгоритм Хоара - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Объединение, пересечение, разность множеств http://www.cyberforum.ru/cpp-beginners/thread18787.html
Это вполне стандартный алгоритм,может есть у кого готовый? Объединение, пересечение, разность множеств. Поверка на включение одного множества в другое.
C++ Дан текстовый файл открыть его удалить из него все пробелы Мне нужно решить такую задачу дан текстовый файл открыть его удалить из него все пробелы причем местоположение пробелов записать в другой файл, чтобы можно то удалять все пробелы то снова их вставлять на место. Помогите http://www.cyberforum.ru/cpp-beginners/thread18695.html
Системы счисления C++
Есто прога перевод числа из 2-ой в 10-ую систему счисления и обратно.Есть проблема как сделать чтоб она ещё и переводила отрицательные и не целые числа.Может кто знает как это сделать? #include<math.h> #include<conio.h> #include<stdlib.h> #include<stdio.h> #include<string.h> void main(void){ long int a,bb; char str;
Нахождение серий символов в строке C++
Приветствую, господа кодеры! При написании диплома появилась некоторая проблемка: Есть строка нулей и едениц (случайно расставлены). Нужно в ней найти количество серий этих нулей и едениц, т.е. подряд идущих одинаковых символов. Написал функцию, которая в качестве аргументов берет саму строку, маску символа (ноль или еденица) и длинну серии. Функция должна возвращать количество серий...
C++ Написать программу внесения в список информации о новых членах кооператива http://www.cyberforum.ru/cpp-beginners/thread18485.html
В списке содержится информация о владельцах гаражного кооператива: ФИО, марка автомобиля, номер машины. Написать программу внесения в список информации о новых членах кооператива, если данные о них отсутствуют в исходном файле.
C++ С++ для чайников Люди помогите скачал книгу "С++ для чайников" там написано как создавать проги а на чем,не написано...Помогите...на каком текстовом редакторе лучше прогроммировать!!! подробнее

Показать сообщение отдельно
mik-a-el
CyberForum Owner
 Аватар для mik-a-el
56368 / 36118 / 231
Регистрация: 10.04.2006
Сообщений: 12,597
17.12.2008, 23:07     Алгоритм Хоара
Она же быстрая сортировка.
Раз:
Код
//Quick Sort Functions for Descending Order
// (2 Functions)
void quicksort(apvector <int> &array, int top, int bottom)
{
      // top = subscript of beginning of vector being considered
      // bottom = subscript of end of vector being considered
      // this process uses recursion - the process of calling itself
     int middle;
     if (top < bottom)
    {
          middle = partition(array, top, bottom);
          quicksort(array, top, middle);   // sort top partition
          quicksort(array, middle+1, bottom);    // sort bottom partition
     }
     return;
}


//Function to determine the partitions
// partitions the array and returns the middle index (subscript)
int partition(apvector <int> &array, int top, int bottom)
{
     int x = array[top];
     int i = top - 1;
     int j = bottom + 1;
     int temp;
     do
     {
           do     
           {
                  j - -;
           }while (x >array[j]);

          do  
         {
                 i++;
          } while (x <array[i]);

          if (i < j)
         { 
                 temp = array[i];    // switch elements at positions i and j
                 array[i] = array[j];
                 array[j] = temp;
         }
     }while (i < j);    
     return j;           // returns middle index
}
Два:
Код
#include<process.h>
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

int Partition(int low,int high,int arr[]);
void Quick_sort(int low,int high,int arr[]);

void main()
{
int *a,n,low,high,i;
clrscr();
cout<<"/**************************Quick Sort Algorithm
Implementation*****************/

";
cout<<"Enter number of elements:
";
cin>>n;

a=new int[n];
/* cout<<"enter the elements:
";
for(i=0;i<n;i++)
cin>>a;*/
for(i=0;i<n;i++)
a[i]=rand()%100;
clrscr();
cout<<"
Initial Order of elements
";
 for(i=0;i<n;i++)
  cout<<a[i]<<"	";
  cout<<"
";

high=n-1;
low=0;
Quick_sort(low,high,a);
cout<<"
Final Array After Sorting:
";

  for(i=0;i<n;i++)
  cout<<a[i]<<"	";

getch();
}

/*Function for partitioning the array*/

int Partition(int low,int high,int arr[])
{ int i,high_vac,low_vac,pivot/*,itr*/;
   pivot=arr[low];
   while(high>low)
{ high_vac=arr[high];

  while(pivot<high_vac)
  {
    if(high<=low) break;
    high--;
    high_vac=arr[high];
  }

  arr[low]=high_vac;
  low_vac=arr[low];
  while(pivot>low_vac)
  {
    if(high<=low) break;
    low++;
    low_vac=arr[low];
  }
  arr[high]=low_vac;
}
  arr[low]=pivot;
   return low;
}

void Quick_sort(int low,int high,int arr[])
{
  int Piv_index,i;
  if(low<high)
  {
   Piv_index=Partition(low,high,arr);
   Quick_sort(low,Piv_index-1,arr);
   Quick_sort(Piv_index+1,high,arr);
  }
}
Три:
Код
#include "QuickSort.h"  

QuickSort::QuickSort(int n, int* x) : Sort(n, x) { 
this->algName = "Quick Sort [Center]"; 
} 

void QuickSort::Run(void) 
{ 
this->Launch(this->x, this->n); 
}

void QuickSort::Launch(int* x, int size) { 
long i = 0, j = size; // начальные значения 
int temp, p;  

p = x[ size>>1 ]; // выбираем середину

// процедура разделения
do {
while (x[i] < p) i++;
while (x[j] > p) j--;

if (i <= j) {

temp = x[i]; x[i] = x[j]; x[j] = temp;
this->CountSwap();
i++; j--;
}
} while (i <= j);

// рекурсивные вызовы, если есть, что сортировать
if ( j > 0 ) this->Launch(x, j);
if ( size > i ) this->Launch(x+i, size-i);
}

QuickSort::~QuickSort(void)
{
}
 
Текущее время: 01:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru