No description available.

Context. Almost all of the modern computers today have a CPU withmultiple cores, providing extra computational power. In the new ageof big data, parallel execution is essential to improve the performanceto an acceptable level. With parallelisation comes new challenges thatneeds to be considered. Objectives. In this work, parallel algorithms are compared and analysedin relation to their sequential counterparts, using the Java platform.Through this, find the potential speedup for multithreading andwhat factors affects the performance. In addition, provide source codefor multithreaded algorithms with proven time complexities. Methods. A literature study was conducted to gain knowledge anddeeper understanding into the aspects of sorting algorithms and thearea of parallel computing. An experiment followed of implementing aset of algorithms from which data could be gather through benchmarkingand testing. The data gathered was studied and analysed with itscorresponding source code to prove the validity of parallelisation. Results. Multithreading does improve performance, with two threadsin average providing a speedup of up to 2x and four threads up to3x. However, the potential speedup is bound to the available physicalthreads of the CPU and dependent of balancing the workload. Conclusions. The importance of workload balancing and using thecorrect number of threads in relation to the problem to be solved,needs to be carefully considered in order to utilize the extra resourcesavailable to its full potential.

Background: Sorting algorithms are an essential part of computer science. With the use of parallelism, these algorithms performance can improve. Objectives: To assess parallel sorting algorithms performance compared with their sequential counterparts and see what contextual factors make a difference in performance. Methods: An experiment was made with quicksort, merge sort, load-balanced parallel merge sort and hyperquicksort. These algorithms executed on Ubuntu 20.10 and Windows 10 Home with three data sets, small (106 integers), medium (5  106 integers) and large (107 integers). Each algorithm executed 1 000 times per data set within each operating system resulting in 6 000 executions per sorting algorithm.  Results: With the data from the executions, it was concluded that hyperquicksort had the fastest execution time. On average load-balanced parallel merge sort had the slowest execution time. The fastest operating system was Ubuntu 20.10, all but one algorithm executed faster on Ubuntu. Conclusions: The results showed that the fastest algorithm was hyperquicksort, but other conclusions also arose. The data set size correlated with both the execution time and speedup for a given parallel sorting algorithm. When the data set size increased, both the execution time and the speedup increased.

À l'origine de cette thèse, nous nous sommes intéressés à l'algorithme de tri TimSort qui est apparu en 2002, alors que la littérature sur le problème du tri était déjà bien dense. Bien qu'il soit utilisé dans de nombreux langages de programmation, les performances de cet algorithme n'avaient jamais été formellement analysées avant nos travaux. L'étude fine de TimSort nous a conduits à enrichir nos modèles théoriques, en y incorporant des caractéristiques modernes de l'architecture des ordinateurs. Nous avons, en particulier, étudié le mécanisme de prédiction de branchement. Grâce à cette analyse théorique, nous avons pu proposer des modifications de certains algorithmes élémentaires (comme l'exponentiation rapide ou la dichotomie) qui utilisent ce principe à leur avantage, améliorant significativement leurs performances lorsqu'ils sont exécutés sur des machines récentes. Enfin, même s'il est courant dans le cadre de l'analyse en moyenne de considérer que les entrées sont uniformément distribuées, cela ne semble pas toujours refléter les distributions auxquelles nous sommes confrontés dans la réalité. Ainsi, une des raisons du choix d'implanter TimSort dans des bibliothèques standard de Java et Python est probablement sa capacité à s'adapter à des entrées partiellement triées. Nous proposons, pour conclure cette thèse, un modèle mathématique de distribution non-uniforme sur les permutations qui favorise l'apparition d'entrées partiellement triées, et nous en donnons une analyse probabiliste détaillée / At first, we were interested in TimSort, a sorting algorithm which was designed in 2002, at a time where it was hard to imagine new results on sorting. Although it is used in many programming languages, the efficiency of this algorithm has not been studied formally before our work. The fine-grain study of TimSort leads us to take into account, in our theoretical models, some modern features of computer architecture. In particular, we propose a study of the mechanisms of branch prediction. This theoretical analysis allows us to design variants of some elementary algorithms (like binary search or exponentiation by squaring) that rely on this feature to achieve better performance on recent computers. Even if uniform distributions are usually considered for the average case analysis of algorithms, it may not be the best framework for studying sorting algorithms. The choice of using TimSort in many programming languages as Java and Python is probably driven by its efficiency on almost-sorted input. To conclude this dissertation, we propose a mathematical model of non-uniform distribution on permutations, for which permutations that are almost sorted are more likely, and provide a detailed probabilistic analysis

Baigiamojo bakalauro darbo tema yra Rikiavimo algoritmų analizė, taigi, jame analizuojami šeši labiausiai naudojami rikiavimo algoritmai, po du iš trijų pagrindinių grupių - išrinkimo, įterpimo ir sukeitimo. Išrinkimo grupėje - Išrinkimo ir Dvigubo išrinkimo algoritmai, įterpimo grupėje - Įterpimo ir Šelo algoritmai, sukeitimo grupėje - Burbulo ir Gnomo algoritmai. Jie lyginami pagal palyginimų ir sukeitim kiekius ir pagal rikiavimo laiką mikrosekundėmis. Kad analizuoti būtų lengviau, naudojant C++ Builder programą buvo sukurtos trys nedidelės apimties programos: pirmoji - duomenų generavimui, antroji - atskirų algoritmų tyrimui ir trečioji - pagrindinė, rikiavimų parametrams tirti. Duomenys generuojami sveikųjų skaičių, slankaus kablelio skaičių ir raidyno pavidalu. Duomenys generuojami pagal reikšmių kiekį ir intervalą, iš kurio mes norime gauti reikšmes. Atskirų algoritmų tyrimo programa išrašo duomenų eilutes po kiekvieno sukeitimo, taigi, mes galime stebėti atskirų algoritmų darbą ir matyti, kuo jie skiriasi. Ir pagrindinė programa rikiuoja duomenis skirtingais algoritmais ir gražina tik palyginimų ir sukeitimų kiekius ir rikiavimo laiką. Pagal šiuos rezultatus buvo sudarytos lentelės ir diagramos algoritmų palyginimui. / The theme of Bachelor Final Work is Analysis of Sorting Algorithms, so I analyse six mostly used algorithms, by two of them from three main groups – selection, insertion, and exchange. In selection group – Selection Sort and Double Selection Sort, in insertion group – Insertion Sort and Shell Sort, in exchange group – Bubble Sort and Gnome Sort. I made comparison of them by the amount of compares, swaps and sorting time in mikroseconds. For making my analysis easier, using C++ Builder program, I made three small programs: one for data generation, the other for the examination of separate algoritms, and the main program which returns sorting parameters. The data are generating in Int type (Integer number), Float type (Floating-point number) and Char type (alphabet). The data are generating by the number of values, for the numbers generating we can appoint the range and so we can make files with different levels of data such like almost sorted row or, on the contrary, very scattered. The program for separate algorythms examination sorts data and after every swap writes the row of values in text box, so we can follow the work of separates algorithms and we can see how different they are. And the main program sorts values by data type and returns just amount of compares, swaps and sorting time. By these results I made tables and diagrams for algoritms comparisons.

Rūšiavimo algoritmų sudėtingumo analizių galima atrasti be problemų, todėl pagrindinė šio darbo idėja buvo sukurti rūšiavimo algoritmų vizualizavimą. Šiame darbe buvo sukurtas trijų paprastųjų rūšiavimo algoritmų (įterpimo, burbulo ir išrinkimo), bei dviejų greitųjų rūšiavimo algoritmų (Šelo ir sąlajos) vizualizavimas. Darbe taip pat galima skaičiuoti rūšiavimo algoritmų rūšiuojamą laiką. / There is a lot of complexity analysis of sorting algorithms can be found without problems, so the main idea of this work was to create a visualization of sorting algorithms. This work was created three simple sorting algorithms (insertion sort, bubble sort and selection sort), and two high-speed sorting algorithms (Shell sort and merge sort) visualization. This program is capable of calculating sorting time of sorting algorithm for further sorting algorithm complexity analysis.

Στη διπλωματική αυτή, παρουσιάζεται μια ρομποτική κατασκευή για την επίδειξη αλγορίθμων ταξινόμησης, με χρήση του εκπαιδευτικού ρομπότ της Lego, το LEGO Mindstorm NXT. Σκοπός αυτής τη επίδειξης είναι να βοηθήσει τους φοιτητές που την παρακολουθούν να κατανοήσουν καλύτερα τους τρόπους εκτέλεσης των αλγορίθμων ταξινόμησης. Το εκπαιδευτικό ρομπότ αυτό αποτελεί εμπορικό προϊόν, μη έχοντας όμως συγκεκριμένη μορφή. Αποτελείται από πολλά πλαστικά μέρη, τα οποία θυμίζουν τα κλασικά τουβλάκια της LEGO αλλά και πολλά άλλα όπως αισθητήρες, κινητήρες, γρανάζια και ρόδες. Με τη χρήση αυτών, κατασκευάστηκε ένα όχημα, το οποίο μπορεί να κινείται μόνο αριστερά-δεξιά, στο οποίο και προσαρτάται ένας αισθητήρας φωτεινότητας. Διαθέτει ακόμη έναν βραχίονα που μπορεί να κινηθεί πάνω-κάτω και στον οποίο προσαρτάται ένας αισθητήρας χρώματος. Οι αριθμοί που καλείται το ρομπότ να ταξινομήσει είναι στην ουσία κύβοι. Οι κύβοι αυτοί, είναι χρωματισμένοι στο επάνω μέρος τους με κάποιο χρώμα ενώ στην πρόσοψή τους έχει εκτυπωθεί ένας αριθμός. Το ρομπότ αναλαμβάνει να αναγνωρίσει με τον αισθητήρα χρώματος το χρώμα του κάθε κύβου και να το ταυτοποιήσει με τον αριθμό στο οποίο αντιστοιχίζεται το χρώμα αυτό. Τον αριθμό δηλαδή που είναι εκτυπωμένος στη πρόσοψη. Για την πλοήγηση του οχήματος εφαρμόζεται μια παραλλαγή της τοπολογικής πλοήγησης. Για την αντιστοίχιση των χρωμάτων με τους αριθμούς χρησιμοποιείται δειγματοληψία χρώματος και στη συνέχεια χρησιμοποιείται 1-προς-1 αντιστοίχιση χρώματος και κατάλληλου αριθμού. Τέλος, οι αλγόριθμοι ταξινόμησης που υλοποιήθηκαν ήταν οι Bubble Sort, Insertion Sort, Heap Sort, Quick Sort. Η επίδειξη των αλγορίθμων γίνεται χρησιμοποιώντας φυσικά τον βραχίονα ο οποίος μετακινεί κατάλληλα τους κύβους. Όμως για την καλλίτερη κατανόηση και για να βοηθηθούν όσοι παρακολουθούν την επίδειξη, παράλληλα της ταξινόμησης με τον βραχίονα, γίνεται χρήση κατάλληλων ηχητικών αλλά και γραπτών μηνυμάτων τα οποία προβάλλονται στην οθόνη που διαθέτει το ΝΧΤ. Τα όσα προβάλλονται στην οθόνη, χρησιμοποιώντας το προγραμματιστικό περιβάλλον Bricx, είναι δυνατόν να προβληθούν σε οθόνη υπολογιστή ή ακόμα και μέσω προβολέα εφόσον ο τελευταίος συνδέεται με υπολογιστή. Τέλος, θεωρούμε ότι το σύστημα που αναπτύχθηκε αποτελεί ένα πολύ καλό εργαλείο που μπορεί να βοηθήσει τον διδάσκοντα στη διδασκαλία των αλγορίθμων ταξινόμησης. Οι φοιτητές μπορούν μέσω της οπτικοποίησης να κατανοήσουν ευκολότερα και γρηγορότερα τους αλγορίθμους. Μελλοντικά ίσως προστεθούν και άλλοι αλγόριθμοι ταξινόμησης, να αναπτυχθεί μια γραφική διεπαφή που θα είναι ανεξάρτητη του Bricx για να προβάλλονται σε κάποια οθόνη τα όσα προβάλλονται χρησιμοποιώντας το Bricx, να χρησιμοποιηθούν διαφορετικοί τρόποι αναγνώρισης αριθμών όπως χρήση αλγορίθμων μορφολογικής επεξεργασίας και τέλος η βηματική ταξινόμηση των αλγορίθμων από κάποιον χειριστή. / --

This MSc Thesis was performed during a study stay at the Hochschule Furtwangen University, Furtwangen, Germany. This Master Project provides a theoretical background for understanding financial market principles. It focuses on foreign exchange market, where it gives a description of fundamentals and price analysis. Further, it covers principles of high-frequency trading including strategy, development and cost. FIX protocol is the financial market communication protocol and is discussed in detail. The core part of Master Project are sorting algorithms, these are covered on theoretical and practical level. Aggregator design includes implementation environment, specification and individual parts of aggregator application represented as objects. Implementation overview can be found in last Chapter.

Background: Computers use sorting algorithms to prepare data for search or insert operations, these operations can be a bottleneck for performance. Objectives: To evaluate sorting algorithms performances when existing in different implementation environments like different languages, sorting in different data types and in different sizes. Methods: By performing an experiment with Java, C++, Python and Javascript on three different sizes and three different data types performance of sorting algorithms will be evaluated. The sorting algorithms used in this study are Insertion sort, Selection sort, Quick sort and Merge sort. They were all tested on each size on each language three times. Results: In the end 432 tests were performed and the results found that Java had best execution time on all four algorithms with quick sort as the best algorithm. The best data type could not be pinpointed down since they acted differently on different algorithms. Quicksort was determined to be the fastest algorithm in the literature review which focused fastest algorithm Conclusions: Together with the results of the experiment and literature review quicksort is the fastest sorting algorithm. The best performing implementation language was Java. For data types one type could not be determined the best only the worse could be decided, floats performed the worse of all three types.

Java applications consume energy, which has become a controversial topic since it limits the number of machines and increases the cost of data centers. This paper investigates the potential relationship between energy consumption and some quality attributes for Java Collections and Sorting algorithms in order to raise awareness about using energy-efficient programs. In addition, introduce to the developers the most and least efficient Java Collection and Sorting algorithm in terms of energy consumption, memory, and CPU usage. This was achieved by conducting a controlled experiment to measure these terms. The data obtained for the results was used to acquire Statistical and Efficiency Analysis to answer the research questions.