Sortowanie bąbelkowe - interesujący problem

Witam.

Napisałem poniższy kod:

#include <stdio.h>
/* Sortowanie bąbelkowe */

int main(void)
	{
		int tablica[] = {4, 2, 5, 1, 7};
		int rozmiar = (sizeof(tablica) / sizeof(*tablica)) - 1;
		int x, y, temp;

		for (x = 0; x <= rozmiar; ++x)
			{
				for (y = 0; y <= rozmiar; ++y)
					{
						if (tablica[y] > tablica[y + 1])
							{
								temp = tablica[y];
								tablica[y] = tablica[y + 1];
								tablica[y + 1] = temp;
							}
					}
			}

		for (x = 0; x <= rozmiar; ++x)
			printf("%d ", tablica[x]);

		return 0;
	}

... który zgodnie z implementacją wypisuje:

1 2 4 5 7

Powyższe rozwiązanie jest niesłychanie nieefektywne, ponieważ porównanie wykonuje się nawet wówczas, gdy tablica jest już uporządkowana. W związku z tym postanowiłem go zoptymalizować, korzystając z dodatkowej zmiennej "logicznej", która pokieruje obrotami pętli.

Tak więc po lekkich modyfikacjach, kod wygląda następująco:

#include <stdio.h>
/* Sortowanie bąbelkowe v2 */

int main(void)
	{
		int tablica[] = {4, 2, 5, 1, 7};
		int rozmiar = (sizeof(tablica) / sizeof(*tablica)) - 1;
		int x, y, temp, zamiana;

		for (x = 0; x <= rozmiar; ++x)
			{
				zamiana = 0;
				
				for (y = 0; y <= rozmiar; ++y)
					{
						if (tablica[y] > tablica[y + 1])
							{
								temp = tablica[y];
								tablica[y] = tablica[y + 1];
								tablica[y + 1] = temp;
								
								zamiana = 1;
							}
					}
					
				if (!zamiana)
					break;
			}

		for (x = 0; x <= rozmiar; ++x)
			printf("%d ", tablica[x]);

		return 0;
	}

Zaskoczył mnie wynik:

1 1 1 1 0

Początkowo zacząłem sam szukać rozwiązania i doszedłem do wniosku (sic!), że jakakolwiek deklaracja nowej zmiennej w pierwszym przeze mnie prezentowanym kodzie, powoduje wypisanie "śmieci" zawartych pod tą zmienną i dalszy fragment właściwego rozwiązania lub tak jak powyżej, ciąg zer i jedynek (wartości zmiennej zmiana).

Jestem w kropce, gdyż pojęcia bladego nie mam jaki związek może mieć "przypadkowa" deklaracja zmiennej na wynik działania algorytmu (wypisania zwartości tablicy, po sortowaniu).

Problem "rozwiązałem", ale stosując inne warunki w konstrukcji pętli zagnieżdżonych for, jednak nadal zastanawia mnie to zjawisko...

Byłym wdzięczny za jakąkolwiek pomoc i przyjrzenie się temu problemowi.

if (tablica[y] > tablica[y + 1])
Nie wyjeżdżasz tutaj przypadkiem poza tablicę?

Gorzej.
sizeof(tablica) wywołane na tablicy zwraca ILOŚĆ elementów a autor sobie to dzieli przez sizeof(int) co daje jakiś dziki wynik. Że później robi takie dziwne odwołanie do tablica[y+1] to inna sprawa

edit: @down mea culpa, nie wiem skąd mi to przyszlo do glowy :)

Shalom napisał(a)

Gorzej.
sizeof(tablica) wywołane na tablicy zwraca ILOŚĆ elementów a autor sobie to dzieli przez sizeof(int) co daje jakiś dziki wynik.

Nie, sizeof(tablica) zwraca rozmiar w bajtach całej tablicy. Dopiero po podzieleniu przez sizeof(int) otrzymujemy liczbę elementów.

Dzięki Panowie za sugestie.

Oto ostateczna wersja, nie sprawiająca już problemów i zdecydowanie lepsza:

#include <stdio.h>
/* Sortowanie bąbelkowe v3 */

int main(void)
	{
		int tablica[] = {4, 2, 5, 1, 7};
		int rozmiar = (sizeof(tablica) / sizeof(*tablica)) - 1;
		int temp, zamiana;
		register int x, y;

		for (x = 0; x <= rozmiar; ++x)
			{
				zamiana = 0;

				for (y = rozmiar; y > x; --y)
					{
						if (tablica[y] < tablica[y - 1])
							{
								temp = tablica[y];
								tablica[y] = tablica[y - 1];
								tablica[y - 1] = temp;
								
								zamiana = 1;
							}
					}

				if (!zamiana)
					break;
			}

		for (x = 0; x <= rozmiar; ++x)
			printf("%d ", tablica[x]);

		return 0;
	}

Sortowanie bąbelkowe to i tak jeden z najgorszych algorytmów do sortowania. Nawet do bardzo małych tablic lepiej nadaje się sortowanie przez wstawianie.