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
}