自学教程：C++ sorter函数代码示例

/** * Sort an (ascending) array of integers * * Arguments: * arr    The array to search * length Number of elements in the array * * Uses "quicksort" to sort "arr".  Use the first element of the array * as the pivot.   * * Your solution MUST use recursive function (or functions) *  * quicksort works in the following way:  *  * find an element in the array (this element is called the * pivot).  * * rearrange the array's elements into two parts: the part smaller * than this pivot and the part greater than this pivot; make the pivot * the element between these two parts *  * sort the first and the second parts separately by repeating the  * procedure described above *  * You will receive no point if you use any other sorting algorithm. * You cannot use selection sort, merge sort, or bubble sort. *  * Some students are fascinated by the name of bubble sort.  In * reality, bubble sort is rarely used because it is slow.  It is a * mystery why some students (or even professors) like bubble sort. * Other than the funny name, bubble sort has nothing special and is * inefficient, in both asymptotic complexity and the amount of data * movement.  There are many algorithms much better than bubble sort. * You would not lose anything if you do not know (or forget) bubble * sort. * */void sorter(int *arr, int length, int *start, int size){  int pivot = *start, *copy, count, curr, decr = 0, incr = 0;  copy = malloc(sizeof(int)*size);  for(count = 0; count < size; count++)    {      curr = *(start+count);      if(curr > pivot)        {          *(copy+ size - 1 + decr) = curr;          decr--;        }      if(curr < pivot)        {          *(copy+incr) = curr;          incr++;        }    }  for(count = 0; count < size - (incr-decr); count++)    *(copy+incr+count) = pivot;  for(count = 0; count < size; count++)    *(start+count)=*(copy+count);  free(copy);  if(incr>1)    sorter(arr, length, start, incr);  if(decr<-1)    sorter(arr, length, (start+size+decr), -decr);  }

/** * calls sorter for subArrays of current subArray of input array and merge sorted subArrays * @param array - array with data * @param p - start of subArray * @param r - end of subArray */void sorter(int *array, const int p, const int r) {    int q = (p+r)/2;    if(p < q) {        sorter(array, p, q);    }    if(q+1 < r) {        sorter(array, q+1, r);    }    merger(array, p ,r);}

AirspaceIntersectionVectorAirspaceCircle::Intersects(const GeoPoint &start, const GeoPoint &end,                           const TaskProjection &projection) const{  const fixed f_radius = projection.ProjectRangeFloat(m_center, m_radius);  const FlatPoint f_center = projection.ProjectFloat(m_center);  const FlatPoint f_start = projection.ProjectFloat(start);  const FlatPoint f_end = projection.ProjectFloat(end);  const FlatLine line(f_start, f_end);  FlatPoint f_p1, f_p2;  if (!line.intersect_circle(f_radius, f_center, f_p1, f_p2))    return AirspaceIntersectionVector();  const fixed mag = line.dsq();  if (!positive(mag))    return AirspaceIntersectionVector();  const fixed inv_mag = fixed(1) / mag;  const fixed t1 = FlatLine(f_start, f_p1).dot(line);  const fixed t2 = (f_p1 == f_p2) ?    fixed(-1) : FlatLine(f_start, f_p2).dot(line);  const bool in_range = (t1 < mag) || (t2 < mag);  // if at least one point is within range, capture both points  AirspaceIntersectSort sorter(start, *this);  if ((t1 >= fixed(0)) && in_range)    sorter.add(t1 * inv_mag, projection.Unproject(f_p1));  if ((t2 >= fixed(0)) && in_range)    sorter.add(t2 * inv_mag, projection.Unproject(f_p2));  return sorter.all();}

TEST(int_merge_sorter_test, test_six_element_array){    std::vector<int> example = {7,2,5,3,6,1};    IntMergeSorter sorter(example);    sorter.sort();    EXPECT_EQ("[1,2,3,5,6,7]", to_string(example));}

void QTodoList::sort(){	QTodoSortDialog sort_dialog;	deselectAll();	if(sort_dialog.exec() == QDialog::Accepted)	{		preserveContentsYPos();		const QTodoSortCriteriaMap* criterias = sort_dialog.getCriterias();		QPtrList<QWidget> list_widgets;		list_widgets.append(0);		QTodoListIterator it(this);		for(;it.current();++it)			list_widgets.append(it.current());		QTodoListItemsSorter sorter(&list_widgets,criterias);		QPtrList<QWidget>* sorted = sorter.get();		QTUM::get()->startRecording();		takeAll();		for(unsigned int i = 0; i < sorted->count(); ++i)		{			if(QTodoItem* item = dynamic_cast<QTodoItem*>(sorted->at(i)))			{				insertTodo(item,i);				item->setDepth(item->getDepth());			}		}		QTUM::get()->stopRecording();		restoreContentsYPos();	}}

    ArrayDesc inferSchema(std::vector< ArrayDesc> schemas, std::shared_ptr< Query> query)	{        //As far as chunk sizes, they can be a pain! So we allow the user to specify an optional chunk size        //as part of the sort op.        assert(schemas.size() >= 1);        ArrayDesc const& schema = schemas[0];        size_t chunkSize = 0;        for (size_t i =0; i<_parameters.size(); i++)        {            if(_parameters[i]->getParamType()==PARAM_LOGICAL_EXPRESSION)            {                chunkSize = evaluate(((std::shared_ptr<OperatorParamLogicalExpression>&)_parameters[i])->getExpression(),                                     query, TID_INT64).getInt64();                if(chunkSize <= 0)                {                    throw SYSTEM_EXCEPTION(SCIDB_SE_INFER_SCHEMA, SCIDB_LE_CHUNK_SIZE_MUST_BE_POSITIVE);                }                break;            }        }        // Use a SortArray object to build the schema.        // Note: even though PhysicalSort::execute() uses an expanded schema, with chunk_pos and cell_pos,        //       these additional attributes are projected off before returning the final sort result.        const bool preservePositions = false;        SortArray sorter(schema, arena::getArena(), preservePositions, chunkSize);        return sorter.getOutputArrayDesc();	}

int command(const char *cmd) {	if (strncasecmp(cmd,"pen",3)==0) pens(cmd);	else if (strncasecmp(cmd,"dot",3)==0) pens(cmd);	//else if (strncasecmp(cmd,"act",3)==0) action_link(cmd);	else if (strncasecmp(cmd,"act",3)==0) action(cmd);	else if (strncasecmp(cmd,"cust",4)==0) pens(cmd);	else if (strncasecmp(cmd,"sort",4)==0) sorter(cmd);	else if (strncasecmp(cmd,"prev",4)==0) move(cmd);	else if (strncasecmp(cmd,"next",4)==0) move(cmd);	else if (strncasecmp(cmd,"redr",4)==0) draw(None);	else if (strncasecmp(cmd,"mute",4)==0) mute(cmd);	else if (strncasecmp(cmd,"quit",4)==0) running = False;	else if (strncasecmp(cmd,"full",4)==0) toggle_fullscreen();	else if (strncasecmp(cmd,"zoom",4)==0) {		char *c;		if ( (c=strchr(cmd, ' ')) ) {			while (c && *c == ' ') c++;			if (*c == '/0') return 1;			if (*c == 'q') {				if (!(c=strchr(c, ' '))) return 1;				while (c && *c == ' ') c++;				if (*c == '/0') return 1;				else if (*c == '1') zoom_rect(0, 0, show->w/2, show->h/2);				else if (*c == '2') zoom_rect(show->w/2, 0, show->w, show->h/2);				else if (*c == '3') zoom_rect(0, show->h/2, show->w/2, show->h);				else if (*c == '4') zoom_rect(show->w/2, show->h/2, show->w, show->h);				else return 1;			}			else pens(cmd);		}		else return 1;	}	XSync(dpy, True);	return 0;}

void shellSort(Iterator begin, Iterator end, Sequence strideSeq, Predicate pred){    struct RecursiveSorter    {        RecursiveSorter(Iterator begin, Iterator end, Sequence strideSeq, Predicate pred):            beg_(begin), end_(end), strideSeq_(strideSeq), pred_(pred), numElems_(std::distance(beg_, end_)) {}        void sort(uint index)        {            if(strideSeq_(index + 1) < numElems_)                sort(index + 1);            detail::hSort(beg_, end_, strideSeq_(index), pred_);        }    private:        Iterator beg_, end_;        Sequence strideSeq_;        Predicate pred_;        uint numElems_;    };    RecursiveSorter sorter(begin, end, strideSeq, pred);    sorter.sort(0);}

int main(int argc, char* argv[]){	global_program_name.setValue2( argv[0] );	sorted_arguments = (InputArgument**) malloc( argc * sizeof(InputArgument*) );	try	{		for ( int index = 0; index < argc; ++index )			all_arguments.push_back( new InputArgument(index, argv[index]) );		assert(argc >= 2);		InputArgument input_count(1, argv[1]);		read_arguments( input_count.valueToUll() );		std::thread printer1( print_arguments_1, 0 );		std::thread sorter( sort_arguments );		printer1.join();		sorter.join();		std::thread printer2( print_arguments_2 );		printer2.join();		delete_arguments();		return 0;	}	catch(std::exception& exc)	{		std::cerr << "Exception: " << exc.what() << std::endl;		return 1;	}}

    void sort(Master&                   master,               //!< master object              const Assigner&           assigner,             //!< assigner object              std::vector<T> Block::*   values,               //!< all values to sort              std::vector<T> Block::*   samples,              //!< (output) boundaries of blocks              size_t                    num_samples,          //!< desired number of samples              const Cmp&                cmp,                  //!< comparison function              int                       k   = 2,              //!< k-ary reduction will be used              bool                      samples_only = false) //!< false: results will be all_to_all exchanged; true: only sort but don't exchange results    {        bool immediate = master.immediate();        master.set_immediate(false);        // NB: although sorter will go out of scope, its member functions sample()        //     and exchange() will return functors whose copies get saved inside reduce        detail::SampleSort<Block,T,Cmp> sorter(values, samples, cmp, num_samples);        // swap-reduce to all-gather samples        RegularDecomposer<DiscreteBounds> decomposer(1, interval(0,assigner.nblocks()), assigner.nblocks());        RegularSwapPartners   partners(decomposer, k);        reduce(master, assigner, partners, sorter.sample(), detail::SkipIntermediate(partners.rounds()));        // all_to_all to exchange the values        if (!samples_only)            all_to_all(master, assigner, sorter.exchange(), k);        master.set_immediate(immediate);    }

/** * calls bitonicSort for array with data and use it sort array * @param array - array with data */void sortParallel(int *array, const int length) {    #pragma omp parallel    {        #pragma omp single nowait        sorter(array, 0, length-1, MIN_ELEMENTS_FOR_PARALLELISM);    }}

AirspaceIntersectionVectorAirspaceCircle::Intersects(const GeoPoint &start, const GeoPoint &end) const{  AirspaceIntersectSort sorter(start, end, *this);  const fixed f_radius = m_task_projection->fproject_range(m_center, m_radius);  const FlatPoint f_center = m_task_projection->fproject(m_center);  const FlatPoint f_start = m_task_projection->fproject(start);  const FlatPoint f_end = m_task_projection->fproject(end);  const FlatLine line(f_start, f_end);  FlatPoint f_p1, f_p2;  if (line.intersect_circle(f_radius, f_center, f_p1, f_p2)) {    const fixed mag = line.dsq();    if (positive(mag)) {      const fixed inv_mag = fixed_one / mag;      const fixed t1 = FlatLine(f_start, f_p1).dot(line);      const fixed t2 = (f_p1 == f_p2) ?                       -fixed_one : FlatLine(f_start, f_p2).dot(line);      const bool in_range = (t1 < mag) || (t2 < mag);      // if at least one point is within range, capture both points      if ((t1 >= fixed_zero) && in_range)        sorter.add(t1 * inv_mag, m_task_projection->funproject(f_p1));      if ((t2 >= fixed_zero) && in_range)        sorter.add(t2 * inv_mag, m_task_projection->funproject(f_p2));    }  }  return sorter.all();}

QModelIndex KrVfsModel::addItem(vfile * vf){    emit layoutAboutToBeChanged();    if(lastSortOrder() == KrViewProperties::NoColumn) {        int idx = _vfiles.count();        _vfiles.append(vf);        _vfileNdx[vf] = index(idx, 0);        _nameNdx[vf->vfile_getName()] = index(idx, 0);        emit layoutChanged();        return index(idx, 0);    }    QModelIndexList oldPersistentList = persistentIndexList();    KrSort::Sorter sorter(createSorter());    int insertIndex = sorter.insertIndex(vf, vf == _dummyVfile, customSortData(vf));    if (insertIndex != _vfiles.count())        _vfiles.insert(insertIndex, vf);    else        _vfiles.append(vf);    for (int i = insertIndex; i < _vfiles.count(); ++i) {        _vfileNdx[ _vfiles[ i ] ] = index(i, 0);        _nameNdx[ _vfiles[ i ]->vfile_getName()] = index(i, 0);    }    QModelIndexList newPersistentList;    foreach(const QModelIndex &mndx, oldPersistentList) {        int newRow = mndx.row();        if (newRow >= insertIndex)            newRow++;        newPersistentList << index(newRow, mndx.column());    }

typename SortedList<T, Pred>::Node* SortedList<T, Pred>::merge_lists(typename SortedList<T, Pred>::Node* list1, unsigned length1, typename SortedList<T, Pred>::Node* list2, unsigned length2, const Sorter &sorter){	unsigned i = 0, j = 0;	SortedList<T, Pred>::Node* front = sorter(list1->Data, list2->Data) ? list1 : list2;	// I will arbitrarily decide to just shove everything into list1.	while (i < length1 && j < length2 && list2 != tail_)	{		if (sorter(list1->Data, list2->Data))		{			list1 = list1->Next;			++i;		}		else		{			SortedList<T, Pred>::Node* temp = list2;			list2 = list2->Next;			++j;			moveNode(temp, list1->Prev);		}	}	// If there's any left over, append the rest.	// If list1 is longer it's already in order and junk, so we	// don't worry about it at all./*	while (j < length2 && list2 != tail_)	{		SortedList<T, Pred>::Node* temp = list2;		list2 = list2->Next;		++j;		moveNode(temp, list1->Prev);		list1 = list1->Next;	} */	// Aaaaaactually, all that is unnecessary.	// In mergesort, the right block is always adjacent to the left block.	// So, there's no point worrying about it, it's already appended for	// your convenience.	// The two should be stuck together now.	// This should work because lists we're comparing should all be	// adjacent to each other.	return(front);}

 // Serilize Constructor MessageTaskDeliver()     : Message( PROTOCOL_VERSION , 131 , 0 ) {     task_id( "" );     uri_list(  );     aligner( "" );     sorter( "" );     reference( "" ); }

int main() {  int shook_array[kArraySize] = {};  RandomizeArray(shook_array, kArraySize);  ArraySorter<int, QuickSort> sorter(shook_array, kArraySize);  sorter.Run();  sorter.PrintResult();  return 0;}

 // sort data void sort() {     if ( ! is_sorted && !simple )     {         _sorted_data.resize( _data.size() );         for ( size_t i = 0; i < _data.size(); ++i )             _sorted_data[ i ] =  &( _data[ i ] );         range::sort( _sorted_data, sorter() );         is_sorted = true;     } }

int main(int argc, char **argv){    int n_processes;    if (argc < 3){        printf("Usage: uniquify <filename> <number-of-sorting-processes>/n");        printf("You invoked the program incorrectly. Aborting.");        return -1;    }    FILE *wordlist = fopen(&argv[1][0], O_RDONLY);    n_processes = argv[2][0];    #ifdef DBG    printf("%d processes shall be used/n", n_processes);    #endif    int proc_pids[n_processes];    FILE *pipes[n_processes][2];//0 for write end, 1 for read end    int ptr = 0;    //create n_processes processes    int i=0;    for(i = n_processes; i<0; i++){        pipe(pipes[i]);        sorter(&pipes[i][0], &proc_pids[i]);    }    int ch;    do{        ch = getc(wordlist);        if ((ch > 64) && (ch < 91)){//char is uppercase            fputs((ch + 32), &pipes[ptr][1]);        }        else if((ch>96) && (ch < 123)){            fputs(ch, &pipes[ptr][1]);        }        else{            if (ptr < n_processes){                ptr++;            }            else{                ptr = 0;            }            fputs(NULL, pipes[ptr][1]);        }    }while(ch != EOF);    ptr = 0;    while (ptr<n_processes){        fputs(EOF,pipes[ptr][1]);        close(pipes[ptr][1]);        fopen(&pipes[ptr][0], O_RDONLY);        ptr++;    }    fclose(wordlist);   //make uniquifier process    //magically hand next-word to uniquifier}

void SignalPeptide::sortExons(){  ExonComparator cmp;  BOOM::VectorSorter<PeptideExon> sorter(exons,cmp);  switch(strand)    {    case FORWARD_STRAND:      sorter.sortAscendInPlace();      break;    case REVERSE_STRAND:      sorter.sortDescendInPlace();      break;    }}

//returns convex hull of the algo's smallest setsstd::vector<Point2D> get_hull(std::vector<Point2D> points){    int pole_pos = get_pole(points);    Point2D pole = points[pole_pos];    points.erase(points.begin() + pole_pos);    sort_class sorter(pole);    std::sort(points.begin(), points.end(), sorter);    std::vector<Point2D> hull = graham_scan(points, pole);    return hull;}

int		csort(t_list *a, t_list *b){	long	ta;	long	tb;	ta = ((t_file*)(a->content))->stats.st_ctime;	tb = ((t_file*)(b->content))->stats.st_ctime;	if (ta == tb)	{		ta = ((t_file*)(a->content))->stats.st_ctimespec.tv_nsec;		tb = ((t_file*)(b->content))->stats.st_ctimespec.tv_nsec;		if (ta == tb)			return (sorter(b, a));	}	return ((int)(ta - tb));}

typename SortedList<T, Pred>::Node* SortedList<T, Pred>::findMinNode(typename SortedList<T, Pred>::Node* current, typename SortedList<T, Pred>::Node* min, const Sorter &sorter){	if (current != tail_)	{		if (sorter(current->Data, min->Data))		{			return(findMinNode(current->Next, current, sorter));		}		else		{			return(findMinNode(current->Next, min, sorter));		}	}	return(min);}

bool palIListSortTest() {  int_container a,b,c,d,e,f,g;  a.z = palGenerateRandom();  b.z = palGenerateRandom();  c.z = palGenerateRandom();  d.z = palGenerateRandom();  e.z = palGenerateRandom();  f.z = palGenerateRandom();  g.z = palGenerateRandom();  palIList ilist_head;  ilist_head.AddHead(&a.list_node);  ilist_head.AddHead(&b.list_node);  ilist_head.AddHead(&c.list_node);  ilist_head.AddHead(&d.list_node);  ilist_head.AddHead(&e.list_node);  ilist_head.AddHead(&f.list_node);  ilist_head.AddHead(&g.list_node);  palIListSorterDeclare(int_container, list_node) sorter(&ilist_head);  palIListForeachDeclare(int_container, list_node) fe(&ilist_head);  printf("Unsorted/n");  while (fe.Finished() == false)  {    int_container* list_entry = fe.GetListEntry();    printf("%d/n", list_entry->z);    fe.Next();  }  sorter.Sort(int_container_compare);  fe.First();    printf("Sorted/n");  while (fe.Finished() == false)  {    int_container* list_entry = fe.GetListEntry();    printf("%d/n", list_entry->z);    fe.Next();  }  return true;}

void run_sort(void *orig, size_t nelem, size_t size,        int (*compar)(const void *, const void *),        void (*sorter)(void *, size_t, size_t,                int (*compar)(const void *, const void *)),        const char *sortername) {    unsigned int start, end;    start = get_time();    sorter(orig, nelem, size, compar);    end = get_time();    printf("%s:/n", sortername);        if (start != 0 && end != 0) {        printf("time spent: %u usec/n", sortername, end - start);    } else {        printf("error while trying to get time spent");    }}

void Set::setupLights(const Math::Vector3d &pos) {	if (!_enableLights) {		g_driver->disableLights();		return;	}	// Sort the ligths from the nearest to the farthest to the pos.	Sorter sorter(pos);	Common::sort(_lightsList.begin(), _lightsList.end(), sorter);	int count = 0;	foreach (Light *l, _lightsList) {		if (l->_enabled) {			g_driver->setupLight(l, count);			++count;		}	}}