Będę wdzięczny za wszelkie uwagi i spostrzeżenia.
Kod: Zaznacz cały
// Sortowanie Shella
#include <iostream>
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<ilosc_podciagow; 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<n; j=j+krok) // szukanie kandydata na inne minimum w danej podtablicy
{
if(tablica[j]<minimum)
{
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<przedzial; k++) //petla po ilosci podtablic w danym kroku
{
for(int j=k; j<n; j=j+przedzial) // petla w obrebie jednej podtablicy
{
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<n; i++)
{
cout << tablica[i];
if(i<n-1) cout << ", "; // brak przecinka na koncu
}
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<n; i++) // wprowadzanie elementow do tablicy
{
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<ilosc_podciagow; 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<n; i++) // przechodzimy po tablicy
{
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
}
