c++ ,merge sort ,problem ze zrozumieniem jednego szczegółu

Question

witam ,mam bardzo proste pytanie dotyczące algorytmu merge sort a dokładnie funkcji łączącej dwa posortowanie zbiory (tylko ją podałem) . Problem dokładnie dotyczy sytuacji kiedy musimy przepisać resztę (pozostałe) elementy z tablicy . Teorytycznie trzeba to zrobić wtedy kiedy jeden zbiór jest dłuższy od drugiego lub kiedy pozostały w nim jakieś elemnty . Zanim może dokładnie powiem co mam na myśli podam cały kod funkcji:

 

 void merge(int *tablica ,int start, int srodek, int koniec) {
	int *tab_pom = new int[(koniec-start)];
	int i = start, j = srodek+1, k = 0;

	while(i<=srodek && j<=koniec) {
		if(tablica[i]<tablica[j]) {
			tab_pom[k]=tablica[i];
			i++;
		} else {
			tab_pom[k]=tablica[j];
			j++;
		}
		k++;
	}

	if(i<=srodek) { //czemu tak ? <=
		while(i<=srodek) {
			tab_pom[k]=tablica[i];
			i++;
			k++;
		}
	} else {
		while(j<=koniec) {
			tab_pom[k]=tablica[j];
			j++;
			k++;
		}
	}


for(int i=0; i<=koniec-start; i++) 
	tablica[start+i] = tab_pom[i];
}

a zwłaszcza tego fragmentu :

 

if(i<=srodek) { //tego nie rozumiem : <= a nie <
		while(i<=srodek) { //przepisywanie pozostałych elementow
			tab_pom[k]=tablica[i];
			i++;
			k++;
		}
	} else {

}

czemu występuje tu warunek i<=srodek a nie po prostu i<srodek ,gdy dam tą drugą opcje to algorytm nie działa ok . Przecież przepisujemy wartości tylko wtedy kiedy jeszcze zostały jakieś elementy a nie kiedy "wskaźnik" jest równy końcowemu elementowi . Wiem że pytanie może się wydawać ne jasne ,jak coś to dajcie znać . Z góry dziękuje za pomoc i dotrwanie do końca :)

Answer 1

Skoro podzieliłeś to w ten sposób, że pierwszy zbiór ma zakres:

<start; srodek> a drugi <srodek+1; koniec> to jeśli sprawdzasz pierwszy zbiór musisz też wziąć pod uwagę jego ostatni element czyli srodek.

int i = start, j = srodek+1, k = 0;

Fragment z Twojego kodu ^^^^^^^

Comments

dzięki za odpowiedź, to wiem że środek muszę brać pod uwagę ale nie rozumiem tego że kiedy już wcześniej sprawdzimy cały zbiór pierwszy łącznie ze środkiem ,to czemu sprawdzamy w if-ie że mamy wypisywać resztę tablicy ze zbioru nawet jeżeli J jest  równy środkowi ,to oznacza że doszliśmy już do końca i nie musimy nic przepisywać ale gdy dam tylko znak < to nie działa <= . Przepraszam że tego nadal nie rozumiem ale wybacz mi bo jestem dzisiaj jakoś nie rozgarnięty ;) ,dziękuje za staranie wytłumaczenia mi tego ... 

---

To, że zmienna i jest równa zmiennej srodek nie oznacza, że doszedłeś do samego końca. Popatrz co sie dzieje tutaj w pętli:

while(i<=srodek && j<=koniec) {
        if(tablica[i]<tablica[j]) {
            tab_pom[k]=tablica[i];
            i++;
        } else {
            tab_pom[k]=tablica[j];
            j++;
        }
        k++;
    }

Zmienną i inkrementujesz po poprzedniej iteracji. Dajmy na to, że wykonuje się pierwszy if a do tej pory i wynosiło srodek-1. W takim wypadku po wykonaniu tego if-a zmienna i wskoczy na wartość tą samą co ma srodek. Teraz kolejny obieg pętli i dajmy na to, że wykonuje się tylko else. W tym wypadku i wciąż jest na srodku ale ten element z tablica[i] nie został wstawiony, bo wykonał się else. Teraz załóżmy, że po inkrementacji j równa się koniec+1. Następuje zakończenie pętli ale i, mimo że wskazuje na srodek, nie oznacza że wszystkie elementy zostały rozpatrzone.

---

Aaaa... już rozumiem ,dzięki wielkie za cierpliwość ,daje naj i zamykam temat