This post is part of a personal study group activity, summarizing the content after reading through the book "Grokking Algorithms."

Having learned Big O notation in the previous chapter, we confirmed that we can compare algorithms against each other by comparing their time complexities. In this chapter, we'll design a bubble sort algorithm and see how it can be improved using Big O notation.

Sorting techniques are widely used to handle arrays effectively. As we saw with binary search, a sorted array imposes a regularity that lets you predict its elements to some extent. For this reason, various techniques for sorting arrays have been devised, and in this section we'll look at bubble sort, the most basic and relatively inefficient of the sorting algorithms.

Given an array like the one above, let's see how bubble sort sorts it into ascending order.

1. First, compare the very first element with the next one.

2. If the earlier element is greater than the later one, swap them.

3. Move each pointer forward by one and compare the next elements.

4. Repeat steps 1 through 3.

Repeat steps 1 through 3 until no more swaps occur. This repeated cycle is called a passthrough.

Now that we understand how bubble sort works from the previous section, let's apply it to fully sort an array.

The target array is the same one used in the previous section.

1. Passthrough 1: Compare 8 and 4

Compare 8 and 4. Since the earlier element is greater, swap them.

2. Passthrough 1: Compare 8 and 6

Compare 8 and 6. Since the earlier element is greater, swap them.

3. Passthrough 1: Compare 8 and 7

Compare 8 and 7. Since the earlier element is greater, swap them.

4. Passthrough 1: Compare 8 and 3

Compare 8 and 3. Since the earlier element is greater, swap them.

We've reached the very last element of the array, so the last element, 8, is now in its correct sorted position. Since ascending order requires the largest value to end up at the end of the array, it's appropriate that 8, the largest value among the elements, ends up there.

Since it's already sorted, the next passthrough doesn't need to compare the last element. In other words, as passthroughs progress, the range of elements to compare shrinks.

Elements that have finished sorting are marked in yellow.

5. Passthrough 2: Compare 4 and 6

Compare 4 and 6. Since the later element is greater, don't swap.

6. Passthrough 2: Compare 6 and 7

Compare 6 and 7. Since the later element is greater, don't swap.

7. Passthrough 2: Compare 7 and 3

Compare 7 and 3. Since the earlier element is greater, swap them.

Element 7 is now fully in place. Start the next passthrough.

8. Passthrough 3: Compare 4 and 6

Compare 4 and 6. Since the later element is greater, don't swap.

9. Passthrough 3: Compare 6 and 3

Compare 6 and 3. Since the earlier element is greater, swap them.

Element 6 is now fully in place. Start the next passthrough.

10. Passthrough 4: Compare 4 and 3

Compare 4 and 3. Since the earlier element is greater, swap them.

Since this is the final passthrough, all elements are now sorted.

The sorted array looks like this, achieved through a total of 10 operations.

Let's implement bubble sort in actual code.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 누구나 자료 구조와 알고리즘 버블 정렬 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/16/about-algorithm-chapter04/">빅 오로 코드 속도 올리기</a>
 * @since 2021.07.16 Fri 19:11:19
 */
public class BubbleSort
{
	// 배열
	private static int[] array;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		writer.write("버블 정렬할 정수 배열을 띄어쓰기로 구분하여 입력 >> ");
		writer.flush();
		
		array = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		int[] count = bubbleSort();
		
		writer.newLine();
		writer.write(Arrays.toString(array));
		writer.newLine();
		writer.newLine();
		writer.flush();
		
		writer.write(" - 비교 작업량: ");
		writer.write(String.valueOf(count[0]));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 스왑 작업량: ");
		writer.write(String.valueOf(count[1]));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 총 작업량: ");
		writer.write(String.valueOf(count[0] + count[1]));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 버블 정렬 및 작업량 반환 함수
	 *
	 * @return [int[]] 비교 작업량과 스왑 작업량
	 */
	private static int[] bubbleSort()
	{
		// 비교 작업량
		int compareCount = 0;
		
		// 스왑 작업량
		int swapCount = 0;
		
		// 스왑 여부
		boolean isSwaped = true;
		
		// 비교 인덱스
		int index = array.length - 1;
		
		// 스왑이 일어나지 않을 때까지
		while (isSwaped)
		{
			isSwaped = false;
			
			for (int i = 0; i < index; i++)
			{
				compareCount++;
				
				// 현재 요소가 다음 요소보다 클 경우
				if (array[i] > array[i + 1])
				{
					// 스왑 발생
					isSwaped = true;
					swapCount++;
					
					int temp = array[i];
					
					array[i] = array[i + 1];
					array[i + 1] = temp;
				}
			}
			
			index--;
		}
		
		return new int[] { compareCount, swapCount };
	}
}

The source code above takes a set of numbers separated by spaces from the user and performs bubble sort on them.

• Input

TC
5 4 12 6 77 32 1 9 11 59

• Output

TC
[1, 4, 5, 6, 9, 11, 12, 32, 59, 77]

 - 읽기 작업량: 42
 - 스왑 작업량: 16
 - 총 작업량: 58

The actual bubble sort algorithm is shown below.

JAVA
/**
 * 버블 정렬 및 작업량 반환 함수
 *
 * @return [int[]] 비교 작업량과 스왑 작업량
 */
private static int[] bubbleSort()
{
	// 비교 작업량
	int compareCount = 0;
	
	// 스왑 작업량
	int swapCount = 0;
	
	// 스왑 여부
	boolean isSwaped = true;
	
	// 비교 인덱스
	int index = array.length - 1;
	
	// 스왑이 일어나지 않을 때까지
	while (isSwaped)
	{
		isSwaped = false;
		
		for (int i = 0; i < index; i++)
		{
			compareCount++;
			
			// 현재 요소가 다음 요소보다 클 경우
			if (array[i] > array[i + 1])
			{
				// 스왑 발생
				isSwaped = true;
				swapCount++;
				
				int temp = array[i];
				
				array[i] = array[i + 1];
				array[i + 1] = temp;
			}
		}
		
		index--;
	}
	
	return new int[] { compareCount, swapCount };
}

• compareCount: comparison operation count
• swapCount: swap operation count
• isSwaped: whether a swap occurred
• index: sorting index

index is the maximum index of the array up to which sorting is performed. The reason 1 is subtracted has to do with a property of bubble sort. The maximum index of an array like $[0, 1, 2]$ is 3. Wait—when the maximum index of the array is 3, the first passthrough performs 2 comparisons: 0 with 1, and 1 with 2. If we don't subtract one from the maximum index, we'd end up trying to compare 0 with 1, 1 with 2, and 2 with something that doesn't exist, triggering an ArrayIndexOutOfBoundsException.

The while loop repeats until no swaps occur. If no swap occurs at all within a passthrough, sorting is considered complete and the loop terminates.

The for loop compares elements up to the index boundary, swapping whenever the current element is greater than the next. During this process, isSwaped gets set to true. Since isSwaped is true, the next passthrough will proceed.

Each relevant step is counted.

Bubble sort consists of two kinds of operations.

• Comparison: comparing to find the larger number.
• Exchange: swapping to sort.

With 5 elements, the following comparison operations occur.

• Passthrough 1: 4 comparisons total
• Passthrough 2: 3 comparisons total
• Passthrough 3: 2 comparisons total
• Passthrough 4: 1 comparison total
• Passthrough 5: no comparisons (sorting complete)

In other words, 4 + 3 + 2 + 1 = 10 comparisons occur in total.

So what about the swap operations? Swaps may or may not occur depending on the situation.

In the previous chapter, we said that algorithms are always evaluated from a pessimistic standpoint, so let's assume a swap always occurs.

The worst case for bubble sort
Bubble sort is an algorithm that sorts by comparing each element with the next one. If sorting into ascending order, the worst case occurs when the input array is sorted in descending order. In this case, every single comparison results in a swap.

With 5 elements sorted in descending order—the worst case—the following swap operations occur.

• Passthrough 1: 4 swaps total
• Passthrough 2: 3 swaps total
• Passthrough 3: 2 swaps total
• Passthrough 4: 1 swap total
• Passthrough 5: no swaps (sorting complete)

The same amount of work occurs as with comparisons. This is summarized in the table below.

For an array of $N$ elements, the maximum work performed by bubble sort is $N(N - 1)$. As mentioned in the previous chapter, algorithms don't distinguish much between $O(N^2)$ and $O(N^2 - N)$. In other words, the time complexity of bubble sort is $O(N^2)$.

$O(N^2)$ grows far more sharply than $O(N)$.

Comparing them makes this even clearer at a glance. This $O(N^2)$ is called quadratic time.

Above, we designed the bubble sort algorithm. Its time complexity turns out to be $O(N^2)$. Given how much effort we put into the previous chapter explaining that we should minimize time complexity as much as possible by comparing linear search and binary search, it feels almost embarrassing how far this algorithm's efficiency has fallen through the floor.

Here's a similarly quadratic-time algorithm—one that checks an input array for duplicate values.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 누구나 자료 구조와 알고리즘 중복 확인 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/16/about-algorithm-chapter04/">빅 오로 코드 속도 올리기</a>
 * @since 2021.07.16 Fri 20:46:15
 */
public class DuplicateCheck
{
	private static int count = 0;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		writer.write("중복 확인할 정수 배열을 띄어쓰기로 구분하여 입력 >> ");
		writer.flush();
		
		// 배열
		int[] array = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		boolean result = isDuplicated(array);
		
		// 중복된 요소가 있을 경우
		if (result)
		{
			writer.write("중복된 요소가 존재합니다.");
		}
		
		// 없을 경우
		else
		{
			writer.write("중복된 요소가 존재하지 않습니다.");
		}
		
		writer.newLine();
		writer.flush();
		
		writer.write("작업량: ");
		writer.write(String.valueOf(count));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 요소의 중복 여부 반환 함수
	 *
	 * @param array: [int[]] 배열
	 *
	 * @return [boolean] 중복 여부
	 */
	private static boolean isDuplicated(int[] array)
	{
		for (int i = 0; i < array.length; i++)
		{
			for (int j = 0; j < array.length; j++)
			{
				count++;
				
				// 서로 다른 요소가 동일한 값을 가질 경우
				if (i != j && array[i] == array[j])
				{
					return true;
				}
			}
		}
		
		return false;
	}
}

The source code is as shown above.

• Input

JAVA
0 1 2 3 4 5 6 7 8 9

• Output

JAVA
중복된 요소가 존재하지 않습니다.
작업량: 100

This algorithm likewise has a worst-case time complexity of $O(N^2)$ when $N = 10$.

Let's look at the core logic that determines duplicates.

JAVA
/**
 * 요소의 중복 여부 반환 함수
 *
 * @param array: [int[]] 배열
 *
 * @return [boolean] 중복 여부
 */
private static boolean isDuplicated(int[] array)
{
	for (int i = 0; i < array.length; i++)
	{
		for (int j = 0; j < array.length; j++)
		{
			count++;
			
			// 서로 다른 요소가 동일한 값을 가질 경우
			if (i != j && array[i] == array[j])
			{
				return true;
			}
		}
	}
	
	return false;
}

Just like bubble sort, there's a nested loop here. When loops are nested, the time complexity rises sharply with the number of nested loops.

A nested loop performs $N$ operations for each of $N$ elements. The more deeply loops are nested, the more you repeat something like $N$ times $N$ times $N$ times... Naturally, this also means the time complexity skyrockets without bound.

In other words, whenever you spot an algorithm using nested loops, you can immediately infer that its time complexity is at least $O(N^2)$.

I recall that in the previous chapter, we went to great lengths comparing the time complexities of linear search and binary search to explain just how inefficient $O(N)$ is compared to $O(\log N)$. And yet, the two algorithms we just looked at deliver an inefficiency so extreme it makes that earlier effort seem trivial by comparison.

Well, maybe that's just because you haven't written many algorithms—there are cases where you have no choice but to design it that way, you know??

That's a fair point. Even on Baekjoon Online Judge, nested loops sometimes show up because the logic is complex. The same holds true in real-world work. Sometimes the logic is complicated, sometimes the cost of optimizing the source is too high, sometimes the inefficiency just isn't that bad in practice. Or maybe the computer's performance is good enough that there's no felt need to invest in such a headache.

As an aside, apparently large companies often choose to maximize computing power rather than invest in this kind of optimization. Logic tends to apply in limited scopes anyway, and it can actually be cheaper to just scale up computing power instead. Unlike logic, computing resources can be redirected elsewhere, making that approach more broadly useful.

My own computer isn't too shabby as of this writing, but unfortunately, the duplicate-check algorithm written above happens to be very cheap to optimize. Since our goal here is learning, let's go ahead and optimize it.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * 누구나 자료 구조와 알고리즘 향상된 중복 확인 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/16/about-algorithm-chapter04/">빅 오로 코드 속도 올리기</a>
 * @since 2021.07.16 Fri 21:18:05
 */
public class ImproveDuplicateCheck
{
	private static int count = 0;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		writer.write("중복 확인할 정수 배열을 띄어쓰기로 구분하여 입력 >> ");
		writer.flush();
		
		// 배열
		int[] array = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		boolean result = isDuplicated(array);
		
		// 중복된 요소가 있을 경우
		if (result)
		{
			writer.write("중복된 요소가 존재합니다.");
		}
		
		// 없을 경우
		else
		{
			writer.write("중복된 요소가 존재하지 않습니다.");
		}
		
		writer.newLine();
		writer.flush();
		
		writer.write("작업량: ");
		writer.write(String.valueOf(count));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 요소의 중복 여부 반환 함수
	 *
	 * @param array: [int[]] 배열
	 *
	 * @return [boolean] 중복 여부
	 */
	private static boolean isDuplicated(int[] array)
	{
		ArrayList<Integer> list = new ArrayList<>();
		
		for (int item : array)
		{
			count++;
			
			// 중복되지 않았을 경우
			if (!list.contains(item))
			{
				list.add(item);
			}
			
			// 중복된 경우
			else
			{
				return true;
			}
		}
		
		return false;
	}
}

The source code is as shown above.

• Input

JAVA
0 1 2 3 4 5 6 7 8 9

• Output

JAVA
중복된 요소가 존재하지 않습니다.
작업량: 10

This is implemented using Java's dynamic array class, ArrayList. If an element hasn't appeared before, it won't already be in list, so we add it. Later, if a number that's already in list is found during execution, that means it's a duplicate, so we stop and return the result.

We can confirm that for $N = 10$, this has been dramatically improved to a time complexity of $O(N)$. Compared to the previous result, that's a 10x difference—mathematically, the improved algorithm can run 10 times for every single run of the previous algorithm.

Right now, with $N = 10$, the difference might not feel very noticeable because the element count itself is small, but at $N = 10,000$, the difference balloons to a staggering 10,000x.

This is exactly why algorithm optimization matters. The closer the data being processed gets to big-data scale, the more dramatically the efficiency gains multiply.

Here's a summary of what we learned in this chapter.

• You can infer time complexity from whether loops are nested and how many levels deep they go.
• Time complexity lets you numerically compare and express improvements in an algorithm's performance.

Honestly, looking back at this summary, it feels like I went on at great length to explain something rather obvious. I just hadn't properly understood this obvious thing before.

There are also algorithms where the speed is similar enough that Big O notation alone doesn't reveal the difference. Even so, some factor will still cause a real difference somewhere. The next chapter looks at optimizing this kind of algorithm.