Сортировка массива

[Chainik!]

Не могу решить легкую на слух задачу!

Дан массив, элементы которого равны либо единицы либо двойки. Написать программу, которая расставит элементы таким образом, чтобы за каждой единицой следовала двойка, причем если каких то елементов больше, то они выписываются в конец. Например, последовательность {2,1,1,1,2,1} должна преобразовываться в {1,2,1,2,1,1}.

#include "stdafx.h"
#include "iostream"
#include "conio.h"
#include "time.h"
using namespace std;
//----------------------------------------
void print(int arr[], int n)
{
	for(int i = 0; i < n; i++)
		cout << arr[i] << " ";
}
//----------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
	const int n = 6;
	int arr[] = {2,1,1,1,2,1};
	cout << "Massiv imeet vid: ";
	print(arr,n);
	for(int i = 0; i < n; i++)
	{
		for(int j = n - 1; j >= 0; j--)
		{
			if(arr[i] > arr[j] && arr[i + 1], arr[j]) swap(arr[i],arr[j]);
		}
	}
	cout << "\n\n";
	print(arr,n);
	_getch();
	return 0;
}

[Stilet]

Я бы в таком направлении двигался:

	const int n = 6;
	int arr[] = {2,1,1,1,2,1};
	cout << "Massiv imeet vid: ";
	print(arr,n);
        int uno=0,duo=0;for(int i=0;i<n;i++) if(arr[i]==1) uno++; else duo++;
        for(int i=0;i<n;i++){
         if(i<=uno) printf("%5f",uno);
         if(i<=duo) printf("%5f",duo);
        }
	_getch();
	return 0;

Р.S. Не проверял...

[Chainik!]

У меня былы такая мысль, полностью поддерживаю.

[BDA]

Вроде работает (красивое решение не приходит в голову):

#include "stdafx.h"
#include "iostream"
#include "conio.h"
#include "time.h"
#include "algorithm"

using namespace std;
//----------------------------------------
void print(int arr[], int n)
{
	for(int i = 0; i < n; i++)
		cout << arr[i] << " ";
}
//----------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
	const int n = 6;
	int arr[] = {2,1,1,1,2,1};
	cout << "Massiv imeet vid: ";
	print(arr, n);
	int t1 = 0, t2 = 0;
	for (int i = 0; i < n; ++i) {
		t1 += arr[i] == 1;
		t2 += arr[i] == 2;
	}
	for (int i = 0; i < 2 * min(t1, t2); i += 2) {
		arr[i] = 1;
		arr[i + 1] = 2;
	}
	for (int i = 2 * min(t1, t2), k = (t1 > t2) ? 1 : 2; i < n; ++i)
		arr[i] = k;
	cout << "\n\n";
	print(arr,n);
	_getch();
	return 0;
}

Более "веселый" вариант:

#include "stdafx.h"
#include "iostream"
#include "conio.h"
#include "time.h"
#include "algorithm"
using namespace std;
//----------------------------------------
void print(int arr[], int n)
{
	for(int i = 0; i < n; i++)
		cout << arr[i] << " ";
}
//----------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
	const int n = 6;
	int arr[] = {2,1,1,1,2,1};
	cout << "Massiv imeet vid: ";
	print(arr, n);
	int fl = 1, j;
	for (int i = 0; i < n && fl; ++i) {
		if (arr[i] % 2 == i % 2) {
			for(j = i + 1; j < n && arr[i] == arr[j]; ++j);
			if (j < n)
				swap(arr[i], arr[j]);
			else
				fl = 0;
		}
	}
	cout << "\n\n";
	print(arr, n);
	_getch();
	return 0;
}

[Chainik!]

BDA, спасибо

[Chainik!]

А, все понял.

#include "stdafx.h"
#include "iostream"
#include "conio.h"
#include "time.h"
using namespace std;
//----------------------------------------
void srand(int arr[], int n)
{
	srand(time(NULL));
	for(int i = 0; i < n; i++)
		arr[i] = rand() % 3;
}
//----------------------------------------
void print(int arr[], int n)
{
	for(int i = 0; i < n; i++)
		cout << arr[i] << " ";
}
//----------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
	const int n = 30;
	int arr[n], res[n], k = 0;
	srand(arr,n);
	for(int i = 0; i < n; i++)
	{
		if(arr[i] != 0)
			res[k++] = arr[i];
	}
	cout << "Massiv imeet vid: ";
	print(res,k);
	//-----------------------------------------
	for(int i = 0; i < k; i+=2)
	{
		for(int j = i + 1; j < k; j++)
		{
			if(res[i] != 1 && res[j] == 1)
				swap(res[i],res[j]);
		}
	}
	//-----------------------------------------
	for(int i = 1; i < k; i+=2)
	{
		for(int j = i + 1; j < k; j++)
		{
			if(res[i] != 2 && res[j] == 2)
				swap(res[i],res[j]);
		}
	}
	//-----------------------------------------
	cout << "\n\n";
	print(res,k);
	_getch();
	return 0;
}

[rrrFer]

Ну да, тут все предложили сортировку подсчетом )
осталось заметить что это лучший вариант и выполняется за линейное время

[_Bers]

http://ideone.com/MYc0Ab

#include <algorithm>    // std::random_shuffle
#include <iostream>
using namespace std;
 
template<class T,size_t N> void view(const T (&ar)[N])
{
    cout<<"ar[]={";
    for(size_t n=0;n<N-1;++n) cout<<ar[n]<<",";
    cout<<ar[N-1]<<"}\n";
}
 
template<class T,size_t N> void mysort(T (&ar)[N])
{
    bool needOne=true;
    for(size_t n=0;n<N;++n)
    {
        const bool isOne = ar[n]==1;
        const bool isIgnore = (needOne && isOne) || (!needOne && !isOne);
 
        //--- отладочный вывод в консоль
        if(n<10)   cout<< ((isIgnore)? "ignr "    : "proc "   );
        if(n>10)   cout<< ((isIgnore)? "ignr  "   : "proc  "  );
        if(n>100)  cout<< ((isIgnore)? "ignr   "  : "proc   " );
        if(n>1000) cout<< ((isIgnore)? "ignr    " : "proc    ");
        cout<<" :       "<<std::string(2*n,' ')<<"*"<<endl;
        cout<<"n = "<<n<<" : "; view(ar); 
 
        needOne = !needOne;
 
        if(isIgnore) continue;
 
        T* it = std::find(ar+n,ar+N,  (isOne? 2: 1)  );
        if(it==ar+N) break;
        std::swap(ar[n], *it);
    }
}
 
 
 
template<class T,size_t N> void test_sort(T (&ar)[N])
{
    std::random_shuffle ( ar, ar+N );
    mysort(ar);
}
 
template<class T> bool check_array(const T (&ar)[15])
{
    int re[]={1,2,1,2,1,2,1,2,1,2,1,2,2,2,2};
    cout<<"expected: \n"; view(re);
 
    size_t n=0;
    while( n<15 && re[n]==ar[n]) ++n;
    return n==15;
}
 
 
 
 
int main() 
{
	cout<<"WELLCOME TO TESTING MY ALGORITHM\n\n";
 
 
    bool all_valid=true;
    for(size_t n=0;n<10;++n) 
    {
        int ar[]={2,1,1,1,2,1,2,2,1,1,2,2,2,2,2};
 
        view(ar);
        test_sort(ar);
        cout<<"actual: \n"; view(ar);
 
        const bool is_valid = check_array(ar);
 
        if(is_valid) cout<<"success!!!!\n";
        else
        {
            cout<< "failed";
            all_valid = false;
        }
    }
 
    cout<< (all_valid? "all testing are valid": "part tests are failed" )<<endl;
	return 0;
}

[_Bers]

Вот другая версия, ещё более быстрого алгоритма:

http://ideone.com/MYc0Ab

#include <set>
#include <algorithm> // std::random_shuffle
#include <iostream>
using namespace std;

template<class T,size_t N> void view(const T (&ar)[N])
{
    cout<<"ar[]={";
    for(size_t n=0;n<N-1;++n) cout<<ar[n]<<",";
    cout<<ar[N-1]<<"}\n";
}

template<class T,size_t N> void mysort(T (&ar)[N])
{
    typedef multiset<T> Myset;
    typedef typename Myset::iterator It;

    Myset myset(ar,ar+N);

    //отладочный вывод:
    //It it = myset.begin(); size_t n=0;
    //while(it!=myset.end()){ cout<< n<<" : "<< *it<<endl;  ++it;++n; }
    //--------------------------------------------

    const size_t num_one = myset.count(1);
    const size_t num_two = myset.count(2);
    const int tail_el = (num_two>num_one)? 2: 1;

    const size_t lenbody = min(num_two,num_one);
    const size_t lentail = max(num_two,num_one)-lenbody;

	//отладочный вывод:
    //cout<<"number of 1 : "<<num_one<<endl;
    //cout<<"number of 2 : "<<num_two<<endl;
    //cout<<"tail        : "<<lentail<<endl;
    //cout<<"tail_element: "<<tail_el<<endl;
    //cout<<"body        : "<<lenbody<<endl;
    //--------------------------------------------

    const size_t size = lenbody*2;
    for(size_t n=0;n<size;n+=2) { ar[n]=1; ar[n+1]=2; }
    for(size_t n=size;n< N; ++n) ar[n]=tail_el;
}



template<class T,size_t N> void test_sort(T (&ar)[N])
{
    std::random_shuffle ( ar, ar+N );
    mysort(ar);
}

template<class T> bool check_array(const T (&ar)[15])
{
    int re[]={1,2,1,2,1,2,1,2,1,2,1,2,2,2,2};
    cout<<"expected: \n"; view(re);

    size_t n=0;
    while( n<15 && re[n]==ar[n]) ++n;
    return n==15;
}




int main() 
{
	cout<<"WELLCOME TO TESTING MY ALGORITHM\n\n";
	    

    bool all_valid=true;
    for(size_t n=0;n<10;++n) 
    {
        int ar[]={2,1,1,1,2,1,2,2,1,1,2,2,2,2,2};

        view(ar);
        test_sort(ar);
        cout<<"actual: \n"; view(ar);

        const bool is_valid = check_array(ar);

        if(is_valid) cout<<"success!!!!\n";
        else
        {
            cout<< "failed";
            all_valid = false;
        }
    }

    cout<< (all_valid? "all testing are valid": "part tests are failed" )<<endl;
	return 0;
}

Примичание:

Здесь мы теряем всю скорость из-за:

1. Пересоздание массива в виде дерева multiset. Для этого производится обход по всему оригинальному массиву. Это колоссальная потеря времени.

2. При моздании дерева multiset задействуется стандартный аллокатор динамической памяти. Единократное использование которого проссаживает рантайм сильнее, чем вся остальная процедура сортировки вместе взятая.

Таким образом, не смотря на то, что сам по себе алгоритм более быстр, он даст профит к скорости только если изначально в качестве контейнера будет использован multiset, а не сишный массив.

И если стандартный аллокатор будет заменен на какой нибудь пул памяти, который не будет дергать кучу.