1. Sortowanie przez wybieranie:
Kod: Zaznacz cały
// Sortowanie przez wybieranie
#include <iostream>
using namespace std;
bool wprowadzenie_danych(int &ilosc_elementow, int tablica[]);
int sortowanie_wybieranie(int tablica[], int n);
int najmniejszy(int tablica[], int n, int start);
void wypisz_rezultat(int tablica[], int n, int zamiany);
void wynik_czastkowy(int tablica[], int n, int od, int dokad);
int main()
{
int tablica[100]={0},n,ile_zamian;
if(wprowadzenie_danych(n, tablica)) // jezeli wprowadzono poprawne dane
{
ile_zamian=sortowanie_wybieranie(tablica,n); // to sortujemy
wypisz_rezultat(tablica,n,ile_zamian); // i wypisujemy posortowana tablice
}
return 0;
}
//***********************************************************************************
// funkcja do wprowadzania danych:
//***********************************************************************************
bool wprowadzenie_danych(int &ilosc_elementow, int tablica[])
{
cout << "Sortowanie przez wybieranie\n\nPodaj ilosc elementow: ";
cin >> ilosc_elementow;
if((ilosc_elementow<1) || (ilosc_elementow>100)) // sprawdzenie poprawnosci danych
{
cout << "Zla ilosc elementow!" << endl;
return false;
}
cout << endl;
for (int i=0; i<ilosc_elementow; i++) // uzupelnienie tablicy
{
cout << "Podaj " << i+1 << " element tablicy: ";
cin >> tablica[i];
}
return true;
}
//*************************************************************************************
// funkcja do wyszukiwania najmniejszego elementu tablicy zaczynajac od elementu start:
//*************************************************************************************
int najmniejszy(int tablica[], int n, int start)
{
int minimum=tablica[start], indeks_minimum=start; // na poczatku zakladamy ze minimalny to pierwszy element
for(int j=start+1; j<n; j++) // szukanie kandydata na inne minimum
{
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:
//****************************************
int sortowanie_wybieranie(int tablica[], int n)
{
int temp,licznik_zamian=0;
for(int k=0; k<n; k++) // wlasciwa petla sortujaca
{
int indeks_najmniejszego=najmniejszy(tablica,n,k); // szukamy najmniejszego elementu w dalszej czesci tablicy
if(tablica[k]>tablica[indeks_najmniejszego]) // jezeli biezacy element tablicy jest wiekszy od minimalnego
{
temp=tablica[k]; //
tablica[k]=tablica[indeks_najmniejszego]; // zamiana
tablica[indeks_najmniejszego]=temp; //
wynik_czastkowy(tablica, n, temp, k); // wypisujemy czastkowe wyniki
licznik_zamian++;
}
}
return licznik_zamian;
}
//*********************************************************
// wypisanie stanu tablicy po kazdym kroku sortowania:
//*********************************************************
void wynik_czastkowy(int tablica[], int n, int od, int dokad)
{
static int licznik_krokow=0;
if(!licznik_krokow)
{
cout << "\n";
}
cout << "Krok " << licznik_krokow+1 << ": [";
licznik_krokow++;
for(int m=0; m<n; m++)
{
cout << tablica[m];
if(m<n-1) cout << ", ";
else cout << "] Zamiana " << od << " ---> " << tablica[dokad] << endl;
}
}
//**********************************************
// wypisanie na ekran posortowanej tablicy:
//**********************************************
void wypisz_rezultat(int tablica[], int n, int zamiany)
{
cout << endl << " Posortowana tablica: [";
for(int m=0; m<n; m++)
{
cout << tablica[m];
if(m<n-1) cout << ", ";
else cout << "]" << endl;
}
cout << " Ilosc zamian: " << zamiany << endl;
}2. Sortowanie przez wstawianie:
Kod: Zaznacz cały
// Sortowanie przez wstawianie
#include <iostream>
using namespace std;
int sortowanie_wstawianie(int tablica[], int ilosc_elementow);
bool wprowadzenie_danych(int tablica[], int &n);
void pokaz_wyniki(int tablica[], int n, int ile_zamian);
void czastkowe_wyniki(int tablica[], int n, int od, int dokad);
double mediana(int tablica[], int n);
int main()
{
int n,tablica[100]={0},ile_zamian;
if(wprowadzenie_danych(tablica,n))
{
ile_zamian=sortowanie_wstawianie(tablica,n);
pokaz_wyniki(tablica,n,ile_zamian);
}
return 0;
}
//***********************************************************
// funkcja sortujaca:
//***********************************************************
int sortowanie_wstawianie(int tablica[], int ilosc_elementow)
{
int temp, licznik_zamian=0; // zmienna pomocnicza do zamiany i licznik zamian
for(int j=1; j<ilosc_elementow; j++) // petla zewnetrzna, elementy wyjmowane ze zbioru elementow nieposortowanych
{
for(int k=0; k<j; k++) // petla wewnetrzna, porownywane elementy zbioru elementow posortowanych
{
if(tablica[j]<tablica[k]) // warunek zamiany, sprawdzamy gdzie upchnac wyjety element
{
temp=tablica[j]; //
tablica[j]=tablica[k]; // zamiana
tablica[k]=temp; //
licznik_zamian++;
czastkowe_wyniki(tablica,ilosc_elementow,j,k);
}
}
}
return licznik_zamian;
}
//*************************************************
// wprowadzenie danych:
//*************************************************
bool wprowadzenie_danych(int tablica[], int &n)
{
cout << "Sortowanie przez wstawianie\n\nPodaj ilosc elementow: ";
cin >> n;
if((n<1) || (n>100)) // dbamy o nieprzekroczenie zakresu tablicy
{
cout << "Zla liczba elementow!\n";
return false;
}
for(int i=0; i<n; i++)
{
cout << "Podaj element nr " << i+1 << ": ";
cin >> tablica[i];
}
return true;
}
//*******************************************
// pokazanie posortowanej tablicy:
//*******************************************
void pokaz_wyniki(int tablica[], int n, int ile_zamian)
{
cout << "\n Posortowana tablica:\n [";
for(int i=0; i<n; i++)
{
cout << tablica[i];
if(i<n-1) cout << ", ";
else cout << "]\n";
}
cout << " Ilosc zamian: " << ile_zamian << "\n";
cout << " Mediana wynosi: " << mediana(tablica,n) << "\n";
}
//*****************************************************
// pokazywanie czastkowych wynikow po kazdej zamianie:
//*****************************************************
void czastkowe_wyniki(int tablica[], int n, int od, int dokad)
{
static int krok;
if(!krok) cout << endl;
cout << " Krok nr " << krok+1 << ": [";
krok++;
for(int i=0; i<n; i++)
{
cout << tablica[i];
if(i<n-1) cout << ", ";
else cout << "] zamiana: " << tablica[od] << " z " << tablica[dokad] << "\n";
}
}
//**************************************************
// wyliczenie mediany:
//**************************************************
double mediana(int tablica[], int n)
{
if(!(n%2)) // dla parzystej liczby elementow
return (tablica[(n/2)-1]+tablica[n/2])/2.;
return tablica[n/2]; // dla nieparzystej liczby elementow
}Pozdrawiam.