Beginning Java Data Structures and Algorithms

Sharpen your problem solving skills by learning core computer science concepts in a pain-free manner

James Cutajar

• Éditeur: Packt Publishing
• Année: 2018
• ISBN:
  9781789533750
• Édition: 1
• Sujet: Ciencia de la computación
• Sous-sujet: Programación en Java

Though your application serves its purpose, it might not be a high performer. Learn techniques to accurately predict code efficiency, easily dismiss inefficient solutions, and improve the performance of your application.

Key Features

• Explains in detail different algorithms and data structures with sample problems and Java implementations where appropriate
• Includes interesting tips and tricks that enable you to efficiently use algorithms and data structures
• Covers over 20 topics using 15 practical activities and exercises

Book Description

Learning about data structures and algorithms gives you a better insight on how to solve common programming problems. Most of the problems faced everyday by programmers have been solved, tried, and tested. By knowing how these solutions work, you can ensure that you choose the right tool when you face these problems.

This book teaches you tools that you can use to build efficient applications. It starts with an introduction to algorithms and big O notation, later explains bubble, merge, quicksort, and other popular programming patterns. You'll also learn about data structures such as binary trees, hash tables, and graphs. The book progresses to advanced concepts, such as algorithm design paradigms and graph theory. By the end of the book, you will know how to correctly implement common algorithms and data structures within your applications.

What you will learn

• Understand some of the fundamental concepts behind key algorithms
• Express space and time complexities using Big O notation.
• Correctly implement classic sorting algorithms such as merge and quicksort
• Correctly implement basic and complex data structures
• Learn about different algorithm design paradigms, such as greedy, divide and conquer, and dynamic programming
• Apply powerful string matching techniques and optimize your application logic
• Master graph representations and learn about different graph algorithms

Who this book is for

If you want to better understand common data structures and algorithms by following code examples in Java and improve your application efficiency, then this is the book for you. It helps to have basic knowledge of Java, mathematics and object-oriented programming techniques.

Sorting Algorithms and Fundamental Data Structures

In the previous chapter, we saw how the intersection problem can be improved by using a sorting algorithm. This is common with many problems. If the data is organized in an ordered manner, a more efficient algorithm can be developed. In this chapter, we will start by exploring three types of sorting techniques, which are bubble, quick, and merge sorting. Later, we will learn different ways to organize data using fundamental data structures.

By the end of this chapter, you will be able to:

• Describe how bubble sorting works
• Implement faster sorting with quick sort
• Characterize merge sorting
• Build a linked list data structure
• Implement queues
• Describe the stack data structure

Introducing Bubble Sorting

Bubble sorting is the simplest sorting algorithm out there. The technique involves making multiple passes over the input array and swapping unordered elements close to one another. The technique is called bubble sort, as the sorted list "bubbles" up from the tail end of the list.

Understanding Bubble Sorting

All sorting algorithms accept a list of elements and return them ordered. The main difference between each algorithm is the manner in which the sorting is done. Bubble sorting works by swapping adjacent elements. This pushes the sorted elements toward the end of the list.

Snippet 2.1 shows the pseudocode for bubble sort. The algorithm involves three simple tasks, which involves repeatedly stepping through the list to sort, comparing adjacent elements, and swapping them around if the first element is bigger than the second.

How many passes do we need to perform on the array until our list is sorted? It turns out that to guarantee that our list is sorted, we need to do (n - 1) passes on the list, n being the length of our array. We will show why (n - 1) passes are needed in the next section, but this is the main reason why bubble sort has a runtime complexity of O(n²), since we're processing n elements for n - 1 times.

The pseudocode for bubble sort is as follows:

bubbleSort(array)
 n = length(array)
 for (k = 1 until n)
 for (j = 0 until -1)
 if(array[j] > array[j + 1])
 swap(array, j, j + 1) 

Snippet 2.1: Bubble sort pseudocode

The swap function in the Snippet 2.1 switches the values of the two array pointers j and j+1 using a temporary variable.

Implementing Bubble Sort

To implement bubble sort in Java, follow these steps:

1. Apply the pseudocode shown in Snippet 2.1 in Java. Create a class and a method, accepting an array to sort as follows:

 public void sort(int[] numbers) 

2. The slightly tricky part of this algorithm is the swapping logic. This is done by assigning one of the elements to be swapped to a temporary variable, as shown in Snippet 2.2:

public void sort(int[] numbers) {
 for (int i = 1; i < numbers.length; i++) {
 for (int j = 0; j < numbers.length - 1; j++) {
 if (numbers[j] > numbers[j + 1]) {
 int temp = numbers[j];
 numbers[j] = numbers[j + 1];
 numbers[j + 1] = temp;
 }
 }
 }
} 

Snippet 2.2: Bubble sort solution. Source class name: BubbleSort

Go to https://goo.gl/7atHVR to access the code.

Although bubble sort is very easy to implement, it's also one of the slowest sorting methods out there. In the next section, we will look at how we can slightly improve the performance of this algorithm.

Improving Bubble Sorting

There are two main techniques we can adopt to improve the performance of bubble sort. It's important to realize that although both of these strategies improve the overall performance of bubble sort in the average case; in the worst case, the algorithm still has the same poor runtime complexity of O(n²).

The first small enhancement we can make to the original bubble sort is to make use of the fact that a sorted "bubble" is building at the end of the list. With every pass we make, another item is added at the end portion of this bubble. This is the reason why (n - 1) passes are needed.

This is also shown in Figure 2.1. In this diagram, the items shown in the dotted circle are already sorted in the correct place:

Figure 2.1: Bubble forming toward the end of the list

We can use this fact so we don't try to sort the elements inside this bubble. We can do this by slightly modifying our Java code, as shown in Snippet 2.3. In the inner loop, instead of processing until the end of the list, we can stop just before the sorted bubble, until numbers.length - i. For brevity, in Snippet 2.3 we have replaced the swap logic with a method as follows:

public void sortImprovement1(int[] numbers) {
 for (int i = 1; i < numbers.length; i++) {
 for (int j = 0; j < numbers.length - i; j++) {
 if (numbers[j] > numbers[j + 1]) {
 swap(numbers, j, j + 1);
 }
 }
 }
} 

Snippet 2.3: Bubble sort improvement 1. Source class name: BubbleSort

Go to https://goo.gl/vj267K to access the code.

If we give a sorted list to our bubble sort algorithm, we will still make multiple passes on it without modifying it. We can further improve the algorithm by cutting short the outer loop when the list inside the array is fully sorted. We can check that the array is sorted by checking if any swaps were done during our last pass. In this manner, if we give our method an already sorted list, we just need to do one pass on the array and leave it untouched. This means that the best case is now O(n), although the worst case stays the same.

Implementing Bubble Sort Improvement

We need to improve the...