Algorithm

Sorting and Searching

排序與堆疊 (Sorting and Searching)

常見的排序演算法

泡泡排序法 (Bubble Sort)








完成第一輪泡泡排序



完成第二輪泡泡排序
完成泡泡排序

Bubble Sort Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
<?php

namespace App\BubbleSort;

class Program
{
	public function sort(array $unsortedItems): array
	{
		$firstIndex = 0;
		$lastIndex = count($unsortedItems) - 1;

		for ($j = $lastIndex; $j > $firstIndex; $j--) {
			for ($i = $lastIndex; $i > $firstIndex; $i--) {
				if ($unsortedItems[$i] < $unsortedItems[$i - 1]) {
					$unsortedItems = $this->swap($unsortedItems, $i, $i - 1);
				}
			}
		}

		$result = $unsortedItems;
		return $result;
	}

	private function swap(array $unsortedItems, int $i, int $j): array
	{
		$itemA = $unsortedItems[$i];
		$itemB = $unsortedItems[$j];

		$unsortedItems[$j] = $itemA;
		$unsortedItems[$i] = $itemB;

		return $unsortedItems;
	}
}
  • Time Complexity: $O(n^2)$

選擇排序法 (Selection Sort)


挑選出最小的值
將它與第一個位置交換，完成第一輪選擇排序
從剩下的位置，挑選出最小值
將它與第二個位置交換，完成第二輪選擇排序
完成選擇排序

Selection Sort Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
<?php

namespace App\SelectionSort;

class Program
{
	public function sort(array $unsortedItems): array
	{
		$itemCount = count($unsortedItems);

		for ($i = 0; $i < $itemCount - 1; $i++) {
			$minInfo = $this->findMin($unsortedItems, $i);

			$unsortedItems = $this->swap($unsortedItems, $i, $minInfo);
		}

		return $unsortedItems;
	}

	private function findMin(array $unsortedItems, int $currentIndex): array
	{
		$sliceItems = array_slice($unsortedItems, $currentIndex);

		$min = min($sliceItems);
		$minKey = array_keys($unsortedItems, min($sliceItems))[0];

		return [
			'value' => $min,
			'key' => $minKey,
		];
	}

	private function swap(array $unsortedItems, int $currentIndex, array $minInfo): array
	{
		$itemA = $unsortedItems[$currentIndex];
		$itemB = $minInfo['value'];

		$unsortedItems[$currentIndex] = $itemB;
		$unsortedItems[$minInfo['key']] = $itemA;

		return $unsortedItems;
	}
}

  • Time Complexity: $O(n^2)$

合併排序法 (Merge Sort)

  • Time Complexity: $O(nlog(n))$


先將每個值分組
兩兩比較，較小的放前面，組出新的組合，完成第一輪合併排序
接著比較兩組中第一個值，較小者為新組合的第一個值
持續比較
完成第二輪合併排序
完成合併排序

Merge Sort Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
<?php

namespace App\MergeSort;

class Program
{
    public function sort(array $unsortedItems): array
    {
        $container = $this->initContainer($unsortedItems);

        while (count($container) > 1) {
            $firstArray = array_shift($container);
            $secondArray = array_shift($container);

            $merged = $this->mergeToOne($firstArray, $secondArray);

            $container[] = $merged;
        }

        $result = $container[0];

        return $result;
    }

    private function mergeToOne(array $firstArray, array $secondArray = []): array
    {
        $result = [];

        $firstArrayItem = null;
        $secondArrayItem = null;

        while (count($firstArray) > 0 && count($secondArray) > 0) {
            if (is_null($firstArrayItem)) {
                $firstArrayItem = $firstArray[0];
            }

            if (is_null($secondArrayItem)) {
                $secondArrayItem = $secondArray[0];
            }

            if ($firstArrayItem <= $secondArrayItem) {
                $result[] = $firstArrayItem;
                array_shift($firstArray);
                $firstArrayItem = null;
            } else {
                $result[] = $secondArrayItem;
                array_shift($secondArray);
                $secondArrayItem = null;
            }
            continue;
        }

        if (count($firstArray) > 0) {
            $result = array_merge($result, $firstArray);
        }

        if (count($secondArray) > 0) {
            $result = array_merge($result, $secondArray);
        }

        return $result;
    }

    private function initContainer(array $unsortedItems): array
    {
        $result = [];

        foreach ($unsortedItems as $unsortedItem) {
            $result[] = [$unsortedItem];
        }

        return $result;
    }
}

快速排序法 (Quick Sort)

  • Time Complexity: $O(nlog(n))$
  • Worst Time Complexity: $O(n^2)$

使用分治法(Divide and Conquer)的概念。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 原始資料
40 60 50 20 10 30

// 選擇最左邊的資料為基準點
[40] 60 50 20 10 30

// 60 > 40，要移到40的右邊
[40] 60 50 20 10 30
     ^

// 50 > 40，要移到40的右邊
[40] 60 50 20 10 30
        ^

// 20 < 40，要移到40的左邊
[40] 60 50 20 10 30
           ^
20 [40] 60 50 10 30

// 10 < 40，要移到40的左邊
20 [40] 60 50 10 30
              ^
20 10 [40] 60 50 30

// 同理30 < 40，要移到40的左邊
20 10 [40] 60 50 30
                 ^
20 10 30 [40] 60 50

// 第一次排序完成
20 10 30 40 60 50

// 接著排序40左右兩側的資料
// 先排左側資料，同樣選擇最左邊的資料為基準點
// 左側基準點為20
[20] 10 30 40 60 50

// 左側資料排序完成
10 [20] 30 40 60 50

// 接著排序右側資料，一樣選擇最左邊的資料為基準點
// 右側基準點為60
10 20 30 40 [60] 50

//右側排序完成
10 20 30 40 50 [60]

//排序結果
10 20 30 40 50 60

Quick Sort Implementation (version 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<?php

namespace App\QuickSort;

class Program
{
    public function sort(array $unsortedSortItems): array
    {
        if (count($unsortedSortItems) <= 1) {
            return $unsortedSortItems;
        }

        $pivot = array_shift($unsortedSortItems);

        $left = [];
        $right = [];
        foreach ($unsortedSortItems as $unsortedSortItem) {
            if ($unsortedSortItem <= $pivot) {
                $left[] = $unsortedSortItem;
            } else {
                $right[] = $unsortedSortItem;
            }
        }

        return array_merge($this->sort($left), [$pivot], $this->sort($right));
    }
}

基數排序 (Radix Sort)

  • Time Complexity: $O(nk)$

基數排序利用整數有限位元這個條件，迭代數字的每一位數，對每一位數分群。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 原始資料
101 20 50 1 37

// 先對個位數來分群
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| 20|101|   |   |   |   |   | 37|   |
| 50| 1 |   |   |   |   |   |   |   |

//得到照個位數的排序
20 50 101 1 37

// 接著對十位數來分群
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|101|   | 20| 37|   | 50|   |   |   |
| 1 |   |   |   |   |   |   |   |   |

//得到照十位數的排序
101 1 20 37 50

//最後照百位數分群
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| 1 |101|   |   |   |   |   |   |   |
| 20 |   |   |   |   |   |   |   |   |
| 37 |   |   |   |   |   |   |   |   |
| 50 |   |   |   |   |   |   |   |   |

//排序結果
1 20 37 50 101

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
<?php

namespace App\RadixSort;

class Program
{
    public function sort(array $unsortedItems): array
    {
        if (count($unsortedItems) <= 1) {
            return $unsortedItems;
        }

        $max = max($unsortedItems);

        $numberOfDigits = count(str_split($max, 1));

        $unsortedItems = $this->convertToStringWithZero($unsortedItems, $numberOfDigits);
        $grouped = $this->emptyGroup();

        foreach ($unsortedItems as $unsortedItem) {
            $number = $unsortedItem % 10;
            $grouped[$number][] = $unsortedItem;
        }

        if ($numberOfDigits == 1) {
            return $this->flatten($grouped);
        }

        for ($digit = 2; $digit <= $numberOfDigits; $digit++) {
            $grouped = $this->sortByDigitNumber($grouped, $digit);
        }

        return $this->flatten($grouped);
    }

    /**
     * @param array $unsortedItems
     * @param int $numberOfDigits
     * @return array
     */
    private function convertToStringWithZero(array $unsortedItems, int $numberOfDigits): array
    {
        $result = [];
        foreach ($unsortedItems as $unsortedItem) {
            $unsortedItemsWithZero = str_pad($unsortedItem, $numberOfDigits, '0', STR_PAD_LEFT);
            $result[] = $unsortedItemsWithZero;
        }

        return $result;
    }

    private function emptyGroup(): array
    {
        return [
            0 => [],
            1 => [],
            2 => [],
            3 => [],
            4 => [],
            5 => [],
            6 => [],
            7 => [],
            8 => [],
            9 => [],
        ];
    }

    private function flatten(array $grouped): array
    {
        $result = [];

        foreach ($grouped as $number => $items) {
            foreach ($items as $item) {
                $result[] = (int)$item;
            }
        }

        return $result;
    }

    private function sortByDigitNumber(array $grouped, int $digit): array
    {
        $result = $this->emptyGroup();
        $flatten = $this->flatten($grouped);

        foreach ($flatten as $item) {
            $number = $this->getCurrentDigitNumber($item, $digit);
            $result[$number][] = $item;
        }

        return $result;
    }

    public function getCurrentDigitNumber(int $item, int $digit): int
    {
        $digitNumber = $item % 10;

        if ($digit == 1) {
            return $digitNumber;
        }

        for ($i = 2; $i <= $digit; $i++) {
            $item = ($item - ($item % 10)) / 10;
            $digitNumber = $item % 10;
        }

        return $digitNumber;
    }

}

搜尋演算法

面試題目

10.1 Sorted Merge

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

(Hints.)
由陣列後面插入比較好，因為有空位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
<?php

class SortedMerge
{
    public static function merge(array &$a, array &$b)
    {
        $indexA = self::getLastElementIndex($a);
        $indexB = self::getLastElementIndex($b);

        $indexMerged = count($a) - 1;

        while ($indexB >= 0) {
            if ($indexA >= 0 && $a[$indexA] > $b[$indexB]) {
                $a[$indexMerged] = $a[$indexA];
                $indexA--;
            } else {
                $a[$indexMerged] = $b[$indexB];
                $indexB--;
            }
            $indexMerged--;
        }
    }

    public static function getLastElementIndex(array $array): int
    {
        $result = -1;
        foreach ($array as $value) {
            if (is_null($value)) {
                break;
            }
            $result++;
        }

        return $result;
    }
}

10.2 Group Anagrams

Write a method to sort an array of strings so that all the anagrams are next to each other.

anagrams (易位構詞遊戲): 是將組成一個詞或短句的字母重新排列順序，所有字母的都被使用一次，構造出一些新的詞或短句。

example:

  • “earth” <—> “heart”
  • “eleven plus two” <—> “twelve plus one”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
<?php

class AnagramGrouper
{

    public function groupAnagrams(array $words)
    {
        $result = [];

        foreach ($words as $index => $word) {
            if (!isset($words[$index])) {
                continue;
            }
            $divides = self::divideIntoGroups($words, $index);

            $sameGroupwords = $divides['same_group_words'];
            $result = array_merge($result, $sameGroupwords);

            $sameGroupwordIndexes = $divides['same_group_word_indexes'];
            foreach ($sameGroupwordIndexes as $sameGroupwordIndex) {
                unset($words[$sameGroupwordIndex]);
            }
        }

        return $result;
    }

    private function divideIntoGroups(array $words, int $targetIndex): array
    {
        $sameGroupwords = [];
        $sameGroupwordIndexes = [];

        $targetWord = $words[$targetIndex];
        $targetCharacterCounts = $this->getCharacterCounts($targetWord);

        foreach ($words as $index => $currentWord) {
            if ($index == $targetIndex) {
                $sameGroupwords[] = $targetWord;
                $sameGroupwordIndexes[] = $index;
                continue;
            }

            $currentCharacterCounts = $this->getCharacterCounts($currentWord);

            if ($currentCharacterCounts == $targetCharacterCounts) {
                $sameGroupwords[] = $currentWord;
                $sameGroupwordIndexes[] = $index;
            }
        }

        return [
            'same_group_words' => $sameGroupwords,
            'same_group_word_indexes' => $sameGroupwordIndexes,
        ];
    }

    private function initCharcterCounts(): array
    {
        return [
            'a' => 0, 'b' => 0, 'c' => 0, 'd' => 0, 'e' => 0, 'f' => 0,
            'g' => 0, 'h' => 0, 'i' => 0, 'j' => 0, 'k' => 0, 'l' => 0,
            'm' => 0, 'n' => 0, 'o' => 0, 'p' => 0, 'q' => 0, 'r' => 0,
            's' => 0, 't' => 0, 'u' => 0, 'v' => 0, 'w' => 0, 'x' => 0,
            'y' => 0, 'z' => 0
        ];
    }

    private function getCharacterCounts(string $word): array
    {
        $charcterCounts = $this->initCharcterCounts();
        $characters = str_split($word);

        foreach ($characters as $character) {
            $charcterCounts[$character]++;
        }

        return $charcterCounts;
    }
}

10.3 Search in Rotated Array

Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.

1
2
3
4
5
6
[1,2,3,4,5,6]
[6,1,2,3,4,5]
[5,6,1,2,3,4]
[4,5,6,1,2,3]
[3,4,5,6,1,2]
[2,3,4,5,6,1]

思路:

  1. 從小至大排列的旋轉，至少有一側排序是對的。
  2. 若目標在排序正確的一側，則binary search。
    若目標在另一側，則繼續從另一側搜尋。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
<?php

class SearchedInRotatedArray
{
	const ITEM_NOT_FOUND = -1;

	public function search(array $items, int $target, ?int $left = null, ?int $right = null): int
	{
		$originalItemsCount = count($items);

		if ($originalItemsCount == 0) {
			return self::ITEM_NOT_FOUND;
		}

		if ($originalItemsCount == 1) {
			return ($items[0] == $target)
				? 0
				: self::ITEM_NOT_FOUND;
		}

		if (is_null($left)) {
			$left = 0;
		}

		if (is_null($right)) {
			$right = $originalItemsCount - 1;
		}

		$mid = (int)floor(($left + $right) / 2);

		if ($mid < 0) {
			return self::ITEM_NOT_FOUND;
		}

		if ($items[$mid] == $target) {
			return $mid;
		}

		if ($items[$left] == $target) {
			return $left;
		}

		if ($items[$right] == $target) {
			return $right;
		}

		$isLeftSorted = ($items[$left] <= $items[$mid])
			? true
			: false;

		$isRightSorted = ($items[$mid] <= $items[$right])
			? true
			: false;

		if (
			($items[$left] < $target) &&
			($target < $items[$mid]) &&
			$isLeftSorted
		) {
			return $this->binarySearch($items, $target, $left, $mid);
		}

		if (
			($items[$mid] < $target) &&
			($target < $items[$right]) &&
			$isRightSorted
		) {
			return $this->binarySearch($items, $target, $mid, $right);
		}

		if ($isLeftSorted) {
			return $this->search($items, $target, $mid, $right - 1);
		}

		if ($isRightSorted) {
			return $this->search($items, $target, $left, $mid - 1);
		}

		return self::ITEM_NOT_FOUND;
	}

	private function binarySearch(array $items, int $target, int $left, int $right): int
	{
		$originalItemsCount = count($items);

		if ($originalItemsCount == 0) {
			return self::ITEM_NOT_FOUND;
		}

		if ($originalItemsCount == 1) {
			return ($items[0] == $target)
				? 0
				: self::ITEM_NOT_FOUND;
		}

		$mid = (int)floor(($left + $right) / 2);

		if ($items[$mid] == $target) {
			return $mid;
		}

		if ($items[$left] == $target) {
			return $left;
		}

		if ($items[$right] == $target) {
			return $right;
		}

		if ($items[$mid] > $target) {
			return $this->binarySearch($items, $target, $left, $mid);
		} else {
			return $this->binarySearch($items, $target, $mid, $right);
		}
	}
}

10.4 Sorted Search, No Size

You are given an array like data structure Listy which lacks a size method. It does, however, have an elementAt(i) method that returns the element at index i in 0(1) time. If i is beyond the bounds of the data structure, it returns -1. (For this reason, the data structure only supports positive integers.) Given a Listy which contains sorted, positive integers, find the index at which an element x occurs. If x occurs multiple times, you may return any index.

思路:

  1. 先找出Listy大概的長度 (利用指數加大的方式)。
  2. 接著使用二元搜尋。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
<?php

class Listy
{
	protected array $items;

	const ITEM_NOT_FOUND = -1;

	public function __construct(array $items)
	{
		$this->items = $items;
	}

	public function elementAt(int $index): int
	{
		$result = self::ITEM_NOT_FOUND;

		if (isset($this->items[$index])) {
			return $this->items[$index];
		}

		return $result;
	}
}

class SortedSearchNoSize
{
	protected Listy $listy;

	const ITEM_NOT_FOUND = -1;

	public function __construct(Listy $listy)
	{
		$this->listy = $listy;
	}

	public function search(int $target): int
	{
		$firstItem = $this->listy->elementAt(0);
		if ($firstItem == self::ITEM_NOT_FOUND) {
			return self::ITEM_NOT_FOUND;
		}

		if ($firstItem == $target) {
			return 0;
		}

		$index = 1;
		while ($this->listy->elementAt($index) != self::ITEM_NOT_FOUND) {
			$index = $index * 2;
		}

		return $this->binarySearch($target, 0, $index);
	}

	private function binarySearch(int $target, int $left, int $right): int
	{
		while ($left <= $right) {
			$mid = (int)floor(($left + $right) / 2);
			$midValue = $this->listy->elementAt($mid);

			if ($midValue > $target || $midValue == -1) {
				$right = $mid - 1;
			} else if ($midValue < $target) {
				$left = $mid + 1;
			} else {
				return $mid;
			}
		}

		return self::ITEM_NOT_FOUND;
	}
}

Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string.

思路:
先找中點附近，不為空的字串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
<?php

class SparseSearch
{
	protected array $items;

	const ITEM_NOT_FOUND = -1;

	public function __construct(array $items)
	{
		$this->items = $items;
	}

	public function search(string $target, ?int $left = null, ?int $right = null): int
	{
		$items = $this->items;

		if (count($items) == 0) {
			return self::ITEM_NOT_FOUND;
		}

		if (count($items) == 1) {
			return ($items[0] == $target)
				? 0
				: self::ITEM_NOT_FOUND;
		}

		if (is_null($left)) {
			$left = 0;
		}

		if (is_null($right)) {
			$right = count($items) - 1;
		}

		if ($left > $right) {
			return self::ITEM_NOT_FOUND;
		}

		$mid = floor(($left + $right) / 2);

		$currentIndex = $mid;
		$currentValue = $items[$mid];

		if ($currentValue == '') {
			$closestNotEmptyPointInfo = $this->findClosestNotEmptyPoint($currentIndex);

			$currentIndex = $closestNotEmptyPointInfo['index'];
			$currentValue = $closestNotEmptyPointInfo['value'];

			if ($currentIndex == self::ITEM_NOT_FOUND) {
				return self::ITEM_NOT_FOUND;
			}
		}

		if ($currentValue == $target) {
			return $currentIndex;
		}

		if ($items[$left] == $target) {
			return $left;
		}

		if ($items[$right] == $target) {
			return $right;
		}

		if (strnatcmp($currentValue, $target) > 0) {
			return $this->search($target, $left, $currentIndex - 1);
		}

		if (strnatcmp($currentValue, $target) < 0) {
			return $this->search($target, $currentIndex, $right - 1);
		}

		return self::ITEM_NOT_FOUND;
	}

	private function findClosestNotEmptyPoint(int $midPointIndex)
	{
		$closestNotEmptyPointIndex = self::ITEM_NOT_FOUND;
		$closestNotEmptyPointValue = '';

		$left = $midPointIndex - 1;
		$right = $midPointIndex + 1;

		while (
			isset($this->items[$left]) ||
			isset($this->items[$right])
		) {
			if (
				isset($this->items[$right]) &&
				$this->items[$right] != ''
			) {
				$closestNotEmptyPointIndex = $right;
				$closestNotEmptyPointValue = $this->items[$closestNotEmptyPointIndex];
				break;
			}

			if (
				isset($this->items[$left]) &&
				$this->items[$left] != ''
			) {
				$closestNotEmptyPointIndex = $left;
				$closestNotEmptyPointValue = $this->items[$closestNotEmptyPointIndex];
				break;
			}

			$right++;
			$left--;

			if ($left > $right) {
				break;
			}
		}

		return [
			'index' => $closestNotEmptyPointIndex,
			'value' => $closestNotEmptyPointValue
		];
	}
}

10.6 Sort Big File

Imagine you have a 20 GB file with one string per line. Explain how you would sort the file.

因限制了20GB的大小，表示不能單純把全部資料帶進記憶體處理。

我們可以將檔案分塊，每一塊獨立排序，存進檔案。

待所有區塊排序後，
再將區塊一塊一塊合併(可透過每次存取第一行的合併排序)，
最終產生完全排序的檔案。

此演算法稱為外排序 (external sort)。

(Reference.)

ʕ •ᴥ•ʔ：排序演算法還有很多，之後有時間再來補充吧！