Třídění čísel – C / C++ – Fórum – Programujte.com

Ahoj, snažím se setřídit velké množství čísel seškrtáváním tak abych našel nejvyšší číslo a od něj čísla na obě strany klesaly(rostoucí čísla - nejvyšší číslo - klesající čísla). Nejlepší postup co mě napadl je zredukovat duplikáty (všechna stejná čísla nahradit jedním - 1, 2, 2, 2, 3, 5 = 1, 2, 3, 5), potom najít nejvyšší číslo "zprava" (1, 8, 2, 3, 4, 8, 5, 6, 8, 1)  a od něj to porovnávat doprava i doleva menší než (1 < 8 < 2 < 3 < 4 < 8 < 5 < 6 < 8 >1) - 2 "vyškrtnutí". Nemáte lepší postup?(nejde mi o rychlost ale o co nejmíň vyřazených čísel)

Díky

takze vlastne uprostred pole bude nejvyssi cislo a pak na kazdou stranu se budou snizovat?

v první řadě to bude nejspíš potřeba setřidit od nejmensiho po nejvetsi... potom do novýho pole to začít tridit.. pokud budou nejaky cisla 2x nebo vickrat, tak je vzdy hodit bud napravo nebo vlevo od stredu

šlo by to i s prohazováním cisel v tom samim poli, ale myslim ze s pomocnym polem to je snazsi

Nestacilo by zotriedit cisla pomocou std::sort(c++) alebo qsort(c)  a potom vypisovat kazde cislo s parnym indexom ako keby bolo nalavo od maxima a kazde cislo s neparnym indexom ako napravo(pripadne opacne)?

Jde mi o to seřadit to tím vyřazováním (vyřazuju čísla dokud to není tak jak má - stoupá - vrchol - klesá). Příklad - 1 8 2 3 4 8 6 - 1 2 3 4 8 6 (škrtnu 8) - chci vyškrtnout co nejmíň čísel tak aby to splňovalo ty podmínky.

Takze ty nechces aby sa prvky pola presuvali, cize nechces zoradit pole.

Teraz som si to naprogramoval a nie je to tak jednoduche ako to na prvy pohlad vyzera. Hlavne ta podmienka:

vyškrtnout co nejmíň čísel

Na co to vlastne potrebujes?

Nejspíš se můžeš snažit sebevíc, ale vždycky najdeš jenom heuristiku, co funguje na nějaká konkrétní data, ale nikoliv obecně. Pokud ti nejde o rychlost, ale správnost, tak použit prohledávání stavového prostoru, tj. postupně vyřazuj jednotlivé kombinace čísel a zkoušej, jestli je posloupnost po vyřazení již setříděná a pamatuj si ten nejlepší pokus.

Ja som to spravyl nasledovne:

Vyradil som vsetky rovnake prvky stojace pri sebe a odpametal si vsetky maxima (nie hodnoty, ale iteratory na maximalne prvky)

Pre kazde maximum som spravyl pole intov ktore bolo rovnako velke ako pole dat.

Kazde pole bolo rozdelene na lavu a pravu cast od vrchola (maxima).

Prvok v novom poli reprezentuje "vahu" prvka s rovnakym indexom v povodnom(datovom) poli.

Kazdy integer(vaha) v novom poli obsahuje pocet cisel ktore treba vyradit z pola dat tak aby sa mohlo ponechat cislo z rovnakym indexom v poli dat.

Potom odstranit prvok z pola ktory ma najvecsiu vahu ( z lavej aj pravej casti zvlst). Odstranenie prvka vyzera tak ze sa mu nastavy vaha na -1 a v dalsich cykloch sa bude prvok ignorovat. 

Znovu sa prepocitaju vsetky vahy a opakuje sa to dovtedy kym na lavej aj pravej strane su prvky s vahou vecsou ako 0.

Teraz nove pole obsahuj vahy s hodnotami 0  a  -1, prvy z datoveho pola s vahou -1 su vyradene a prvky s vahou 0 sa mozu pouzit.

Samozrejme je to spravene pre vsetky vrcholy(maxima), uz si staci vybrat kombinaciu ktora je najdlhsia.

Trochu spraseny kod   :

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <limits>
using namespace std;

typedef int num_t;
typedef int weight_t;

class Tops{
		vector<vector<num_t>::iterator>	data;
	public:
		num_t value()const{return *data.front();}
		void reset(vector<num_t>::iterator x){data.clear();data.push_back(x);}
		void add(vector<num_t>::iterator x){data.push_back(x);}
		size_t size()const{return data.size();}
		vector<num_t>::iterator operator [](size_t i)const{return data[i];}
		vector<vector<num_t>::iterator>::iterator begin(){return data.begin();}
		vector<vector<num_t>::iterator>::iterator end(){return data.end();}
		Tops(vector<num_t>::iterator x){data.push_back(x);}
};
class Weights{
		const vector<num_t>& data;
		vector<num_t>::const_iterator	top;	//vrchol
		vector<weight_t>::iterator	wtop;	//vrchol(vaha)
		vector<weight_t> weights;			//vahy
		vector<weight_t>::iterator max_left, max_right;	//maxima
		size_t	a_size;		//pocet aktyvnych prvkov
	public:
		size_t size()const{
			return a_size;
			}
		
		Weights(const vector<num_t>& data, vector<num_t>::const_iterator top):data(data), top(top), weights(data.size(), 0), a_size(data.size()){
			auto d = data.begin();		//aktualny prvok v data
			auto w = weights.begin();	//aktualna vaha
			
			//lava cast od vrcholu:
			max_left = w;
			for(; d != top; ++d, ++w){
				auto x = data.begin();
				if(*d == *top){
					 *w = numeric_limits<int>::max();
					 max_left = w;
					 continue;
				 }	
				
				for( ; x != d; ++x)if(*x >= *d)++(*w);//lava cast od testovaneho prvku
				for(++x; x != top; ++x)if(*x <= *d)++(*w);//prava cast od testovaneho prvku
				
				if(*w > *max_left)max_left = w;
			}
			
			//prava cast od vrcholu:
			wtop = w;
			++d;	//vrchol sa ignoruje
			++w;	//vrchol sa ignoruje
			max_right = w;
			for(auto d_begin = d; d != data.end(); ++d, ++w){
				auto x = d_begin;
				if(*d == *top){
					 *w = numeric_limits<int>::max();
					 max_right = w;
					 continue;
				 }
				
				for( ; x != d; ++x)if(*x <= *d)++(*w);//lava cast od testovaneho prvku
				for(++x; x != data.end(); ++x)if(*x >= *d)++(*w);//prava cast od testovaneho prvku
				
				if(*w > *max_right)max_right = w;
				
			}
			//reduce(data);
		}
		
		size_t reduce(){
			vector<num_t>::const_iterator d;		//aktualny prvok v data
			vector<int>::iterator w;		//aktualna vaha
			
			//lava cast od vrcholu
			while(*max_left > 0){
				d = data.begin();		//aktualny prvok v data
				w = weights.begin();	//aktualna vaha
			
				(*max_left) = (-1);		//oznaci prvok ako zmazany
				--a_size;				//znizi pocet aktivnych prvkov
				max_left = w;			//nastavy maximum ako prvy prvok
				
				for(; d != top; ++d, ++w){
					if(*w < 0)continue;		//preskoci zmazane prvky
					if(*d != *top)*w = 0;	//vynuluje vahu
					else{
						 *w = numeric_limits<int>::max();
						 max_left = w;
						 continue;
					 }	
					
					auto x = data.begin();
					auto y = weights.begin();
					
					//prepocita vahy:
					for( ; x != d; ++x, ++y)if(*x >= *d && *y >= 0 )++(*w);//lava cast od testovaneho prvku
					for(++x, ++y; x != top; ++x, ++y)if(*x <= *d && *y >= 0)++(*w);//prava cast od testovaneho prvku
					
					if(*w > *max_left)max_left = w;
				}
			}
			
			while(*max_right > 0){
				d = (top  + 1);	//vrchol sa ignoruje
				w = (wtop + 1);	//vrchol sa ignoruje
		
				(*max_right) = (-1);
				--a_size;
				max_right = w;
				
				auto x_begin = d;
				auto y_begin = w;
								
				for(; d != data.end(); ++d, ++w){	
					if(*w < 0)continue;
					if(*d != *top)*w = 0;
					else{
						 *w = numeric_limits<int>::max();
						 max_right = w;
						 continue;
					 }	

					auto x = x_begin;
					auto y = y_begin;
					
					for( ; x != d; ++x, ++y)if(*x <= *d && *y >= 0 )++(*w);//lava cast od testovaneho prvku
					for(++x, ++y; x != data.end(); ++x, ++y)if(*x >= *d && *y >= 0 )++(*w);//prava cast od testovaneho prvku
					
					if(*w > *max_right)max_right = w;
					
				}
			}
			return a_size;
		}
		void print()const{
			for(auto a : weights){
				if(a == -1)cout << setw (4)<< "   -  ";
				else if(a == numeric_limits<int>::max())cout << setw (4)<< "   M  ";
				else cout << setw (4) << a << ", ";
			}
			cout << endl;
		}
		void print(const vector<num_t>& data)const{
			auto d = data.begin();
			auto w = weights.begin();
			for(;d!= data.end(); ++d, ++w)
				if(*w == 0)cout << setw (4) << *d << "  ";
		}
		
		Weights(const Weights& x) = delete;
		Weights(Weights&& x) = default;
	
};

int main(){
	vector<num_t>	data = { 1, 8, 2, 2, 2, 3, 4, 8, 8, 6};
	
	auto i = data.begin(); 
	for(auto d = data.begin();d != data.end();++i){

		*i = *d;
		while(d != data.end() && *d == *i)++d;
		
	}
	data.erase(i, data.end());
	
	Tops max(data.begin());
	for(auto d = data.begin() + 1;d != data.end();++d){
		if(max.value() < *d)max.reset(d);
		else if(max.value() == *d)max.add(d);
		
	}
	
	cout << "input : ";
	for(auto x : data)cout << setw (4) << x << "  ";
	
	vector<Weights>	weights;
	for(auto& top : max)
		weights.emplace_back(data, top);
	
	cout << "\n-----------------------------\n";
	for(auto& w : weights){
		
		cout << "      : ";w.print();
		w.reduce();
		cout << "      : ";w.print();
		cout << "output: ";w.print(data);
		
		cout << "\n-----------------------------\n";
	}
		
}

edit: opraveny kod