przesuwanie elementów tablicy

Question

Witam 

Od niedawna uczę się programowania i jako pierwsze zadanie muszę przenieść ujemne elementy tablicy na jej koniec przy zachowaniu kolejności występowania elementów. Jak dotąd udało mi się posortować tablicę malejąco, jednak nie mam pojęcia w jaki sposób zachować pierwotną kolejność występowania elementów. z góry dziękuję za odpowiedź :)

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>
using namespace std;

int main ()
{
    int minZ, minp, i , j, x;
    int tab[ ] = { -10, 5, 8, -4, 1, 3, 0, -7 };


   for(int i=0; i<8; i++)
{
    cout << setw ( 4 ) << tab [ i ];
cout << endl;

}

 for( i = 0; i < 7; i++ )
  {
    minZ = tab [ i ];
    minp = i;
    for( j = i + 1; j < 8; j++ )
      if( tab [ j ] > minZ )
      {
        minZ = tab [ j ];
        minp = j;
      }
    x = tab [ i ];
    tab[ i ] = tab [ minp ];
    tab [ minp ] = x;
  }
  for( i = 0; i < 8; i++ ) cout  << tab [ i ];
  cout << endl;
  return 0;

}

Answer 1

Tytuł pytania jest mylący: to nie jest sortowanie?

Proponuję przejść od końca tablicy, przenosząc fragment tablicy w przód, a ujemny element na bieżący indeks początku ujemnych elementów.

(Ale nie pytaj o kod.)

Comments

no nie jest sortowanie, bo elementy ujemne ma przenieść kolega na koniec.. a nie jest powiedziane o tym, że ma to być w kolejności posrtowoanej jesli np w tablicy mamy

1, -1,-5,-11,-3,2,6 ... to powinno być -> 1,2,6,-1,-5,-11-,3 ... a to nie jest posortowanie

---

czyli posortowanie tych elementów malejąco jest bez sensu w takim razie?

---

Zależy jakie jest kryterium sortowania, czyli jaką ma postać funkcja porównująca wartości. Przecież można napisać funkcję dla które dwie dowolne nieujemne liczby są równe, dwie ujemne też są równe, a jedynie dodatnie są większe niż ujemne. Sortowanie bąbelkowe będzie ok bo nie zmienia kolejności takich samych elementów.

 

Oczywiście można napisać specjalizowany algorytm do takiego sortowania, nawet będzie prosty:

Dla kolejnych elementów tablicy:

dodatni element zostawiamy na miejscu - nic nie robimy

ujemny przesuwamy na koniec.

 

Przesunięcie na koniec wymaga skopiowania pozostałych elementów 1 do tyłu, no i indeks nie powinien być zwiększany, bo teraz mamy tam nowy element.

Trochę trudno zakończyć pętle - trzeba wykonać dokładnie N razy, a indeks w tablicy może nie dojść do końca. Potrzebne będą dwie zmienne: licznik i indeks.

Answer 2

przenieść ujemne elementy tablicy na jej koniec przy zachowaniu kolejności

Spojrzeć na problem od takiej strony " w tablicy" jako sekwencji liczb, masz na przemian lub w różnej kolejności liczby ujemne i dodanie, masz przesunąc wszystkie "ujemne" zachować ich kolejność występowania na liście nie, wielkość jako sortowanie więc jak na to spojrzeć?
Popatrz na to jak na dwie listy "dodatnią" i ujemną" -> wyciagnij najpierw w odpowiedniej kolejności jakiej występują wszystkie dodatnie ..., a następnie wszystkie ujemne ;] dodjać wszystko na koniec nowej tablicy 

Przykład:  

Tablica1 : [1, -1, -5, -11, -3, 2, 6  ]
Tablica2 : dodanich z tego [1,2,6]  -> i zachowuje kolejność występowania
Tablica ujemnych [-1,-5,-11,-3] 

nowa tablica zachowując kolejność ujemnych na końcu
 jako połączenie tablicy1 i tablicy2

[1,2,6,-1,-5,-11,-3]   - nowa tablica
     |               |
  dodatnie   ujemne w odp. kolejnosci

I tak podejdź do problemu jeśli to jest sednem zadania 

Jak rozwiązać problem, jesli nie możemy tworzyć nowej tablicy ?  Warunek:

Jeśli iterując na bieżąco tablice element trafiasz na pierwszy element, który jest ujemny -> przesuń go na koniec ( i zapisz go, żeby uniknąć przesuwania powtórzeń -> postępuj tak dla wszystkich pozostałych elementów do końca)

Potencjalny problem: możliwość występowania takich samych wartości ;] dlatego nie jest to trywialne rozwiązanie 

Comments

niestety, muszę działać na tej tablicy co już mam, najłatwiej byłoby to zrobić przy użyciu stable_partition, ale nauczyciel powiedział że muszę kombinować z pętlami. Nie mniej dziękuję za odpowiedzi :)