マージ ソートは挿入ソートよりも高速に実行されることは周知の事実です。使用する 漸近分析 。マージ ソートの実行時間は O(nlogn) で、挿入ソートの実行時間は O(n^2) であることが証明できます。これは明らかです。挿入ソートが増分アプローチに従うのに対し、マージ ソートは問題を再帰的に解決する分割統治アプローチを使用するからです。時間計算量の分析をさらに詳しく調べてみると、挿入ソートはそれほど悪くないことがわかります。驚くべきことに、より小さい入力サイズでは挿入ソートがマージソートよりも優れています。これは、時間計算量を推定する際に無視する定数がほとんどないためです。 10^4 程度の大きな入力サイズでは、これは関数の動作に影響しません。ただし、入力サイズが 40 未満などの場合、方程式内の定数が入力サイズ「n」を支配します。ここまでは順調ですね。しかし、私はそのような数学的分析に満足していませんでした。コンピューターサイエンスの学部生として、私たちはコードを書くことに自信を持っていなければなりません。さまざまな入力サイズに対してアルゴリズムがどのように競合するかを理解するために、C プログラムを作成しました。また、これらの並べ替えアルゴリズムの実行時間の複雑さを確立するために、なぜこのような厳密な数学的分析が行われるのかも説明します。
Javaカウンター
実装：
CPP#include
import java.util.Scanner; import java.util.Arrays; import java.util.Random; public class SortingAlgorithms { // Maximum element in array static final int MAX_ELEMENT_IN_ARRAY = 1000000001; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); for (int i = 0; i < t; i++) { int size = scanner.nextInt(); int num_of_times = scanner.nextInt(); testSortingRuntimes(size num_of_times); } scanner.close(); } static int[] generateRandomArray(int n) { // Generate an array of n random integers. int[] arr = new int[n]; Random random = new Random(); for (int i = 0; i < n; i++) { arr[i] = random.nextInt(MAX_ELEMENT_IN_ARRAY); } return arr; } static void insertionSortAsc(int[] a int start int end) { // Perform an in-place insertion sort on a from start to end. for (int i = start + 1; i <= end; i++) { int key = a[i]; int j = i - 1; while (j >= start && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } } static void merge(int[] a int start int end int mid) { // Merge two sorted sublists of a. // The first sublist is a[start:mid+1] and the second sublist is a[mid+1:end+1]. int[] aux = new int[end - start + 1]; int i = start j = mid + 1 k = 0; while (i <= mid && j <= end) { if (a[i] <= a[j]) { aux[k++] = a[i++]; } else { aux[k++] = a[j++]; } } while (i <= mid) { aux[k++] = a[i++]; } while (j <= end) { aux[k++] = a[j++]; } System.arraycopy(aux 0 a start aux.length); } static void mergeSort(int[] a) { // Perform an in-place merge sort on a. mergeSortHelper(a 0 a.length - 1); } static void mergeSortHelper(int[] a int start int end) { // Recursive merge sort function. if (start < end) { int mid = start + (end - start) / 2; mergeSortHelper(a start mid); mergeSortHelper(a mid + 1 end); merge(a start end mid); } } static void insertionAndMergeSortCombine(int[] a int start int end int k) { /* Perform an in-place sort on a from start to end. If the size of the list is less than or equal to k use insertion sort. Otherwise use merge sort. */ if (start < end) { int size = end - start + 1; if (size <= k) { insertionSortAsc(a start end); } else { int mid = start + (end - start) / 2; insertionAndMergeSortCombine(a start mid k); insertionAndMergeSortCombine(a mid + 1 end k); merge(a start end mid); } } } static void testSortingRuntimes(int size int num_of_times) { // Test the runtime of the sorting algorithms. double insertionSortTime = 0; double mergeSortTime = 0; double mergeSortAndInsertionSortMixTime = 0; double qsortTime = 0; for (int i = 0; i < num_of_times; i++) { int[] a = generateRandomArray(size); int[] b = Arrays.copyOf(a a.length); long start = System.currentTimeMillis(); insertionSortAsc(b 0 b.length - 1); long end = System.currentTimeMillis(); insertionSortTime += end - start; int[] c = Arrays.copyOf(a a.length); start = System.currentTimeMillis(); mergeSort(c); end = System.currentTimeMillis(); mergeSortTime += end - start; int[] d = Arrays.copyOf(a a.length); start = System.currentTimeMillis(); insertionAndMergeSortCombine(d 0 d.length - 1 40); end = System.currentTimeMillis(); mergeSortAndInsertionSortMixTime += end - start; int[] e = Arrays.copyOf(a a.length); start = System.currentTimeMillis(); Arrays.sort(e); end = System.currentTimeMillis(); qsortTime += end - start; } insertionSortTime /= num_of_times; mergeSortTime /= num_of_times; mergeSortAndInsertionSortMixTime /= num_of_times; qsortTime /= num_of_times; System.out.println('nTime taken to sort:n' + '(i) Insertion sort: ' + insertionSortTime + 'n' + '(ii) Merge sort: ' + mergeSortTime + 'n' + '(iii) Insertion-mergesort-hybrid: ' + mergeSortAndInsertionSortMixTime + 'n' + '(iv) Qsort library function: ' + qsortTime + 'n'); } }
import time import random import copy from typing import List # Maximum element in array MAX_ELEMENT_IN_ARRAY = 1000000001 def generate_random_array(n: int) -> List[int]: #Generate a list of n random integers. return [random.randint(0 MAX_ELEMENT_IN_ARRAY) for _ in range(n)] def insertion_sort_asc(a: List[int] start: int end: int) -> None: #Perform an in-place insertion sort on a from start to end. for i in range(start + 1 end + 1): key = a[i] j = i - 1 while j >= start and a[j] > key: a[j + 1] = a[j] j -= 1 a[j + 1] = key def merge(a: List[int] start: int end: int mid: int) -> None: #Merge two sorted sublists of a. #The first sublist is a[start:mid+1] and the second sublist is a[mid+1:end+1]. aux = [] i = start j = mid + 1 while i <= mid and j <= end: if a[i] <= a[j]: aux.append(a[i]) i += 1 else: aux.append(a[j]) j += 1 while i <= mid: aux.append(a[i]) i += 1 while j <= end: aux.append(a[j]) j += 1 a[start:end+1] = aux def _merge_sort(a: List[int] start: int end: int) -> None: #Recursive merge sort function. if start < end: mid = start + (end - start) // 2 _merge_sort(a start mid) _merge_sort(a mid + 1 end) merge(a start end mid) def merge_sort(a: List[int]) -> None: #Perform an in-place merge sort on a. _merge_sort(a 0 len(a) - 1) def insertion_and_merge_sort_combine(a: List[int] start: int end: int k: int) -> None: ''' Perform an in-place sort on a from start to end. If the size of the list is less than or equal to k use insertion sort. Otherwise use merge sort. ''' if start < end: size = end - start + 1 if size <= k: insertion_sort_asc(a start end) else: mid = start + (end - start) // 2 insertion_and_merge_sort_combine(a start mid k) insertion_and_merge_sort_combine(a mid + 1 end k) merge(a start end mid) def test_sorting_runtimes(size: int num_of_times: int) -> None: #Test the runtime of the sorting algorithms. insertion_sort_time = 0 merge_sort_time = 0 merge_sort_and_insertion_sort_mix_time = 0 qsort_time = 0 for _ in range(num_of_times): a = generate_random_array(size) b = copy.deepcopy(a) start = time.time() insertion_sort_asc(b 0 len(b) - 1) end = time.time() insertion_sort_time += end - start c = copy.deepcopy(a) start = time.time() merge_sort(c) end = time.time() merge_sort_time += end - start d = copy.deepcopy(a) start = time.time() insertion_and_merge_sort_combine(d 0 len(d) - 1 40) end = time.time() merge_sort_and_insertion_sort_mix_time += end - start start = time.time() a.sort() end = time.time() qsort_time += end - start insertion_sort_time /= num_of_times merge_sort_time /= num_of_times merge_sort_and_insertion_sort_mix_time /= num_of_times qsort_time /= num_of_times print(f'nTime taken to sort:n' f'(i)Insertion sort: {insertion_sort_time}n' f'(ii)Merge sort: {merge_sort_time}n' f'(iii)Insertion-mergesort-hybrid: {merge_sort_and_insertion_sort_mix_time}n' f'(iv)Qsort library function: {qsort_time}n') def main() -> None: t = int(input()) for _ in range(t): size num_of_times = map(int input().split()) test_sorting_runtimes(size num_of_times) if __name__ == '__main__': main()
// Importing required modules const { performance } = require('perf_hooks'); // Maximum element in array const MAX_ELEMENT_IN_ARRAY = 1000000001; // Function to generate a list of n random integers function generateRandomArray(n) { return Array.from({length: n} () => Math.floor(Math.random() * MAX_ELEMENT_IN_ARRAY)); } // Function to perform an in-place insertion sort on a from start to end function insertionSortAsc(a start end) { for (let i = start + 1; i <= end; i++) { let key = a[i]; let j = i - 1; while (j >= start && a[j] > key) { a[j + 1] = a[j]; j -= 1; } a[j + 1] = key; } } // Function to merge two sorted sublists of a function merge(a start end mid) { let aux = []; let i = start; let j = mid + 1; while (i <= mid && j <= end) { if (a[i] <= a[j]) { aux.push(a[i]); i += 1; } else { aux.push(a[j]); j += 1; } } while (i <= mid) { aux.push(a[i]); i += 1; } while (j <= end) { aux.push(a[j]); j += 1; } for (let i = start; i <= end; i++) { a[i] = aux[i - start]; } } // Recursive merge sort function function _mergeSort(a start end) { if (start < end) { let mid = start + Math.floor((end - start) / 2); _mergeSort(a start mid); _mergeSort(a mid + 1 end); merge(a start end mid); } } // Function to perform an in-place merge sort on a function mergeSort(a) { _mergeSort(a 0 a.length - 1); } // Function to perform an in-place sort on a from start to end function insertionAndMergeSortCombine(a start end k) { if (start < end) { let size = end - start + 1; if (size <= k) { insertionSortAsc(a start end); } else { let mid = start + Math.floor((end - start) / 2); insertionAndMergeSortCombine(a start mid k); insertionAndMergeSortCombine(a mid + 1 end k); merge(a start end mid); } } } // Function to test the runtime of the sorting algorithms function testSortingRuntimes(size numOfTimes) { let insertionSortTime = 0; let mergeSortTime = 0; let mergeSortAndInsertionSortMixTime = 0; let qsortTime = 0; for (let _ = 0; _ < numOfTimes; _++) { let a = generateRandomArray(size); let b = [...a]; let start = performance.now(); insertionSortAsc(b 0 b.length - 1); let end = performance.now(); insertionSortTime += end - start; let c = [...a]; start = performance.now(); mergeSort(c); end = performance.now(); mergeSortTime += end - start; let d = [...a]; start = performance.now(); insertionAndMergeSortCombine(d 0 d.length - 1 40); end = performance.now(); mergeSortAndInsertionSortMixTime += end - start; start = performance.now(); a.sort((a b) => a - b); end = performance.now(); qsortTime += end - start; } insertionSortTime /= numOfTimes; mergeSortTime /= numOfTimes; mergeSortAndInsertionSortMixTime /= numOfTimes; qsortTime /= numOfTimes; console.log(`nTime taken to sort:n(i)Insertion sort: ${insertionSortTime}n(ii)Merge sort: ${mergeSortTime}n(iii)Insertion-mergesort-hybrid: ${mergeSortAndInsertionSortMixTime}n(iv)Qsort library function: ${qsortTime}n`); } // Main function function main() { let t = parseInt(prompt('Enter the number of test cases: ')); for (let _ = 0; _ < t; _++) { let size = parseInt(prompt('Enter the size of the array: ')); let numOfTimes = parseInt(prompt('Enter the number of times to run the test: ')); testSortingRuntimes(size numOfTimes); } } // Call the main function main();
次のアルゴリズムの実行時間を比較しました。
Javaの部分文字列の例
- 挿入ソート : 変更や最適化を行わない従来のアルゴリズム。入力サイズが小さい場合に非常に優れたパフォーマンスを発揮します。そしてはい、マージソートに勝ります
- 運命が進む : 分割統治アプローチに従います。 10^5 程度の入力サイズの場合、このアルゴリズムは正しい選択です。このような大きな入力サイズでは、挿入ソートは非実用的になります。
- 挿入ソートとマージソートを組み合わせたバージョン: マージ ソートのロジックを少し調整して、入力サイズが小さい場合の実行時間を大幅に改善しました。ご存知のとおり、マージ ソートは、要素の並べ替えが十分に簡単になるまで、入力を 2 つの半分に分割します。ただし、入力サイズが「n」などのしきい値を下回った場合< 40 then this hybrid algorithm makes a call to traditional insertion sort procedure. From the fact that insertion sort runs faster on smaller inputs and merge sort runs faster on larger inputs this algorithm makes best use both the worlds.
- クイックソート: この手順は実装していません。これは、 で使用できるライブラリ関数 qsort() です。実装の意義を知るためにこのアルゴリズムを考えてみました。ステップ数を最小限に抑え、基礎となる言語プリミティブを最大限に活用してアルゴリズムを最適な方法で実装するには、多大なプログラミングの専門知識が必要です。これが、ライブラリ関数の使用が推奨される主な理由です。これらはあらゆるものを処理できるように書かれています。可能な限り最大限に最適化されます。そして忘れないうちに、私の分析から qsort() は事実上あらゆる入力サイズで非常に高速に実行されます。
分析:
- 入力： ユーザーは、テスト ケースの数に対応するアルゴリズムをテストする回数を指定する必要があります。各テスト ケースについて、ユーザーは入力サイズ「n」を示す 2 つのスペースで区切られた整数と、分析を実行して平均を取得する回数を示す「num_of_times」を入力する必要があります。 (明確化: 「num_of_times」が 10 の場合、上記で指定された各アルゴリズムは 10 回実行され、平均がとられます。これは、指定した入力サイズに対応して入力配列がランダムに生成されるためです。入力配列はすべてソートされる可能性があります。最悪の場合、つまり降順に対応する可能性があります。そのような入力配列の実行時間を回避するため。アルゴリズムは「num_of_times」で実行され、平均がとられます。) CLOCKS_PER_SEC マクロは、所要時間を測定するために使用されます。コンパイル: 上記のコードは Linux 環境 (Ubuntu 16.04 LTS) で作成しました。上記のコード スニペットをコピーします。指定どおりに入力で gcc キーを使用してコンパイルし、ソート アルゴリズムのパワーに感心してください。
- 結果： ご覧のとおり、入力サイズが小さい場合、挿入ソートはマージ ソートよりも 2 * 10^-6 秒速くなります。しかし、この時間の差はそれほど重要ではありません。一方、ハイブリッド アルゴリズムと qsort() ライブラリ関数はどちらも挿入ソートと同等のパフォーマンスを発揮します。
入力サイズは、n = 30 から n = 1000 まで約 100 倍に増加しました。その違いは明らかです。マージ ソートは挿入ソートより 10 倍高速に実行されます。ここでも、ハイブリッド アルゴリズムのパフォーマンスと qsort() ルーチンの間には関係があります。これは、qsort() がハイブリッド アルゴリズムと多かれ少なかれ似た方法で実装されていること、つまり、異なるアルゴリズムを切り替えて最大限に活用していることを示唆しています。
最後に、入力サイズが 10^5 (100 万!) に増加しました。これは、おそらく実際のシナリオで使用される理想的なサイズです。前の入力 n = 1000 と比較すると、マージ ソートが挿入ソートよりも 10 倍高速に実行されるため、この違いはさらに顕著になります。マージソートは挿入ソートよりも 100 倍も優れています。実際、私たちが作成したハイブリッド アルゴリズムは、従来のマージ ソートよりも 0.01 秒速く実行されます。そして最後の qsort() ライブラリ関数は、実行時間を 3 ミリ秒高速化することで実行時間を綿密に測定しながら、実装も重要な役割を果たしていることをついに証明しました。 :D
注: 大量の計算能力を必要とするため、上記のプログラムを n >= 10^6 で実行しないでください。ありがとうございます。コーディングを楽しんでください。 :)
クイズの作成