Analiza vremena izvršavanja algoritama za pretraživanje i uređivanje kolekcija podataka

Abstract

Uređivanje (sortiranje) je sveprisutno, bilo u svetu računara ili u svakodnevnom životu. To je proces preuređivanja elemenata nekog skupa po određenom poretku i preduslov za efikasno pretraživanje takvog skupa. Pretraživanje je proces koji za cilj ima pronalaženje elemenata u nekoj kolekciji podataka. Najčešće je to traženje elemenata koji sadrži određeni podatak, tj ključ. Postoji više algoritama kako za uređivanje, tako i za pretraživanje, pa se postavlja pitanje koji algoritam je optimalan u zavisnosti od parametara date kolekcije podataka. Kroz rad se posmatraju različite kolekcije podataka, a razlike se ogledaju u više kriterijuma. Najpre prema mestu koje kolekcija zauzima u memoriji: nizovi i liste kao delovi unutrašnje memorije i datoteke kao delovi spoljašnje memorije. Ovakve kolekcije prema nivou uređenosti mogu biti: uređene, inverzno uređene, delimično uređene i nasumične, i mogu biti različite veličine (1000, 100000 i 10000000 elemenata). Kroz aplikacije u C programskom jeziku implementirano je uređivanje i pretraživanje nizova, lista i datoteka, koje poseduju različite kombinacije dve pomenute karakteristike. Koristeći rezultate merenja izvršavanja pomenutih algoritama nad svakim tipom kolekcije, izvršena je analiza, u cilju dobijanja odgovora na pitanje koji algoritam je najbolje koristiti u odnosu na prirodu kolekcije podataka.

In word of computer programming, sorting is present to a large degree, just like in everyday life. It is process of arranging elements of any set by certain order and precondition for efficient search of that set. Searching is process which goal is to find certain element in some data collection. It usually refers to search of element that contain some information (key). There are several sorting and searching algorithms, and the question is which one is optimal to use, depending on parameters of data collection. This paper considers different data collections, and those differences compete in more criterions. Firstly, data collections are divided by place in memory that they held into arrays and lists, as parts of internal memory, and files as parts of external memory. Further, these data collections are divided by level of sort in assorted, inverse assorted, partially assorted and random collections, and can be of different size (1000, 100000 and 10000000 elements). Searching and sorting of arrays, lists and files that have different combinations of mentioned characteristics are implemented in applications, using C programming language. Analysis of algorithms' execution time is done by using the results of searching and sorting measurements, with goal to get answer to question which algorithm is best to use depending on characteristics of data collection.