Algorithms and Data Structures in an Object-Oriented Framework (“ADSOOF”)

Code for “Sorting and Efficiency” section

Examples of code for searching

• Find1.java Demonstrates a static method which uses linear search to return a boolean saying whether a particular integer occurs in an array of integers. The support code generates an array of random integers to test the method with.
• Find2.java As Find1.java, but the array is not displayed (to allow the method to be tested on arrays too big to be displayed).
• Find3.java Demonstrates a static method which uses linear search to return a boolean saying whether a particular integer occurs in an array of integers. The code for the method assumes it is in numerically ascending order. The support code generates an array of random integers, then sorts the array (using Java's built-in sort method on arrays) to test the method with.
• Find4.java As Find3.java, but the array is not displayed.
• Find5.java Demonstrates a static method which uses binary search (implemented using recursion) to return a boolean saying whether a particular integer occurs in an ordered array of integers.
• Find6.java As Find5.java, but the array is not displayed.
• Find7.java Demonstrates a static method which uses binary search (implemented using iteration) to return a boolean saying whether a particular integer occurs in an ordered array of integers.
• Find8.java As Find7.java, but the array is not displayed.
• Find9.java Shows linear search on an unordered array implemented using recursion.
• Find10.java As Find9.java, but the array is not displayed.

Examples of code for sorting: insertion sort algorithm

• InsertSort1.java Demonstrates a static method which sorts an arrayList of integers constructively using the insertion sort algorithm. Requires the integers to be typed in.
• InsertSort1a.java As InsertSort1.java, but the sort code is all in one method rather than with a separate insert method.
• InsertSort2.java As InsertSort1.java, but the integers are generated randomly and displayed.
• InsertSort2a.java As InsertSort2.java, but the sort code is all in one method rather than with a separate insert method.
• InsertSort3.java As InsertSort1.java, but the integers are generated randomly, and not displayed. The time elapsed between start and finish of the sorting is displayed.
• InsertSort3a.java As InsertSort3.java, but the sort code is all in one method rather than with a separate insert method.
• InsertSort4.java Demonstrates a static method which sorts an ArrayList<Integer> destructively (in place) using the insertion sort algorithm. The integers are generated randomly and displayed.
• InsertSort5.java As InsertSort4.java, but the integers are generated randomly, and not displayed. The time elapsed between start and finish of the sorting is displayed.
• InsertSort6.java Demonstrates a static method which sorts an array of integers destructively (in place) using the insertion sort algorithm. Requires the integers to be typed in.
• InsertSort7.java As InsertSort6.java, but the integers are generated randomly, and not displayed. The time elapsed between start and finish of the sorting is displayed.

Examples of code for sorting: selection sort algorithm

• SelSort1.java Demonstrates a static method which sorts an array of integers destructively (in place) using the selection sort algorithm. Requires the integers to be typed in.
• SelSort1a.java The same algorithm as in SelSort1.java, but broken down into one less method.
• SelSort2.java Demonstrates a static method which sorts an array of strings destructively (in place) using the selection sort algorithm, putting them in alphabetic order. Requires the strings to be typed in.
• SelSort3.java As SelSort1.java, but the integers are generated randomly and displayed.
• SelSort4.java As SelSort2.java, but the strings are generated randomly and displayed.
• SelSort5.java As SelSort1.java, but the integers are generated randomly, and not displayed. The time elapsed between start and finish of the sorting is displayed.
• SelSort6.java As SelSort2.java, but the Strings are generated randomly, and not displayed. The time elapsed between start and finish of the sorting is displayed.
• SelSort7.java Demonstrates a static method which sorts an arrayList of integers destructively (in place) using the insertion sort algorithm. The integers are generated randomly and displayed.
• SelSort8.java As SelSort7.java, but the integers are not displayed. The time elapsed between start and finish of the sorting is displayed.

Examples of code for sorting: bubble sort algorithm

• BubbleSort1.java Demonstrates a static method which sorts an ArrayList<Integer> destructively (in place) using the bubble sort algorithm. Requires the integers to be typed in.
• BubbleSort2.java Demonstrates a static method which sorts an array of strings destructively (in place) using the bubble sort algorithm, putting them in alphabetic order. Requires the strings to be typed in.
• BubbleSort3.java As BubbleSort1.java, but the integers are generated randomly and displayed.
• BubbleSort4.java As BubbleSort2.java, but the strings are generated randomly and displayed.
• BubbleSort5.java As BubbleSort1.java, but the integers are generated randomly, and not displayed. The time elapsed between start and finish of the sorting is displayed.

Examples of code for sorting: quick sort algorithm

• QuickSort1.java Demonstrates a static method which sorts an ArrayList<Integer> constructively using the quicksort algorithm. The integers are generated randomly and displayed.
• QuickSort1a.java As QuickSort1.java, but the integers are not generated randomly, they have to be typed in.
• QuickSort2.java As QuickSort1.java, but the integers are not displayed. The time elapsed between start and finish of the sorting is displayed.
• QuickSort3.java As QuickSort1.java, but works with arrays rather than arrayLists.
• QuickSort3a.java A modified form of QuickSort3.java which avoids checking elements against a pivot twice.
• QuickSort4.java As QuickSort3.java, but the integers are not displayed, and the time elapsed between start and finish of the sorting is displayed.
• QuickSort4a.java As QuickSort3a.java, but the integers are not displayed, and the time elapsed between start and finish of the sorting is displayed.
• QuickSort5.java Demonstrates a static method which sorts an array of integers destructively using the quicksort algorithm implemented with temporary arrays. The integers are generated randomly and displayed.
• QuickSort6.java As QuickSort5.java, but the integers are not displayed. The time elapsed between start and finish of the sorting is displayed.
• QuickSort7.java Demonstrates a static method which sorts an array of integers destructively. It uses the quicksort algorithm implemented fully in place (that is, it makes no use of extra temporary arrays). The integers are generated randomly and displayed.
• QuickSort8.java As QuickSort7.java, but the integers are not displayed. The time elapsed between start and finish of the sorting is displayed.
• QuickSort9.java As QuickSort7.java, but works on arrayLists rather than arrays.
• QuickSort10.java As QuickSort8.java, but works on arrayLists rather than arrays.
• QuickSort11.java Shows the quicksort algorithm on arrays implemented purely iteratively, with the recursion replaced by a stack of start-to-finish pairs.
• QuickSort12.java As QuickSort11.java, but only the time elapsed between start and finish of the sorting is displayed.

Examples of code for sorting: merge sort algorithm

• MergeSort1.java Demonstrates a static method which sorts an array of integers destructively using the merge sort algorithm. The integers have to be typed in.
• MergeSort2.java Demonstrates a static method which sorts an array of strings destructively into alphabetic order using the merge sort algorithm. The strings have to be typed in.
• MergeSort3.java As MergeSort1.java, but the integers are generated randomly and displayed.
• MergeSort4.java As MergeSort2.java, but the integers are generated randomly and displayed.
• MergeSort5.java As MergeSort1.java, but the integers are generated randomly and only the time elapsed between start and finish of the sorting is displayed.
• MergeSort6.java As MergeSort2.java, but the strings are generated randomly and only the time elapsed between start and finish of the sorting is displayed.
• MergeSort7.java As MergeSort3.java, but works on arrayLists rather than arrays.
• MergeSort8.java As MergeSort5.java, but works on arrayLists rather than arrays.
• MergeSort9.java Demonstrates a static method which sorts an array of integers constructively using the merge sort algorithm. The integers are generated randomly and displayed.
• MergeSort10.java As MergeSort9.java, but only the time elapsed between start and finish of the sorting is displayed.
• MergeSort11.java As MergeSort9.java, but works on arrayLists rather than arrays.
• MergeSort12.java As MergeSort10.java, but works on arrayLists rather than arrays.

Use of Java's built-in sorting methods

• JavaSort1.java Demonstrates Java's built-in method for sorting arrays destructively on an array of integers, with the integers generated randomly and displayed.
• JavaSort1a.java As JavaSort1.java, but the integers are not generated randomly, they have to be typed in.
• JavaSort2.java Demonstrates Java's built-in method for sorting arrays destructively on an array of strings, with the strings generated randomly.
• JavaSort3.java As JavaSort1.java, but only the time elapsed between start and finish of the sorting is displayed.
• JavaSort4.java As JavaSort2.java, but only the time elapsed between start and finish of the sorting is displayed.
• JavaSort5.java Demonstrates Java's built-in method for sorting arrayLists destructively on an ArrayList<Integer>, with the integers generated randomly and displayed.
• JavaSort6.java Demonstrates Java's built-in method for sorting arrayLists destructively on an ArrayList<Integer>, with the strings generated randomly and displayed.
• JavaSort7.java As JavaSort5.java, but only the time elapsed between start and finish of the sorting is displayed.
• JavaSort8.java As JavaSort6.java, but only the time elapsed between start and finish of the sorting is displayed.

Supplementary code

• WordGen.java Code to generate random pronounceable strings.
• Exercise6.java Front-end code for Exercise 6, type in your own data.
• Exercise6a.java Front-end code for Exercise 6, randomly generates data, and measures timing.

Last modified: 16 July 2019