Zamolila me jedna koleginica da joj pomognem oko jednog zadatka u C jeziku. Moram priznati da sam ja JAAAAKO davno radio u C jeziku i to sam tada zesce brkao C i C++ (mislio sam da je to jedno te isto) i tek sada vidim da to tako ne ide... :)
Nego, da predjem ja na stvar.
Dobila je zadatak da 4 (zadata) algoritma za sortiranje prilagodi tako da se mogu uporediti po:
1. vremenu potrebnom za izvrsavanje
2. broju potrebnih "promena" (swaps)
3. broju potrebnih uporedjivanja
Pri tom, je jos potrebno prosiriti algoritme da mogu da rade i sa nekim drugim tipovima podatak i da mogu da sortiraju i u rikverc.
E sad, znaci ona je dobila ciste algoritme u jednom smeru bez ikakvog merenja a ja sam joj ugradio merenje i prebrojavanje i rikverc sortiranje.
Od vas bi zeleo da mi to proverite da li je OK sto sam uradio, jer ja sam nemam pojma gde da se tacno broje ta poredjenja i menjanje clanova.
Evo sada jedan po jedan algoritam u CODE blokovima (radi lakseg pregleda) a ceo kod je u prilozenom fajlu.
static void bubble_sort(int arr[], int length)
{
int i, swapped;
do
{
swapped = 0;
if (bubble_rev_dir)
{
for (i = 1; i < length; i++)
{
bubble_comp_count++;
if (arr[i - 1] < arr[i])
{
swap(&arr[i - 1], &arr[i]);
bubble_swap_count++;
swapped = 1;
}
}
}
else
{
for (i = 1; i < length; i++)
{
bubble_comp_count++;
if (arr[i - 1] > arr[i])
{
swap(&arr[i - 1], &arr[i]);
bubble_swap_count++;
swapped = 1;
}
}
}
} while (swapped);
}
static void insertion_sort(int arr[], int length) {
int i, j, key;
if (ins_rev_dir)
{
for (i = 1; i < length; i++) {
key = arr[i];
j = i - 1;
ins_comp_count++;
while (j >= 0 && key > arr[j]) {
ins_swap_count++;
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
else
{
for (i = 1; i < length; i++) {
key = arr[i];
j = i - 1;
ins_comp_count++;
while (j >= 0 && key < arr[j]) {
ins_swap_count++;
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}
static void selection_sort(int arr[], int length) {
int i, j, min, max;
if (sel_rev_dir)
{
for (i = 0; i < length - 1; i++) {
max = i;
for (j = i + 1; j < length; j++)
{
sel_comp_count++;
if (arr[j] > arr[max])
max = j;
}
swap(&arr[i], &arr[max]);
sel_swap_count++;
}
}
else
{
for (i = 0; i < length - 1; i++) {
min = i;
for (j = i + 1; j < length; j++)
{
sel_comp_count++;
if (arr[j] < arr[min])
min = j;
}
swap(&arr[i], &arr[min]);
sel_swap_count++;
}
}
}
static void merge(int arr[], int l, int m, int r) {
int *tmp = (int *) malloc(sizeof(int) * (m - l + 1));
int i, j = 0, k = m + 1;
/* kopiere arr[l..m] in ein temporaeres Array */
for (i = l; i <= m; i++)
tmp[j++] = arr[i];
/* vergleiche die Eintraege des temp. Arrays mit den Eintraegen arr[m+1..r] */
i = l;
j = 0;
while (i < k && k <= r)
{
merge_comp_count++;
if (tmp[j] <= arr[k])
{
arr[i++] = tmp[j++];
merge_swap_count++;
}
else
{
arr[i++] = arr[k++];
merge_swap_count++;
}
}
/* kopiere eventuelle vorhandene Eintraege des temp. Arrays nach arr */
while (i < k)
{
arr[i++] = tmp[j++];
merge_swap_count++;
}
free(tmp);
}
/* merge-sort */
static void merge_sorter(int arr[], int l, int r) {
int m = (l + r) / 2;
/* arr[l..r] hat min. zwei Elemente <=> l < r */
if (l < r) {
/* sortiere ersten Teil */
merge_sorter(arr, l, m);
/* sortiere zweiten Teil */
merge_sorter(arr, m + 1, r);
/* Fuege sortierte Teile zusammen */
merge(arr, l, m, r);
}
}
/* Wrapper für mergesorter */
static void merge_sort(int arr[], int n) {
merge_sorter(arr, 0, n - 1);
}
P.S.
Kao sto primecujete, komentari su na nemackom (kojeg ja ne znam) a ona mi je prevela kompletan tekst zadatka i ja vam taj prevod dostavljam u originalu sada, mozda sam ja nesto pogresno shvatio pa mi vi mozete pomoci da ne radim suvisne operacije ako nisu potrebne :)
Prosirite dati program za sortiranje sort.c sa predavanja tako da s njim mozete uporedjivati slozenost i ponasanje algoritama za sortiranje Bubble-Sort Insertion-Sort, Selection-Sort i Merge-Sort za razlicite Array-velicine i Array-tipove
Pri tom prilagodite u data 4 algoritma za sortiranje varijable za mjerenje broja operacija poredjenja i zamjene. Zatim izvedite algoritme za sortiranje za svaki od tri ista niza (Arrays) velicine n, jedan nasumicno izabran , jedan sortiran u rastucem poredku i jedan u opadajucem
Protokoliraj uz to broj operacija poredjenje i zamjene I dajte rezultat u vidu tabele
Velicina niza (array) treba biti data kao parameter komandne linije (Kommandozeilenparametar). Analizirajte tabelarni izdanje za nizove velicine 10, 100 i 10000 I interpretirajte rezultat