Sorting Algorithms PDF
Document Details
Uploaded by ProgressiveRelativity
STI College
Tags
Summary
This handout provides an overview of sorting algorithms, such as Bubble Sort, Selection Sort, Insertion Sort, and Merge Sort, and explains their underlying principles and methods. It includes examples and visual representations of how these algorithms work with different sets of data. The handout also highlights the similarities and differences between various approaches to sorting algorithms, such as using Java or Python's integrated libraries for sorting tasks.
Full Transcript
IT1815 Sorting Algorithms Intervals: N/2 = 6/2 = 3 N/4 = 6/4 = 1 Fundamentals...
IT1815 Sorting Algorithms Intervals: N/2 = 6/2 = 3 N/4 = 6/4 = 1 Fundamentals 31 12 25 8 33 17 Sorting is the process of arranging data in a specific order. 31 8 8 31 The most common sorting algorithms are as follows: 12 33 12 33 o Bubble Sort – Every pair of adjacent items is compared and 25 17 17 25 items are swapped until they are in order. 8 12 17 31 33 25 8 12 17 31 33 25 31 12 25 8 12 31 25 8 8 12 17 31 33 25 8 12 17 31 33 25 12 31 25 8 12 25 31 8 8 12 17 31 33 25 8 12 17 31 33 25 12 25 31 8 12 25 8 31 8 12 17 31 33 25 8 12 17 31 33 25 12 25 8 31 12 25 8 31 8 12 17 31 33 25 8 12 17 31 25 33 12 25 8 31 12 8 25 31 8 12 17 31 25 33 12 8 25 31 12 8 25 31 8 12 17 25 31 33 12 8 25 31 8 12 25 31 o Merge Sort – The list is divided into sorted sub-lists then o Selection Sort – The smallest unsorted item is chosen and combined into a single sorted list. then swapped with the item in the next position to be filled. 31 12 25 8 33 17 40 42 31 12 25 8 33 17 8 12 25 31 33 17 8 12 25 31 33 17 8 12 25 31 33 17 31 12 25 8 33 17 40 42 8 12 25 31 33 17 8 12 17 31 33 25 8 12 17 31 33 25 8 12 17 25 33 31 31 12 25 8 33 17 40 42 8 12 17 25 33 31 8 12 17 25 31 33 o Insertion Sort – The comparison applies to adjacent items and 12 31 8 25 17 33 40 42 previously scanned items. 31 12 25 8 17 12 31 25 8 17 8 12 25 31 17 33 40 42 12 31 25 8 17 12 25 31 8 17 12 25 31 8 17 12 25 8 31 17 8 12 17 25 31 33 40 42 12 25 8 31 17 12 8 25 31 17 Easiest way to sort in Java and Python: __ 8 12 25 31 17 Java: ArrayList values = new ArrayList(); 8 12 25 31 17 8 12 25 17 31 Collections.addAll(values, 1, 3, 2); Collections.sort(values); 8 12 25 17 31 Python: values = [1, 3, 2] 8 12 17 25 31 values.sort() o Shell Sort – Items at a specific interval are sorted. The interval between the items is gradually decreasing based on a sequence. Reference: The most common sequence is the original sequence by Donald Koffman, E. & Wolfgang, P. (2016). Data structures: Abstraction and design using Java. Shell, the inventor of this algorithm, which is N/2, N/4, …, 1, where Hoboken: John Wiley & Sons, Inc. Oracle Docs (n.d.). Citing sources. Retrieved from N is the number of items. Insertion sort is applied when the interval https://docs.oracle.com/javase/8/docs/api/java/util/package-summary.html reaches 1. 10 Handout 1 *Property of STI [email protected] Page 1 of 1
