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

So far, we've quantified algorithm performance comparisons using Big O notation. But Big O notation isn't perfect for measuring an algorithm's performance either.

In the previous chapter, we explained that both $N(O^2)$ and $N(N^2 - N)$ are considered $N(O^2)$ under Big O notation. Because of this property, algorithms that actually show a clear difference can end up measured as having nearly identical performance under Big O notation.

An algorithm's speed is a critical metric when choosing between algorithms, so measuring it accurately is very important. In this chapter, as described above, we'll distinguish between algorithms that generally appear to have similar performance and determine which one is actually faster.

The previous chapter walked through the bubble sort algorithm. In this chapter, we'll walk through a different sorting algorithm: selection sort.

The selection sort algorithm works by scanning the elements on each passthrough to find the minimum value, then moving it to the front to sort it.

The array we'll use for sorting is shown above, and the process proceeds as follows.

1. Examine the very first value.

The key idea is to find the smallest element within a single passthrough. Since this is still the first step, the first element becomes the minimum by default.

2. Move the search pointer forward by one and compare it against the passthrough minimum.

• Minimum: 5
• Value examined: 3

Update the passthrough minimum to 3.

3. Repeat step 2.

• Minimum: 3
• Value examined: 9

Since the passthrough minimum is smaller, it isn't updated.

4. Repeat step 2.

• Minimum: 3
• Value examined: 2

Update the passthrough minimum to 2.

5. Repeat step 2.

• Minimum: 2
• Value examined: 6

Since the passthrough minimum is smaller, it isn't updated. Since this is the last element, the scan ends and a single element gets sorted.

6. Move the element with the passthrough minimum to the front.

Swap the front element, 5, with the minimum value, 2. Since 2 is now fully in its correct position, it's excluded from all future passthroughs.

Now that we understand how selection sort works from the previous section, let's perform selection sort on the entire array.

Passthrough 1 is identical to the process from the previous section.

1. Passthrough 1: Examine the very first element.

• Minimum: -
• Value examined: 5

The key idea is to find the smallest element within a single passthrough. Since this is still the first step, the first element becomes the minimum by default.

2. Passthrough 1: Move the search pointer forward by one and compare it against the passthrough minimum.

• Minimum: 5
• Value examined: 3

Update the passthrough minimum to 3.

3. Passthrough 1: Repeat step 2.

• Minimum: 3
• Value examined: 9

Since the passthrough minimum is smaller, it isn't updated.

4. Passthrough 1: Repeat step 2.

• Minimum: 3
• Value examined: 2

Update the passthrough minimum to 2.

5. Passthrough 1: Repeat step 2.

• Minimum: 2
• Value examined: 6

Since the passthrough minimum is smaller, it isn't updated. Since this is the last element, the scan ends and a single element gets sorted.

6. Passthrough 1: Move the element with the passthrough minimum to the front.

Swap the front element, 5, with the minimum value, 2. Since 2 is now fully in its correct position, it's excluded from all future passthroughs.

7. Passthrough 2: Examine the second element.

• Minimum: -
• Value examined: 3

Assign this element as the minimum.

8. Passthrough 2: Repeat step 2.

• Minimum: 3
• Value examined: 9

Since the passthrough minimum is smaller, it isn't updated.

9. Passthrough 2: Repeat step 2.

• Minimum: 3
• Value examined: 5

Since the passthrough minimum is smaller, it isn't updated.

10. Passthrough 2: Repeat step 2.

• Minimum: 3
• Value examined: 6

Since the passthrough minimum is smaller, it isn't updated.

11. Passthrough 2: Move the element with the passthrough minimum to the second position.

The minimum value, 3, happens to already be in the correct position, so no swap occurs. Since the second element is now sorted, it's likewise excluded from all future passthroughs.

12. Passthrough 3: Examine the third element.

• Minimum: -
• Value examined: 9

Assign this element as the minimum.

13. Passthrough 3: Repeat step 2.

• Minimum: 9
• Value examined: 5

Update the passthrough minimum to 5.

14. Passthrough 3: Repeat step 2.

• Minimum: 5
• Value examined: 6

Since the passthrough minimum is smaller, it isn't updated.

15. Passthrough 3: Move the element with the passthrough minimum to the third position.

Swap the third element, 9, with the minimum value, 5.

16. Passthrough 4: Examine the fourth element.

• Minimum: -
• Value examined: 9

Assign this element as the minimum.

17. Passthrough 4: Repeat step 2.

• Minimum: 9
• Value examined: 6

Update the passthrough minimum to 6.

18. Passthrough 4: Move the element with the passthrough minimum to the fourth position.

Swap the fourth element, 9, with the minimum value, 6.

19. Passthrough 5: Examine the last element.

• Minimum: -
• Value examined: 9

Update the passthrough minimum to 9.

Since this is the last element, it's already in its sorted position by default, and the passthrough ends.

With this, the final sorted array produced by selection sort looks like this.

Let's implement selection 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/23/about-algorithm-chapter05/">빅 오를 사용하거나 사용하지 않는 코드 최적화</a>
 * @since 2021.07.23 Fri 01:12:20
 */
public class SelectionSort
{
	/**
	 * 메인 함수
	 *
	 * @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();
		
		int[] processes = selectionSort(array);
		
		writer.write(Arrays.toString(array));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 비교 작업량: ");
		writer.write(String.valueOf(processes[0]));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 스왑 작업량: ");
		writer.write(String.valueOf(processes[1]));
		writer.newLine();
		writer.flush();
		
		writer.write(" - 총 작업량: ");
		writer.write(String.valueOf(processes[0] + processes[1]));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 선택 정렬 함수
	 *
	 * @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 };
	}
}

• Input

TC
5 3 4 1 2

• Output

TC
[1, 2, 3, 4, 5]
 - 비교 작업량: 10
 - 스왑 작업량: 4
 - 총 작업량: 14

It takes a space-separated array of numbers from the user, performs selection sort, and displays the amount of work broken down by category. The core logic is performed in the selectionSort method.

• First for: passthrough
• Second for: comparison work
• if statement: swap work

JAVA
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++;
	}
}

For each passthrough, the first element is assigned to the minimum min. Then, each subsequent element up through the last is compared against min in sequence.

Whenever an element smaller than min is found, it replaces min. Ultimately, min ends up holding the smallest value among all the elements examined.

The if statement checks whether min has changed. If it's not the index of the passthrough's first element, that means min changed, so a swap is performed.

Let's examine the efficiency of selection sort. As mentioned above, selection sort consists of comparison and exchange operations. Comparisons always happen, while exchanges happen conditionally.

For an array of 5 elements, the amount of comparison work when performing selection sort is as follows.

$4 + 3 + 2 + 1 = 10$, so a total of 10 comparisons are performed. In general terms, this can be defined as $(N - 1) + (N - 2) + \dots + 1$.

Unlike comparisons, exchanges happen at most once per passthrough, and depending on the conditions, may not happen at all.

In the worst case, an exchange happens on every passthrough, so with 5 elements, we can expect at most 4 exchange operations.

For example, with $[ 5, 3, 4, 1, 2 ]$, a swap occurs on every single passthrough.

Doesn't the book say the worst case is when the array is reversed??
With a reversed array, only two exchanges actually end up occurring. Once half is sorted, the remaining back half sorts itself automatically.

Comparing bubble sort and selection sort looks like this.

Selection sort's speed converges to about 50% of bubble sort's. In other words, even in the worst case, selection sort is roughly twice as fast.

The detailed comparison in the previous section confirmed there's a meaningful difference between bubble sort and selection sort. Expressed in Big O notation, selection sort is $O(N^2 / 2)$.

The table above backs this up. But the actual Big O notation for both bubble sort and selection sort is the same: $O(N^2)$. Selection sort likewise has two nested loops, exhibiting the same $O(N^2)$ characteristics. This is a property that's been mentioned consistently since Chapter 3, where Big O notation was first introduced: Big O notation ignores constants.

Constants clearly matter numerically, so why does a technique that's supposed to measure performance take such a loose form?

Why does Big O notation ignore constants? This can be explained by the perspective Big O notation takes. Let's compare the workloads of $O(N)$ vs. $O(N^2)$, and $O(100N)$ vs. $O(N^2)$, to see what perspective Big O notation adopts when evaluating algorithms.

For $O(N^2)$, it's always equal to or slower than $O(N)$ no matter what. But $O(100N)$ is a bit different. In the early range where the data is small, $O(N^2)$ is actually faster, but once the data grows large enough, $O(100N)$ becomes faster.

This is why Big O notation doesn't put much weight on constants. When the ranges are entirely different, like $O(N)$ vs. $O(N^2)$, one is always faster or always slower.

But for $O(100N)$ vs. $O(N^2)$, which one is relatively faster or slower depends on the amount of data. To distinguish between algorithms in this kind of situation, Big O notation ignores constants. Either way, in the long run, both $O(N)$ and $O(100N)$ end up faster than $O(N^2)$.

Big O notation is still a valid measure of performance when comparing algorithms from entirely different ranges. Just keep in mind that even with identical time complexity, the actual performance shown by algorithms can differ meaningfully.

Let's design an algorithm that, given an array of $N$ elements, selects only one out of every two elements to build a new array with $N \div 2$ elements.

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/23/about-algorithm-chapter05/">빅 오를 사용하거나 사용하지 않는 코드 최적화</a>
 * @since 2021.07.23 Fri 22:32:54
 */
public class HalfArray
{
	/**
	 * 메인 함수
	 *
	 * @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();
		
		int[] result = solve(array);
		
		writer.write(Arrays.toString(result));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 알고리즘 결과 반환 함수
	 *
	 * @param array: [int[]] 대상 배열
	 *
	 * @return [int[]] 결과 배열
	 */
	private static int[] solve(int[] array)
	{
		int length = (int) Math.ceil(array.length / 2D);
		
		int[] result = new int[length];
		
		int count = 0;
		
		for (int i = 0; i < array.length; i++)
		{
			// 인덱스가 짝수일 경우
			if (i % 2 == 0)
			{
				result[count] = array[i];
				
				count++;
			}
		}
		
		return result;
	}
}

• Input

TC
0 1 2 3 4 5 6 7 8 9

• Output

TC
[0, 2, 4, 6, 8]

The algorithm above iterates over every element of the array and, whenever the index is even, extracts that value into a new array which it then returns.

This algorithm consists of scanning and insertion.

• Scanning: $N$ elements
• Insertion: $N / 2$ elements

In other words, the exact time complexity of the algorithm above is $O(1.5N)$, but as mentioned above, since constants are ignored, it's expressed as $O(N)$.

Let's optimize the algorithm above a bit further.

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/23/about-algorithm-chapter05/">빅 오를 사용하거나 사용하지 않는 코드 최적화</a>
 * @since 2021.07.23 Fri 22:51:52
 */
public class ImproveHalfArray
{
	/**
	 * 메인 함수
	 *
	 * @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();
		
		int[] result = solve(array);
		
		writer.write(Arrays.toString(result));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 알고리즘 결과 반환 함수
	 *
	 * @param array: [int[]] 대상 배열
	 *
	 * @return [int[]] 결과 배열
	 */
	private static int[] solve(int[] array)
	{
		int length = (int) Math.ceil(array.length / 2D);
		
		int[] result = new int[length];
		
		int count = 0;
		
		for (int i = 0; i < array.length; i += 2)
		{
			result[count] = array[i];
			
			count++;
		}
		
		return result;
	}
}

• Input

TC
0 1 2 3 4 5 6 7 8 9

• Output

TC
[0, 2, 4, 6, 8]

The algorithm above is an improved version of the for loop in the solve method.

JAVA
for (int i = 0; i < array.length; i += 2)
{
	result[count] = array[i];
	
	count++;
}

Instead of scanning each element one by one to determine whether its index is even, it scans only even indices from the start and inserts directly. In other words, scanning work is reduced by 50%.

• Scanning: $N / 2$ elements
• Insertion: $N / 2$ elements

This algorithm has a genuine time complexity of $O(N)$. Strictly speaking, the algorithm below has better performance, but from a time-complexity standpoint, both are identical.

Even with identical time complexity, when the amount of data is enormous, the algorithm below would be more suitable.

The main points covered in this chapter are as follows.

• Because Big O notation takes a pessimistic perspective, it ignores constants in time complexity.
• Even with identical time complexity, actual performance can differ meaningfully.

Every so often, when meeting various people, you run into someone who always looks at life from a negative perspective. If Big O notation were personified, I imagine it would be exactly this kind of person.

Sometimes viewing things negatively is useful, but "always" doesn't hold universally. There are countless perspectives in the world, and algorithms are no exception. Fortunately, in reality, most things fall within the range of the ordinary.

In the next chapter, let's step away from the negative perspective and spend some time looking at things from an average perspective instead.