Sortowanie przez wybieranie - optymalizacja

Witam.

W związku z tym, że od pewnego czasu uczę się języka C (ANSI), z pewnością mój kod nie jest tak efektywny, jaki mógłby być.

Celem tego tematu jest możliwość zaprezentowania moich wypocin oraz prośba użytkowników forum o sugestię dotyczącego jego działania. Głównie interesują mnie komentarze, w których użycie pewnych instrukcji, bądź sztuczek spowoduje szybsze działanie mojego kodu.

Oto dwa algorytmy Sortowania przez wybieranie:

#include <stdio.h>

int main(void)
	{
		int tablica[] = {9, 1, 6, 8, 4, 3, 2, 0};
		int rozmiar = sizeof(tablica) / sizeof(*tablica);
		int x, y, min, temp;
		
		for (x = 0; x < rozmiar - 1; ++x)
			{
				min = x;
				
				for (y = x + 1; y < rozmiar; ++y)
					{
						if (tablica[y] < tablica[min])
							min = y;
					}
					
				if (x < min)
					{
						temp = tablica[x];
						tablica[x] = tablica[min];
						tablica[min] = temp;	
					}
			}
			
		for (x = 0; x < rozmiar; ++x)
			printf("%d ", tablica[x]);
			
		return 0;
	}

Oraz:

#include <stdio.h>

int main(void)
	{
		int tablica[] = {9, 1, 6, 8, 4, 3, 2, 0};
		int rozmiar = sizeof(tablica) / sizeof(*tablica);
		int x, y, ster;

		for (x = 1; x < rozmiar; ++x)
			{
				ster = tablica[x];
				
				for (y = x; y > 0 && tablica[y - 1] > ster; --y)
					{
						tablica[y] = tablica[y - 1];
						tablica[y - 1] = ster;
					}
			}
			
		for (x = 0; x < rozmiar; ++x)
			printf("%d ", tablica[x]);
			
		return 0;
	}

Moje pytanie w tym miejscu brzmi, czy stosowanie warunków złożonych w pętli:

for (y = x; y > 0 && tablica[y - 1] > ster; --y)

... po za zmniejszoną ilością linii kodu (eliminuję całą instrukcję if wraz z jej blokiem), wprowadzają poprawę w jakości działania kodu (np. przy dużej ilości danych)?

Z góry dziękuję za udział w temacie.

Wprowadzają. Mniej instrukcji = mniej czasu. Przy małej ilości danych wejściowych różnicy nie będzie, ale przy większych można będzie już ją odczuć.

Jeżeli ten sam efekt uzyskujesz przy pomocy mniejszej ilości instrukcji - Twój program zyskuje na wydajności :) Poczytaj sobie może o złożoności algorytmów.

Teoria złożoności zajmuje się tylko złożonością asymptotyczną, nie obchodzą ją stałe. Jeśli chciałbyś oszacować wydajność algorytmu to musiałbyś policzyć oczekiwaną liczbę operacji, a i to nie da pełnego obrazu, bo różne algorytmy różnie wykorzystują cache procesora co czasem ma niebagatelny wpływ.

Witam ponownie.

W związku z tym, że można z tego algorytmu wycisnąć jeszcze więcej, prezentuję podejście zwiększające efektywność programu o całe 50%:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ilosc 10

int main(void)
	{
		int tablica[ilosc];
		
		int start = 0;
		int end = ilosc - 1;
		int x, minimum_i, maximum_i, minimum, maximum, temp;
		
		srand(time(NULL));
		
		for (x = 0; x < ilosc; ++x)
			tablica[x] = 1 + rand() % ilosc;			
		
		while (start < end)
			{
				minimum_i = start;
				minimum = tablica[minimum_i];
				
				maximum_i = end;
				maximum = tablica[maximum_i];
				
				for (x = start; x <= end; ++x)
					{
						if (tablica[x] < minimum)
							{
								minimum_i = x;
								minimum = tablica[minimum_i];
							}
							
						else if (tablica[x] > maximum)
							{
								maximum_i = x;
								maximum = tablica[maximum_i];
							}
					}
				
				temp = tablica[end];
				
				if (minimum_i != start)
					{
						tablica[minimum_i] = tablica[start];
						tablica[start] = minimum;
					}
					
				if (maximum_i != end)
					{
						tablica[maximum_i] = temp;
						tablica[end] = maximum;
					}
					
				++start;
				--end;
			}
			
		for (x = 0; x < ilosc; ++x)
			printf("%d ", tablica[x]);
						
		return 0;
	}

Algorytm zaprojektowałem zgodnie z sugestiami znajomego: czyli jednocześnie wyszukuję minimum i maksimum dla danego "wyciku" tablicy, który to z każdą iteracją pomniejsza się z obu stron. Łatwe do zwizualizowania, gorzej z logiką...

Zmierzam do tego, że program średnio 1/20 wyników daje błędy wynik - źle posortowaną tablicę. Domyślam się, że nie przewidziałem jakiejś sytuacji w warunkach, przez co "sypie" się cała dalsza wiązanka.

Bardzo proszę o przyjrzenie się temu rozwiązaniu i zachęcam do pomocy w szukaniu lokalizacji usterki(ek).

Dziękuję!