Глава_01

Назад | Начало урока | Вперед
Содержание

Глава 01 (продолжение 1)

Метод быстрой сортировки.



//параметризованная версия  алгоритма быстрой сортировки  

#include <iostream.h>

#include <string.h>

template <class Stype> void quick(Stype *item,int count);

template <class Stype> void qs(Stype *item,int left,int right);

main()
{


//сортировка массива символов
char str[] = "dcab";

quick(str, (int) strlen(str));

cout<<"Otsortirovannyi massiv  simvolov-  " << str << endl;

char enterchar;

  cout<<endl<<endl<<"Type any character to  finish:";

  cin>>enterchar;

//сортировка массивов целых чисел
int nums[] = {
5,7,3,9,5,1,8};

int i;
quick(nums,7);

cout<<" Otsortirovannyi massiv chisel : ";

for(i=0;i<7;i++) cout <<nums[i] <<" ";

//char enterchar;

  cout<<endl<<endl<<"Type any character to  finish:";

  cin>>enterchar;


return 0;

}



//входная функция быстрой сортировки

template <class Stype> void quick(Stype *item,int count)
{

	qs(item,0,count-1);

}


//параметризованная функция быстрой сортировки

template <class Stype> void qs(Stype *item,int left,int right)
{

  register int i,j;

  Stype x,y;

 i=left; j=right;

 x=item[(left+right)/2];

 do {

	 		 while(item[i]<x && i<right) i++;

		 while( x<item[j] && j<left) j--;

		 if(i<=j) {

			 y=item[i];

			 item[i]=item[j];

			 item[j]=y;

			 i++;j--;

		 }

	 }



     while(i<=j);

	 if(left<j) qs(item,left,j);

	 if(i<right) qs(item,i,right);

 }

Результат:

Otsortirovannyi massiv simvolov- abdc
Otsortirovannyi massiv chisel : 8 1 5 5 3 7 9

Назад | Начало урока | Вверх | Вперед
Содержание