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

Until now, we've always looked at algorithms from a pessimistic perspective. The advantage of this is clear: preparing for the worst means you're covered no matter what. But not all data represents the worst case, and in fact most cases fall within an ordinary range.

In this chapter, we consider all scenarios and judge the appropriate algorithm based on the situation.

This chapter proceeds based on the insertion sort algorithm.

The array to be sorted is shown above, and the underlying idea is as follows.

1. Store the second element's value in a temporary variable and remove it from the array.

Insertion sort starts from the second index of the array.

• Temporary variable: 3
• Value compared: -

Since this is the first step, assign 3 to the temporary variable.

2. Compare the elements to the left of the current index and shift as needed based on the comparison.

Compare the elements currently positioned to the left of the current index, and if any is greater than the temporary variable's value, shift that value one position to the right.

• Temporary variable: 3
• Value compared: 7

Since the compared value is greater than the temporary variable, shift it one position to the right.

This comparison repeats until it encounters a value smaller than the temporary variable, or reaches the start of the array.

3. Insert the temporary variable's value into the current gap.

Since we've reached the very start of the elements, comparison ends, and the temporary variable's value, 3, is inserted into the current gap. 3 isn't fully sorted yet, and it isn't excluded from the next passthrough's work.

Based on the principle from the previous section, let's perform insertion sort.

1. Passthrough 1: Store the second element's value in a temporary variable and remove it from the array.

Insertion sort starts from the second index of the array.

• Temporary variable: 3
• Value compared: -

Since this is the first step, assign 3 to the temporary variable.

2. Passthrough 1: Compare the elements to the left of the current index and shift as needed based on the comparison.

Compare the elements currently positioned to the left of the current index, and if any is greater than the temporary variable's value, shift that value one position to the right.

• Temporary variable: 3
• Value compared: 7

Since the compared value is greater than the temporary variable, shift it one position to the right.

This comparison repeats until it encounters a value smaller than the temporary variable, or reaches the start of the array.

1. Passthrough 1: Insert the temporary variable's value into the current gap.

Since we've reached the very start of the elements, comparison ends, and the temporary variable's value, 3, is inserted into the current gap. 3 isn't fully sorted yet, and it isn't excluded from the next passthrough's work.

4. Passthrough 2: Move the current index one position to the right and perform step 1.

• Temporary variable: 9
• Value compared: -

Assign the third element's value, 9, to the temporary variable.

5. Passthrough 2: Compare the elements to the left of the current index and shift as needed based on the comparison.

• Temporary variable: 9
• Value compared: 7

If the compared value is smaller than the temporary variable, comparison ends and the temporary variable is inserted into the current gap. In this case, the element immediately to the left is 7, which is smaller than 9, so comparison ends immediately and insertion proceeds.

5. Passthrough 2: Insert the temporary variable's value into the current gap.

As it happens, the temporary variable, 9, gets inserted back into its original position.

6. Passthrough 3: Move the current index one position to the right and perform step 1.

• Temporary variable: 2
• Value compared: -

Assign the fourth element's value, 2, to the temporary variable.

7. Passthrough 3: Compare the elements to the left of the current index and shift as needed based on the comparison.

• Temporary variable: 2
• Value compared: 9

Since the compared value, 9, is greater than the temporary variable, 2, shift it to the right.

• Temporary variable: 2
• Value compared: 7

Since the compared value, 7, is greater than the temporary variable, 2, shift it to the right.

• Temporary variable: 2
• Value compared: 3

Since the compared value, 3, is greater than the temporary variable, 2, shift it to the right.

8. Passthrough 3: Insert the temporary variable's value into the current gap.

The temporary variable, 2, is inserted into the very first position.

9. Passthrough 4: Move the current index one position to the right and perform step 1.

• Temporary variable: 5
• Value compared: -

Assign the fifth element's value, 5, to the temporary variable.

10. Passthrough 4: Compare the elements to the left of the current index and shift as needed based on the comparison.

• Temporary variable: 5
• Value compared: 9

Since the compared value, 9, is greater than the temporary variable, 5, shift it to the right.

• Temporary variable: 5
• Value compared: 7

Since the compared value, 7, is greater than the temporary variable, 5, shift it to the right.

The temporary variable, 5, is inserted into the fourth position.

11. Passthrough 4: Insert the temporary variable's value into the current gap.

The temporary variable, 5, is inserted into the third position.

Since the current index has reached the last element, this concludes the final passthrough.

Let's implement insertion sort in Java based on the process above.

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/24/about-algorithm-chapter06/">긍정적인 시나리오 최적화</a>
 * @since 2021.07.24 Sat 02:40:19
 */
public class InsertionSort
{
	private static int compareCount = 0;
	private static int shiftCount = 0;
	private static int deleteCount = 0;
	private static int insertCount = 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();
		
		selectionSort(array);
		
		writer.write(Arrays.toString(array));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 비교 작업량: ");
		writer.write(String.valueOf(compareCount));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 시프트 작업량: ");
		writer.write(String.valueOf(shiftCount));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 삭제 작업량: ");
		writer.write(String.valueOf(deleteCount));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 삽입 작업량: ");
		writer.write(String.valueOf(insertCount));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 총 작업량: ");
		writer.write(String.valueOf(compareCount + shiftCount + deleteCount + insertCount));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 삽입 정렬 알고리즘
	 *
	 * @param array: [int[]] 대상 배열
	 */
	private static void selectionSort(int[] array)
	{
		for (int i = 1; i < array.length; i++)
		{
			// 임시 변수
			int temp = array[i];
			
			// 빈 공간
			int blank = i;
			
			// 삭제 작업 추가
			deleteCount++;
			
			// 공백 표시
			array[i] = Integer.MIN_VALUE;
			
			for (int j = i - 1; j > -1; j--)
			{
				// 비교 작업 추가
				compareCount++;
				
				// 현재 요소가 임시 변수보다 클 경우
				if (array[j] > temp)
				{
					// 시프트 작업 추가
					shiftCount++;
					
					array[blank] = array[j];
					
					blank--;
					
					array[blank] = Integer.MIN_VALUE;
				}
				
				// 아닐 경우
				else
				{
					break;
				}
			}
			
			// 삽입 작업 추가
			insertCount++;
			
			array[blank] = temp;
		}
	}
}

• Input

TC
10 9 8 7 6 5 4 3 2 1

• Output

TC
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 - 비교 작업량: 45
 - 시프트 작업량: 45
 - 삭제 작업량: 9
 - 삽입 작업량: 9
 - 총 작업량: 108

The source code and its input/output are as shown above. It takes an arbitrary array from the user, performs insertion sort, and displays the sorted result along with a breakdown of each type of work performed.

The actual core logic happens in the selectionSort method. The gap is represented by inserting Integer.MIN_VALUE, purely to signify a deletion, and it isn't counted as work.

JAVA
for (int i = 1; i < array.length; i++)
{
	// 임시 변수
	int temp = array[i];
	
	// 빈 공간
	int blank = i;
	
	// 삭제 작업 추가
	deleteCount++;
	
	// 공백 표시
	array[i] = Integer.MIN_VALUE;
	
	// ...
}

The first for loop represents each passthrough. For each passthrough, the current index i, the temporary variable temp, and the index of the deleted element blank are freshly defined. During this process, exactly one delete operation always occurs.

JAVA
for (int j = i - 1; j > -1; j--)
{
	// 비교 작업 추가
	compareCount++;
	
	// 현재 요소가 임시 변수보다 클 경우
	if (array[j] > temp)
	{
		// 시프트 작업 추가
		shiftCount++;
		
		array[blank] = array[j];
		
		blank--;
		
		array[blank] = Integer.MIN_VALUE;
	}
	
	// 아닐 경우
	else
	{
		break;
	}
}

The second for loop represents the comparison and shift work done on the elements to the left of the current index i, down to 0. Every cycle involves exactly one comparison, and depending on the relative sizes of the temporary variable and the current element, a shift may occur.

JAVA
for (int i = 1; i < array.length; i++)
{
	// ...
	
	// 삽입 작업 추가
	insertCount++;
	
	array[blank] = temp;
}

Once all comparisons finish, the temporary variable is inserted into the current gap. Exactly one insert operation always occurs during this step.

Let's analyze the work involved in insertion sort to understand its efficiency. Insertion sort consists of 4 kinds of operations: delete, compare, shift, and insert.

The worst case for insertion sort is an array with elements sorted in reverse order. When every element is sorted in reverse, every possible operation ends up occurring. The general formula for the amount of work in each category in the worst case is as follows.

• Delete: $N - 1$
• Compare: $N^2 \div 2$ (approximate)
• Shift: $N^2 \div 2$ (approximate)
• Insert: $N - 1$

From this, we can see the time complexity of insertion sort is $O(N^2 + 2N - 2)$. Since Big O notation ignores constants, this can be simplified to $O(N^2 + N)$. But Big O notation doesn't just ignore constants—it also ignores all terms except the highest-order one. That means, since the highest-order term in $N^2 + N$ is $N^2$, the $N$ term is ignored. So the final time complexity of insertion sort ends up being $O(N^2)$.

When the number of elements $N$ is 100, $N^4$ and $N^3$ differ by exactly the value of $N$, i.e., 100x. From $N^4$'s perspective, even if a full cycle of $N^3$ work happens, that's only about 1% of its own workload. Because the gap in workload between terms of different degree grows exponentially, the lower-order terms are ignored.

We've now covered three sorting algorithms: bubble, selection, and insertion. Here's a summary of their time complexities.

Having come this far through Chapters 4 through 6, we now know both the Big O notation for each sorting algorithm and the actual expression that shows up in practice. Looking at the table above, we could say that among the three sorting techniques, selection sort is the fastest. However, as repeatedly noted, this comes with the premise of being close to the worst case.

So what about the average case?

Unless the data reaches into the hundreds of millions or trillions, most ordinary environments don't process nearly that much data. In other words, this also means that most cases never reach the worst case.

Most cases follow a normal distribution like the one shown above. The further left it converges, the closer to the worst case; the further right, the closer to the best case; and the closer to the center, the closer to the average case. The vast majority fall within the average range, while the extreme cases on either end are relatively rare.

For most of the sorting algorithms we've covered so far, the worst case was when the elements were sorted in reverse order. Assuming a completely random array is given as input, think about how likely it would be to get an array that's exactly reverse-sorted. Most arrays would end up randomly arranged with no particular pattern. Even setting aside the normal distribution shown above, there are plenty of similar examples in everyday life. An outlier case among many possible cases means it differs, in some direction, from the vast majority of other cases. The best and worst cases, in a sense, fall into this category of outlier cases.

Let's check this against the insertion sort we covered in this chapter.

• Worst case: $O(N^2 + 2N - 2)$. That is, $O(N^2)$.
• Best case: $O(3(N - 1))$. That is, $O(N)$.
• Average case: $O(N^2 \div 2)$. That is, $O(N^2)$.

This can be shown in the table below.

Insertion sort's performance varies meaningfully depending on the case. Selection sort, on the other hand, is rather unfortunate here, since it has a time complexity of $O(N^2)$ regardless of the case.

JAVA
/**
 * 선택 정렬 함수
 *
 * @param array : [int[]] 대상 배열
 *
 * @return [int[]] 작업 갯수 배열
 */
private static int[] selectionSort(int[] array)
{
	int compareCount = 0;
	int swapCount = 0;
	
	for (int i = 0; i < array.length; i++)
	{
		// 패스스루의 최소값 인덱스
		int min = i;
		
		for (int j = i + 1; j < array.length; j++)
		{
			compareCount++;
			
			// 현재 요소의 값이 패스스루의 최소값보다 작을 경우
			if (array[j] < array[min])
			{
				min = j;
			}
		}
		
		// 최소 인덱스에 변화가 있었을 경우
		if (min != i)
		{
			int temp = array[min];
			
			array[min] = array[i];
			array[i] = temp;
			
			swapCount++;
		}
	}
	
	return new int[] { compareCount, swapCount };
}

The source code above is the selection sort code we covered in Chapter 5. As you can see, since there are two for loops, it's not hard to infer that it has a time complexity of $O(N^2)$. Look closer at the code, too—there's no break anywhere to end the loop early. That means it always performs $N^2$ work regardless of circumstances. In fact, running the source from Chapter 5, you'll notice the workload doesn't differ much between cases.

If most of the data you're working with is already somewhat sorted, insertion sort can be judged to be far more advantageous. If the data is completely random, there's not much difference between selection sort and insertion sort.

Let's design an intersection algorithm that, given two arrays, extracts and returns the elements common to both.

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/24/about-algorithm-chapter06/">긍정적인 시나리오 최적화</a>
 * @since 2021.07.24 Sat 04:21:40
 */
public class InsertionSort
{
	private static int compareCount = 0;
	private static int insertCount = 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[] array1 = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		writer.write("두 번째 정수 배열을 띄어쓰기로 구분하여 입력 >> ");
		writer.flush();
		
		int[] array2 = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		int[] result = intersection(array1, array2);
		
		writer.write(Arrays.toString(result));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 비교 작업량: ");
		writer.write(String.valueOf(compareCount));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 삽입 작업량: ");
		writer.write(String.valueOf(insertCount));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 총 작업량: ");
		writer.write(String.valueOf(compareCount + insertCount));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 교집합 배열 반환 함수
	 *
	 * @param array1: [int[]] 첫 번째 배열
	 * @param array2: [int[]] 두 번째 배열
	 *
	 * @return [int[]] 교집합 배열
	 */
	private static int[] intersection(int[] array1, int[] array2)
	{
		ArrayList<Integer> list = new ArrayList<>();
		
		for (int item1 : array1)
		{
			for (int item2 : array2)
			{
				compareCount++;
				
				// 두 배열의 요소가 같을 경우
				if (item1 == item2)
				{
					insertCount++;
					
					list.add(item1);
				}
			}
		}
		
		return list.stream().mapToInt(Integer::intValue).toArray();
	}
}

• Input

TC
3 1 9 8 5
2 4 7 5 1

• Output

TC
[1, 5]
 - 비교 작업량: 25
 - 삽입 작업량: 2
 - 총 작업량: 27

Since it uses a doubly nested for structure, its time complexity is naturally $O(N^2)$. When the two arrays are exactly the same size, the worst case that can occur is $O(N^2 + N)$. This can be simplified to $O(N^2)$.

The algorithm above also performs some unnecessary computation. Let's 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/24/about-algorithm-chapter06/">긍정적인 시나리오 최적화</a>
 * @since 2021.07.24 Sat 04:21:40
 */
public class ImproveIntersection
{
	private static int compareCount = 0;
	private static int insertCount = 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[] array1 = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		writer.write("두 번째 정수 배열을 띄어쓰기로 구분하여 입력 >> ");
		writer.flush();
		
		int[] array2 = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		int[] result = intersection(array1, array2);
		
		writer.write(Arrays.toString(result));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 비교 작업량: ");
		writer.write(String.valueOf(compareCount));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 삽입 작업량: ");
		writer.write(String.valueOf(insertCount));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 총 작업량: ");
		writer.write(String.valueOf(compareCount + insertCount));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 교집합 배열 반환 함수
	 *
	 * @param array1: [int[]] 첫 번째 배열
	 * @param array2: [int[]] 두 번째 배열
	 *
	 * @return [int[]] 교집합 배열
	 */
	private static int[] intersection(int[] array1, int[] array2)
	{
		ArrayList<Integer> list = new ArrayList<>();
		
		for (int item1 : array1)
		{
			for (int item2 : array2)
			{
				compareCount++;
				
				// 두 배열의 요소가 같을 경우
				if (item1 == item2)
				{
					insertCount++;
					
					list.add(item1);
					
					break;
				}
			}
		}
		
		return list.stream().mapToInt(Integer::intValue).toArray();
	}
}

• Input

TC
3 1 9 8 5
2 4 7 5 1

• Output

TC
[1, 5]
 - 비교 작업량: 24
 - 삽입 작업량: 2
 - 총 작업량: 27

The difference lies in the if statement inside the for loop.

JAVA
// 두 배열의 요소가 같을 경우
if (item1 == item2)
{
	insertCount++;
	
	list.add(item1);
	
	break;
}

As shown here, once a matching element is found, a break was added to forcibly end that passthrough. In the worst-case scenario, this still comes out to the same $O(N^2)$, but in the best-case scenario, it will run at $O(N)$. Given that the previous algorithm was always $O(N^2)$, this can be considered a reasonable optimization.

The main points covered in this chapter are as follows.

• Algorithms don't necessarily need to be viewed pessimistically.
• In fact, most cases fall within the average range.
• Depending on an algorithm's logic, time complexity can vary meaningfully based on the distribution of cases.

In this chapter, we explored another perspective on algorithms. Since most cases fall within the average range, average time complexity is also an important factor when measuring performance.

The next chapter introduces a new concept: hash tables.