Analiza vremena izvršavanja algoritama za pretraživanje i uređivanje kolekcija podataka
Analysis of searching and sorting data collections algorithms' execution time
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 jez...iku 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 sor...ting 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.
Keywords:
uređivanje / pretraživanje / merenje vremena / komparativna analiza / kolekcija podataka / algoritam / time measurement / sorting / searching / data collection / comparative analysis / algorithmSource:
Info M, 2016, 15, 60, 36-42Publisher:
- Univerzitet u Beogradu - Fakultet organizacionih nauka, Beograd
Collections
Institution/Community
Fakultet organizacionih naukaTY - JOUR AU - Matijević, Selena AU - Lazarević, Saša PY - 2016 UR - https://rfos.fon.bg.ac.rs/handle/123456789/1520 AB - 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. AB - 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. PB - Univerzitet u Beogradu - Fakultet organizacionih nauka, Beograd T2 - Info M T1 - Analiza vremena izvršavanja algoritama za pretraživanje i uređivanje kolekcija podataka T1 - Analysis of searching and sorting data collections algorithms' execution time EP - 42 IS - 60 SP - 36 VL - 15 UR - conv_739 ER -
@article{ author = "Matijević, Selena and Lazarević, Saša", year = "2016", 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.", publisher = "Univerzitet u Beogradu - Fakultet organizacionih nauka, Beograd", journal = "Info M", title = "Analiza vremena izvršavanja algoritama za pretraživanje i uređivanje kolekcija podataka, Analysis of searching and sorting data collections algorithms' execution time", pages = "42-36", number = "60", volume = "15", url = "conv_739" }
Matijević, S.,& Lazarević, S.. (2016). Analiza vremena izvršavanja algoritama za pretraživanje i uređivanje kolekcija podataka. in Info M Univerzitet u Beogradu - Fakultet organizacionih nauka, Beograd., 15(60), 36-42. conv_739
Matijević S, Lazarević S. Analiza vremena izvršavanja algoritama za pretraživanje i uređivanje kolekcija podataka. in Info M. 2016;15(60):36-42. conv_739 .
Matijević, Selena, Lazarević, Saša, "Analiza vremena izvršavanja algoritama za pretraživanje i uređivanje kolekcija podataka" in Info M, 15, no. 60 (2016):36-42, conv_739 .