#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#define N 10000000 //sta³a definiuj¹ca rozmiar tablic
int tablica[N];
int tablica1[N];
long int swap1, swap2; //zmienne do zliczania operacji swap
long int porownania1, porownania2;
void wypelnij_tablice (int tablica[], int liczba_elementow) //funkcja wype³niaj¹ca tablice liczbami losowymi
{
int i;
srand(time(NULL));
for(i=0; i<liczba_elementow; i++)
tablica[i]=-1000+rand()%2000;
}
void wyswietl_tablice (int tablica[], int liczba_elementow) //funkcja wyswietla tablice
{
int i;
for(i=0; i<liczba_elementow; i++)
printf("%4d", tablica[i]);
}
void swap(int *first, int *second) //funkcja zamieniaj¹ca 2 elementy miejscami
{
int tmp = *first;
*first = *second;
*second = tmp;
}
void sortowanie_przez_wybieranie(int tablica[], int liczba_elementow) //funkcja sortujaca przez proste wybieranie
{
int i,j;
for(i=0; i<liczba_elementow-1; i++)
{
int min = i;
for(j=i+1; j<liczba_elementow; j++) {
porownania1+=1;
if(tablica[min]>tablica[j])
min = j;
}
if(min!=i) {
swap(&tablica[min],&tablica[i]);
swap1=swap1+1;
}
}
}
void naprawkopiec (int *tab, int rozmiar, int i)
{
int wiekszy;
int l=2*i, p=(2*i)+1;
if (l<rozmiar && tab[l]>tab[i]) {
wiekszy=l;
porownania2+=1;
}
else {
wiekszy=i;
porownania2+=1;
}
if (p<rozmiar && tab[p]>tab[wiekszy]){
wiekszy=p;
porownania2+=1;
}
if (wiekszy!=i)
{
swap(&tab[wiekszy], &tab[i]);
swap2=swap2+1;
naprawkopiec(tab,rozmiar,wiekszy);
}
}
void stworzkopiec(int *tab, int rozmiar)
{
int i;
for (i=rozmiar/2; i>=0; --i)
naprawkopiec(tab,rozmiar, i);
}
void sortowanie_przez_kopcowanie(int *tab, int rozmiar) //funkcja sortujaca przez kopcowanie
{
int i;
stworzkopiec(tab, rozmiar);
for (i=rozmiar-1; i>=1; --i)
{
swap2=swap2+1;
swap(&tab[0], &tab[i]);
--rozmiar;
naprawkopiec(tab,i,0);
}
}
int main()
{
int liczba_elementow, i;
printf("Podaj rozmiar tablicy:");
scanf("%d", &liczba_elementow);
wypelnij_tablice(tablica, liczba_elementow);
for (i=0; i<liczba_elementow; i++)
tablica1[i]=tablica[i];
int start = GetTickCount();
sortowanie_przez_wybieranie(tablica, liczba_elementow);
int end = GetTickCount();
printf("\nSortowanie zajelo Ci %d ms.\n", end-start);
int start1 = GetTickCount();
sortowanie_przez_kopcowanie(tablica1, liczba_elementow);
int end1 = GetTickCount();
printf("\n\nZajelo Ci to %d ms.\n\n", end1-start1);
printf("Swap 1: (przez wybor): %ld\n", swap1);
printf("Porownania: (przez wybor): %ld\n", porownania1);
printf("Swap 2: (przez kopcowanie) %ld\n", swap2);
printf("Porownania: (przez kopcowanie): %ld\n", porownania2);
return 0;
}
Witam. Mam taki oto kod. Muszę porównać sortowanie przez wstawianie z sortowaniem kopcowym. Algorytmy sortują dobrze. Moje pytanie jest o liczniki. Czy zliczają one dobrze liczbę porównań i liczbę zamian? Mam wątpliwości co do licznika porównań w sortowaniu kopcowym. Może ktoś rzucić okiem czy jest dobrze? :)