wysoce zoptymalizowany algo do sortowania tablicy składającej się tylko z 0s n 1s

Question

Potrzebuję znaleźć wysoce zoptymalizowane algo do sortowania tablicy składającej się tylko z 0s n 1s.

Moja wersja rozwiązania polega na liczeniu nie. zer (powiedzmy x) i jedynek (np. y). Gdy to zrobisz, wstaw x zer w tablicy, a następnie y 1s. To sprawia, że ​​O (n).

Jakieś algo, które działa lepiej niż to? Zadano mi to pytanie w wywiadzie.

Answer 1

Ponieważ trzeba sprawdzić każdy z elementów wejściowych n, nie można poprawić na O(n).

Ponadto, ponieważ twój algorytm wymaga pamięci O(1), nie możesz tego poprawić (nie ma nic asymptotycznie lepszego niż O(1)).

Answer 2

Jeśli sumujesz tablicę, możesz mieć liczbę 1, nieco bardziej wydajną, ale wciąż O (n).

Answer 3

Nie można być bardziej wydajnym niż O (N), ponieważ każdy element musi zostać sprawdzony.

Answer 4

Jakiego rodzaju "macierzy" mówimy? Jeśli policzyliśmy bity w 16-bitowej liczbie całkowitej bez znaku, opracowano kilka algorytmów czasowych O (1): patrz Fast Bit Count Routines.

Jest to jeden z przedstawionych algorytmów; jeden nazywają fajną Hrabiego równolegle:

#define MASK_01010101 (((unsigned int)(-1))/3) 
#define MASK_00110011 (((unsigned int)(-1))/5) 
#define MASK_00001111 (((unsigned int)(-1))/17) 
int bitcount (unsigned int n) { 
    n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101); 
    n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011); 
    n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111); 
    return n % 255 ; 
} 

Answer 5

nie możemy zrobić lepiej niż O (n), ale wygląda na to, co możemy zrobić w jednym przejściu

low = 0; 
high = arr.length - 1; 

while (low < high) { 
    while (arr[low] == 0) { 
     low ++; 
    } 
    while (arr[high] == 1) { 
     high --; 
    } 
    if (low < high) { 
    //swap arr[low], arr[high] 
    } 
} 

Answer 6

To brzmi jak jedno- sortowanie z pręta abacus. Teraz jestem ciekaw kim był twój ankieter.

http://www.dangermouse.net/esoteric/abacussort.html