[C++] Sortowanie Shella


(Kanaliaon) #1

Witam, napisałem program na sortowanie metoda Shella, czyli na dzielenie tablicy na mniejsze podtablice, przesortowaniu ich poprzez wybieranie (selection sort) i przy dążeniu z liczbą podtablic do 1, dążeniu do posortowania całej tablicy. Program liczy medianę i dominantę.

Będę wdzięczny za wszelkie uwagi i spostrzeżenia.

// Sortowanie Shella


#include 


using namespace std;


int najmniejszy(int tablica[], int n, int start, int krok);

void shell(int tablica[], int n, int przedzial);

void wyniki_czastkowe(int tablica[], int n, int ktory_krok);

bool wprowadzanie_danych(int tablica[], int &n, int &ilosc_podciagow, int podciagi[]);

bool dystrybuanta(int tablica[], int n, int &dystry);

double mediana(int tablica[], int n);


int main()

{

	int tablica[100]={0},podciagi[100]={0},n,ilosc_podciagow,dystry;

	if(wprowadzanie_danych(tablica,n,ilosc_podciagow,podciagi)) //jesli wprowadzono wlasciwe dane

	{

		for(int k=0; k
		{

			shell(tablica,n,podciagi[k]); // to sortujemy

			wyniki_czastkowe(tablica,n,k); // i pokazujemy po kazdym kroku wyniki czastkowe

		}

		if(dystrybuanta(tablica,n,dystry)) cout << "\n Dystrybuanta wynosi: " << dystry << "\n"; // jak jest dystrybuanta to pokazujemy

		else cout << "\n Nie ma dystrybuanty!\n"; // a jak nie ma to nie :P

		cout << " Mediana wynosi: " << mediana(tablica,n) << "\n\n"; // pokazanie mediany

	}

	return 0;

}


// ***********************************************************

// poszukiwanie minimalnego elementu z danej podtablicy:

// ***********************************************************

int najmniejszy(int tablica[], int n, int start, int krok)  

{

	int minimum=tablica[start], indeks_minimum=start; // na poczatku zakladamy ze minimalny to pierwszy element podtablicy

	for(int j=start+krok; j
	{

		if(tablica[j]
		{

			minimum=tablica[j]; // jest minimum

			indeks_minimum=j; // i jego indeks ktory zwracamy do funkcji sortujacej

		}

	}

	return indeks_minimum;

}


// ********************************************************

// wlasciwa funkcja sortujaca:

// ********************************************************

void shell(int tablica[], int n, int przedzial)

{

	for(int k=0; k
		{

		for(int j=k; j
		{

			int temp,indeks_najmniejszego=najmniejszy(tablica,n,j,przedzial);

			if(tablica[j]>tablica[indeks_najmniejszego]) // wykorzystujemy sortowanie przez wybieranie do sortowania podtablic

			{

				temp=tablica[j]; //

				tablica[j]=tablica[indeks_najmniejszego]; // zamiana

				tablica[indeks_najmniejszego]=temp; //

			}

		}

	}

}


// *****************************************************************

// pokazanie wynikow czastkowych po kazdym kroku:

// *****************************************************************

void wyniki_czastkowe(int tablica[], int n, int ktory_krok)

{

	if (!ktory_krok) cout << "\n"; //odstep przed pokazaniem pierwszego kroku

	cout << " Krok nr " << ktory_krok+1 << ": [";

	for(int i=0; i
	{

		cout << tablica[i];

		if(i
	}

	cout << "]\n";

}


// *************************************************************

// funkcja do wprowadzania danych:

// *************************************************************

bool wprowadzanie_danych(int tablica[], int &n, int &ilosc_podciagow, int podciagi[])

{

	cout << "Sortowanie Shella\n\nPodaj liczbe elementow: ";

	cin >> n; // liczba elementow do posortowania

	if((n<1) || (n>100)) // zabezpieczenie przed przekroczeniem zakresu

	{

		cout << "\nZla liczba elementow!\n";

		return false;

	}

	for (int i=0; i
	{

		if(!i) cout << "\n";

		cout << "Podaj element nr " << i+1 << ": ";

		cin >> tablica[i];

	}

	cout << "\nPodaj ilosc podciagow: ";

	cin >> ilosc_podciagow; // ilosc podtablic (podciagow)

	for(int j=0; j
	{

		cout << "Podaj odstep podciagu " << j+1 << ": "; // i ich odstepy (np. 5 - podtablica bedzie skladala sie z co piatego elementu)

		cin >> podciagi[j];

	}

	return true;

}


// ***********************************************************

// wyznaczenie dystrybuanty: 

// ***********************************************************

bool dystrybuanta(int tablica[], int n, int &dystry) // zwracamy dystrybuante przez referencje

{

	int licznik=0, stary_licznik=0;

	for(int i=0; i
	{

		if(tablica[i+1]==tablica[i]) // i patrzymy czy sie cos powtarza

		{

			licznik++; // jesli tak to zwiekszamy licznik

			if(licznik>stary_licznik) // ale patrzymy czy jest wiekszy od licznika z poprzedniego obiegu petli

			dystry=tablica[i]; // jesli tak, to mamy dystrybuante

		}

		else

		{

			licznik=0; // albo nie :(

		}

		if((licznik) && licznik>stary_licznik) stary_licznik=licznik; // ogolny licznik powtorzen elementow 

	}

	if(stary_licznik) return true; // jak jest dystrybuanta to zwracamy true a jak nie ma to false

	else return false;

} 


// **************************************************

// wyliczenie mediany:

// **************************************************

double mediana(int tablica[], int n)

{

	if(!(n%2)) // jezeli n parzyste

		return (tablica[(n/2)-1]+tablica[n/2])/2.;

	return tablica[n/2]; // jezeli n nieparzyste

}

([alex]) #2

zmień warunek z:

if(tablica[j]

na:

if(j==start+krok || tablica[j]

wtedy nie trzeba zakładać że minimalny to pierwszy. Może w tym kodzie nigdy tak nie będzie ale w innych przypadkach może się okazać że tablica jest pusta.

Dystrybuanta liczy się niezbyt poprawnie, na ile pamiętam to dystrybuantą jest najczęściej powtarzający się element. U ciebie zwraca największy powtarzający się. Poza tym w takiej postaci algorytmu tablica może zawierać nie do końca posortowane dane, więc przedstawiony algorytm obliczania dystrybuanty jest do ... powiedzmy do niczego.

:lol:


(Kanaliaon) #3

Dystrybuantę testowałem na ciągu podobnym do 1 4 4 5 5 5 5 5 7 7 7 8 8 8 8 i pokazało 5, poprawnie. Najczęściej powtarzająca się wartość.


([alex]) #4

No tak masz racje zmylił mnie zapis:

if(licznik>stary_licznik)dystry=tablica[i]; [/code]żadnych klamerek, żadnych wcięć ...
[code]for(int i=0; i
...

   if(tablica[i+1]==...Wyłazisz poza tablicę.

(Kanaliaon) #5

[alex], faktycznie wychodzę poza tablicę, dzieki, wystarczy dać w tym forze i

Jeszcze jakieś uwagi, sugestie?