Sortowanie tablicy jednowymiarowej.

0

Mam za zadanie zrobic projekt:
Dana jest nieuporządkowana tablica jednowymiarowa (wektor) o długości n. Tablica
ta zawiera tylko dwa rodzaje elementów. Posortuj tą tablicę w ten sposób, aby
złożoność obliczeniowa algorytmu była jak najmniejsza. Sortowanie wykonaj za
pomocą przestawiania odpowiednich elementów i bez używania pomocniczej tablicy.
Np. jeśli tablica jest typu całkowitego i zawiera tylko elementy o wartości 0 i 1 ,
{0,1,1,0, .....0,1,0} to po uporządkowaniu jest postaci {0,0,0,........,1,1,1}.

Posiadam takie cos:

unsigned int  ileZer = 0, ileJedynek = 0;
for(int i = 0 ; i < ileElementow ; ++i)
 {
if(tablica[i] == 1)
 {
 ++ileJedynek;
 }
else if(tablica[i] == 0)
 {
 ++ileZer;
 }
 }

int j;
for(j = 0 ; j < ileZer ; ++j)
 {
 tablica[j] = 0;
 }
for( ; j < ileElementow ; ++j)
 {
 tablica[j] = 1;
 }

Moglby mi to ktos sprawdzic? Dobre to jest? W czym mam to zrobic? Gdzie wkleic? jaki program? jaki jezyk?
jestem kompletnie zielony. (posiadam jeszcze jeden kod ale wstawilem krotszy)

1

"Sortowanie wykonaj za pomocą przestawiania odpowiednich elementów", to co podałeś nie spełnia zadania:

for(int i = 0,k=ileElementow-1 ; i<k ;)
  {
   if(!tablica[i]) ++i;
   else if(tablica[k]) --k;
   else
     {
      int tmp=tablica[i];
      tablica[i++]=tablica[k];
      tablica[k--]=tmp;
     }
  }
1

Sprawa wygląda tak, że po posortowaniu na początku masz mieć same zera, a na końcu jedynki. Idziesz po tablicy od początku, i jak jest 0, to idziesz do następnego pola (indeks i jest zwiększany), a jak jest 1, to zaczynasz sprawdzać od końca. Od końca jak jest 1, to idziesz do poprzedzającego pola (indeks k jest zmniejszany). W momencie, jak pod indeksem i jest 1, a pod k jest 0, to musisz to zamienić (blok else). Po zamianie pola mają dobre wartości, więc idziesz dalej: zwiększasz i i zmniejszasz k. Jak i jest już równe, albo większe k, to kończysz i masz posortowane.
Ten algorytm, który wkleiłeś liczy ile jest zer i ile jedynek w tablicy i potem wpisuje na początku tyle zer, a na końcu tyle jedynek. Efekt końcowy ten sam, ale nie spełnia to założenia zadania o przestawianiu.
Ten algorytm, który ja napisałem jest dłuższy, ale zważ na to, że to było jakieś 6 lat temu, więc lepiej użyj tego powyżej.

1 użytkowników online, w tym zalogowanych: 0, gości: 1