<< 2. Praktikum | NASM Lehele | 4. Praktikum >>

C – Praktikum3: Järjestusmeetodid, luuresort

Selles praktikumis võtame läbi näiteid järjestumeetoditest ning kirjutame need C-keeles käsitsi. C <stdlib.h> teegis on saadaval ka quicksort implementatsioon nimega qsort, mis on kintsenduste tõttu käsitsi kirjutatud lahendustest kahjuks alati aeglasem.


Ülesanne 1: Mullimeetod

Küsida kasutaja käest sõne kujul tähtede jada ning sorteerida tähed mullimeetodi põhjal.
Sisend: 'Tere mull!'
Väljund: ' !Teellmru'

Antud ülesande jaoks on vaja kasutaja käest sisendi küsimist, mida saab näha eelmise praktikumi lahendustest. Mullimeetodi võiks kirjutada eraldi funktsioonina. Kasutada on järgnev alusprogramm:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int getline(char* buffer, int size); // Prax2 Ülesanne 3

void bubblesort_string(char* str, int len)
{

}

int main()
{
	char input[128];
	printf("Sisesta sõne mida järjestada: ");

	if (getline(input, sizeof input))
	{
		bubblesort_string(input, strlen(input));
		printf("Järjestatud: '%s'\n", input);
	}
	system("pause");
	return 0;
}


Ülesanne 2: Mullimeetod täisarvudega

Sõne järjestamine on lihtsam, kuid üpriski kasutu tegevus. Palju praktilisem on täisarvude sorteerimine. Alusprogrammi jaoks sisestame arvud programmi sisse int massiivina:

#include <stdio.h>
#include <stdlib.h>

void bubblesort(int* list, int len)
{

}

void printarr(char* descr, int* list, int len)
{
	printf("%s = { ", descr);
	for (int i = 0; i < len; ++i)
		printf("%d, ", list[i]);
	printf("}\n");
}

int main()
{
	int list[10] = { 5, 7, 43, 27, 8, 95, 37, 14, 28, 3 };
	int len = sizeof(list) / sizeof(int);

	printarr("unsorted", list, len);
	bubblesort(list, len);
	printarr("  sorted", list, len);

	system("pause");
	return 0;
}


Ülesanne 3: Luuresort

Suuremate sorteerimata massiivide puhul on tihti kasulikum luua histogramm ning selle põhjal massiiv ära sorteerida. Histogrammimeetod (või luuremeetod) muutub teistest sorteerimismeetoditest (nt. quicksort) kiiremaks alles 1000+ elemendi puhul. Alusprogramm on sama mis eelnevas ülesandes.

Esimeseks etapiks on sagedusvektori (ehk siis histogrammi) pikkuse arvutamine. Selleks peame leidma massiivi elementide min ja max väärtused. Sagedusvektori pikkuse saame arvutada tehtega (max - min) + 1. Sagedusvektori saame tekitada dünaamiliselt funktsiooniga malloc(n) mille peame funktsiooni lõpus kindlasti vabastama funktsiooniga free(p). Peale seda on vaja sagedusvektori elemendid väärtustada ning sagedusvektori põhjal välja kirjutada elemendid sorteeritud järjekorras.

#include <stdio.h>
#include <stdlib.h>

void luuresort(int* list, int len)
{

}

void printarr(char* descr, int* list, int len)
{
	printf("%s = { ", descr);
	for (int i = 0; i < len; ++i)
		printf("%d, ", list[i]);
	printf("}\n");
}

int main()
{
	int list[10] = { 5, 7, 43, 27, 8, 95, 37, 14, 28, 3 };
	int len = sizeof(list) / sizeof(int);

	printarr("unsorted", list, len);
	luuresort(list, len);
	printarr("  sorted", list, len);

	system("pause");
	return 0;
}


<< 2. Praktikum | NASM Lehele | 4. Praktikum >>