Поредај боје  


Ниво тешкоће Средњи
Често питани у амазонка еБаи Екпедиа фацебоок Голдман Сакс Нвидиа пророчанство
Ред сортирање Тво Поинтер Тво Поинтерс

Сортирај боје је проблем у коме морамо да дамо поредак који садрже Н објеката. Свака кутија је обојена једном бојом која може бити црвена, плава и бела. Имамо Н предмета који су већ насликани. Морамо сортирати низ тако да објекти исте боје долазе непрекидно. Овде је црвена боја означена са 0, бела боја означена са 1, а плава боја означена са 2 респективно. Погледајмо пример описан на слици испод. На слици јасно видимо да су сви исти објекти у боји један уз другог. Два црвена предмета, три бела предмета и три плава предмета поређана су поредано.

Поредај бојеПин

Белешка: Не можемо користити било коју унапред дефинисану функцију библиотеке за сортирање Н објеката.

Улазни формат

Прва линија која садржи цео број који означава број објеката у низу.

Друга линија која садржи Н целих бројева.

Излаз

Испишите сортирани низ тако да су два предмета у истој боји увек суседна.

Ограничења

  • 1 <= Н <= 100000
  • 0 <= а [и] <= 2
6
0 1 0 2 1 2
0 0 1 1 2 2

Објашњење

Ми само користимо 3 променљиве за бројање броја 0,1 и 2. После бројања прво поставимо сву нулу на почетак користећи променљиву цоунт оф зеро.

И након што је поставио све оне и на крају све две.

Алгоритам за сортирање боја

Step:1 Set zero_count=0,one_count=0,two_count=0.
Step:2 For i in range 0 to N-1:
           If a[i] = 0 then:
               zero_count++.
           If a[i] = 1 then:
               one_count++.
           If a[i] = 2 then:
               two_count++.
Step:3 Set i=0.
Step:4 While(zero_count>0) then:
          a[i] = 0.
          zero_count--;
Step:5 While(one_count>0) then:
          a[i] = 1.
          one_count--;
Step:6 While(two_count>0) then:
          a[i] = 0.
          two_count--;
Step:7 Print the final array a.

Примена за сортиране боје

/*C++ Implementation of Sort Colors.*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{ 
    /*input values.*/ 
    int n; 
    cin>>n;
    int a[n];
    int zero_count=0,one_count=0,two_count=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        /*count all the same color objects.*/
        if(a[i]==0)
        {
            zero_count++;
        }
        else if(a[i]==1)
        {
            one_count++;
        }
        else
        {
            two_count++;
        }
    }
    int i=0;
    /*all objects with red color.*/
    while(zero_count>0)
    {
        a[i]=0;
        zero_count--;i++;
    }
    /*all object with white color.*/
    while(one_count>0)
    {
        a[i]=1;
        one_count--;i++;
    }
    /*all object with blue color.*/
    while(two_count>0)
    {
        a[i]=2;
        two_count--;i++;
    }
    /*print final result.*/
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0; 
}
6
1 2 1 0 2 0
0 0 1 1 2 2

Сложеност времена

НА) јер исписујемо Н вредности датог низа. Овде покрећемо једну линеарну петљу за испис коначног резултата.

Види такође
Реконструкција реда по висини

Сложеност простора

О (1) јер само користимо 3 променљиве за бројање истих објеката у боји.

Референце