IP02-12 実践プログラム⑤　整列アルゴリズム　挿入法

項目	変数名	説明
比較回数のカウント	compare_count	比較回数をカウントする。 20行目：compare_count = 0 　# カウント用に0で初期化する 38行目：compare_count = compare_count + 1 　# 比較回数を1カウントアップする 45行目：compare_count = compare_count + 1 　# 52行目：print("比較回数:", compare_count) 　# 比較回数を表示する
移動回数のカウント	move_count	移動回数をカウントする。 21行目：move_count = 0 　# カウント用に0で初期化する 39行目：move_count = move_count + 1 　#移動回数を1カウントアップする 53行目：print("移動回数:", move_count) 　#移動回数を表示する
整列処理時間の計測	start_time end_time	挿入法で並び替えを行う処理を計測する。 25行目：start_time = time.time() 　# 整列処理開始時刻の取得 48行目：end_time = time.time() 　# 整列処理終了時刻の取得 54行目：print("処理時間: {:.6f} 秒".format(end_time - start_time)) 　# 終了時刻 - 開始時刻を計算し、処理時間を求めて表示する

挿入法のプログラム

import random
import time

# 配列をランダムに生成する関数
def generate_array(size, low, high):
    """
    ランダムな整数の配列を生成する
    size : 要素数
    low  : 最小値
    high : 最大値
    """
    return random.sample(range(low, high+1), size)  # 重複なし

# ここから処理を始める
# ランダム配列を生成
data = generate_array(20, 1, 100)  # 配列の作成
print("ソート前:", data)

# 初期化
compare_count = 0  # 比較回数カウント用
move_count = 0     # 移動回数カウント用

n = len(data)      # 配列の要素数を n に代入

# 時間計測用 ソート開始時間の取得
start_time = time.time()

# 挿入法の開始
i = 1 # データの挿入は2番目のデータ(添字1)から始める
while i < n :
    insert_data = data[i]           # 挿入する値を一時保存
    j = i - 1
    # 比較と移動
    while j >= 0 and data[j] > insert_data :
        data[j + 1] = data[j]  # 要素を1つ後ろにずらす（移動）
        j = j - 1
        # カウントアップ
        compare_count = compare_count + 1  # 比較回数のカウントアップ
        move_count = move_count + 1        # 移動回数のカウントアップ
    
    data[j + 1] = insert_data  # 挿入
    i = i + 1
    # カウントアップ
    if j >= 0 : # 比較回数のカウントアップの条件
        compare_count = compare_count + 1  # 比較回数のカウントアップ

# ソート終了時間
end_time = time.time()

# 表示
print("ソート後:", data)
print("比較回数:", compare_count)
print("移動回数:", move_count)
print("処理時間: {:.6f} 秒".format(end_time - start_time))

このプログラムをGoogle Colabで実行した結果を提出してください。

Google Colabのデータをコピーして解答として貼り付けましょう。

ソート前のデータ

比較回数

移動回数

処理時間

2. データの並び方による効率の違いを確認する

挿入法は、「交換法(バブルソート)」、「選択法」と比べ、並べ替え前のデータの並び順が処理時間に大きく関係するアルゴリズムです。

そうなんですか？並べ替えるからどんな順番でも処理時間はあまり変わらないような気がするけれど。

でも、一つの配列で並べ替えるから、移動が少なければ少ないほど速いと思うな。

挿入法は、全くのランダムなデータを並べ替える場合と、ある程度整列されているデータを並べ替える場合で、処理時間が大きく変わります。
どのくらい処理時間が変わるか確認しましょう。

これから次の4種類の500件のデータを昇順に並べ替えます。

1. 降順に並んだデータ
2. 30％整列済みのデータ
3. 50%整列済みのデータ
4. 80%整列済みのデータ

1の降順に並んだデータは、最も移動回数が多くなるケースです。一番処理時間がかかる最悪な並びのデータということになります。

最初に「1. 降順に並んだデータ」を並べ替えて、処理時間を計測します。
その後で、2～4のデータを使ってどのくらい処理時間が変わるか確認します。

課題1

下記の「1. 降順に並んだデータ」を使って挿入法のプログラムを実行してください。

プログラムをコピーしたら、16行目の「data = generate_array(20, 1, 100) # 配列の作成」をコピーした命令に変更してからプログラムを実行してみましょう。

data = [9997, 9976, 9946, 9941, 9934, 9930, 9919, 9909, 9906, 9900, 9896, 9885, 9879, 9868, 9867, 9840, 9830, 9796, 9780, 9766, 9754, 9738, 9733, 9710, 9701, 9692, 9684, 9683, 9682, 9680, 9659, 9633, 9628, 9614, 9609, 9604, 9582, 9578, 9570, 9569, 9565, 9556, 9542, 9541, 9538, 9519, 9518, 9507, 9501, 9497, 9492, 9485, 9482, 9451, 9447, 9442, 9432, 9428, 9423, 9421, 9415, 9406, 9403, 9400, 9382, 9375, 9374, 9370, 9351, 9349, 9315, 9309, 9302, 9294, 9293, 9273, 9265, 9264, 9253, 9247, 9244, 9235, 9232, 9225, 9223, 9221, 9206, 9193, 9187, 9179, 9178, 9173, 9160, 9148, 9127, 9108, 9098, 9085, 9084, 9083, 9073, 9050, 9048, 9033, 9032, 9026, 9022, 9020, 9013, 9003, 8994, 8980, 8967, 8960, 8954, 8953, 8947, 8946, 8905, 8902, 8884, 8878, 8869, 8844, 8804, 8758, 8724, 8718, 8710, 8702, 8699, 8688, 8687, 8684, 8680, 8669, 8665, 8660, 8657, 8641, 8624, 8611, 8601, 8577, 8523, 8512, 8510, 8500, 8494, 8493, 8478, 8464, 8461, 8460, 8458, 8454, 8442, 8439, 8435, 8416, 8402, 8391, 8377, 8368, 8366, 8359, 8356, 8355, 8327, 8318, 8312, 8300, 8298, 8275, 8259, 8258, 8231, 8228, 8209, 8204, 8203, 8196, 8179, 8174, 8108, 8084, 8080, 8047, 8040, 8036, 8029, 8024, 8004, 7983, 7980, 7978, 7956, 7941, 7938, 7928, 7922, 7911, 7898, 7889, 7866, 7848, 7847, 7841, 7835, 7826, 7808, 7780, 7775, 7735, 7727, 7710, 7704, 7680, 7675, 7665, 7590, 7577, 7569, 7558, 7549, 7548, 7541, 7537, 7531, 7505, 7501, 7500, 7497, 7479, 7453, 7452, 7448, 7409, 7399, 7389, 7366, 7355, 7336, 7325, 7323, 7322, 7321, 7310, 7304, 7288, 7278, 7270, 7258, 7256, 7255, 7254, 7247, 7241, 7237, 7232, 7226, 7207, 7202, 7201, 7195, 7194, 7193, 7187, 7158, 7150, 7149, 7139, 7125, 7118, 7102, 7097, 7096, 7088, 7071, 7066, 7059, 7057, 7050, 7040, 7032, 7030, 7026, 7015, 7014, 6998, 6990, 6960, 6954, 6947, 6941, 6927, 6916, 6915, 6902, 6898, 6897, 6887, 6880, 6841, 6833, 6820, 6812, 6804, 6795, 6790, 6787, 6779, 6772, 6769, 6758, 6748, 6738, 6737, 6735, 6726, 6722, 6699, 6691, 6673, 6660, 6646, 6611, 6608, 6607, 6583, 6579, 6566, 6544, 6524, 6523, 6520, 6517, 6509, 6505, 6497, 6494, 6492, 6490, 6476, 6471, 6467, 6451, 6446, 6438, 6429, 6418, 6410, 6373, 6364, 6356, 6355, 6354, 6336, 6321, 6319, 6315, 6313, 6281, 6275, 6257, 6247, 6242, 6238, 6237, 6234, 6226, 6208, 6203, 6183, 6159, 6158, 6148, 6137, 6129, 6125, 6089, 6084, 6081, 6077, 6076, 6075, 6074, 6041, 6038, 6036, 6034, 6026, 6022, 6010, 5993, 5979, 5964, 5962, 5959, 5947, 5934, 5926, 5925, 5919, 5896, 5890, 5885, 5876, 5854, 5842, 5814, 5802, 5792, 5783, 5768, 5762, 5757, 5743, 5736, 5726, 5713, 5698, 5689, 5686, 5680, 5671, 5662, 5661, 5656, 5641, 5638, 5622, 5619, 5584, 5582, 5574, 5563, 5549, 5547, 5532, 5520, 5511, 5510, 5506, 5488, 5473, 5459, 5458, 5448, 5447, 5414, 5412, 5402, 5396, 5381, 5374, 5361, 5336, 5326, 5322, 5308, 5294, 5289, 5278, 5275, 5271, 5263, 5223, 5211, 5204, 5193, 5191, 5184, 5181, 5180, 5178, 5174, 5173, 5151, 5149, 5146, 5122, 5104, 5080, 5077, 5063, 5060, 5056, 5051, 5009, 4989, 4983, 4972, 4970, 4967, 4953, 4947, 4945, 4940, 4938, 4905, 4896, 4885, 4877, 4861, 4857, 4853, 4840, 4839, 4829, 4826, 4817, 4815, 4814, 4779, 4777, 4766, 4761, 4756, 4751, 4743, 4739, 4735, 4723, 4707, 4697, 4695, 4690, 4674, 4672, 4664, 4660, 4639, 4632, 4630, 4628, 4626, 4624, 4619, 4617, 4594, 4561, 4558, 4557, 4533, 4524, 4515, 4509, 4506, 4468, 4459, 4429, 4418, 4414, 4407, 4397, 4385, 4380, 4378, 4361, 4343, 4328, 4319, 4316, 4298, 4296, 4270, 4242, 4215, 4212, 4210, 4175, 4168, 4144, 4136, 4113, 4098, 4089, 4087, 4080, 4077, 4076, 4064, 4055, 4050, 4045, 4040, 4036, 4025, 4013, 4012, 4009, 3999, 3996, 3985, 3981, 3975, 3966, 3943, 3935, 3917, 3911, 3905, 3896, 3894, 3893, 3876, 3866, 3862, 3860, 3859, 3853, 3842, 3835, 3817, 3814, 3811, 3801, 3799, 3789, 3783, 3726, 3720, 3716, 3712, 3699, 3677, 3670, 3652, 3648, 3646, 3636, 3629, 3628, 3622, 3595, 3592, 3585, 3583, 3578, 3577, 3575, 3569, 3565, 3558, 3547, 3535, 3526, 3525, 3522, 3507, 3503, 3500, 3495, 3490, 3471, 3468, 3466, 3439, 3423, 3414, 3412, 3406, 3393, 3378, 3374, 3369, 3356, 3353, 3350, 3335, 3332, 3325, 3308, 3297, 3285, 3282, 3256, 3245, 3234, 3229, 3225, 3221, 3184, 3181, 3174, 3165, 3148, 3147, 3142, 3133, 3116, 3097, 3089, 3069, 3057, 3043, 3042, 3040, 3027, 3021, 3016, 3015, 3000, 2999, 2985, 2981, 2978, 2968, 2960, 2946, 2922, 2917, 2906, 2903, 2862, 2845, 2841, 2834, 2830, 2829, 2827, 2826, 2819, 2810, 2794, 2780, 2770, 2732, 2731, 2722, 2714, 2700, 2688, 2686, 2679, 2677, 2675, 2656, 2643, 2624, 2596, 2578, 2575, 2554, 2553, 2548, 2541, 2537, 2531, 2530, 2519, 2512, 2507, 2491, 2471, 2460, 2457, 2455, 2449, 2441, 2440, 2423, 2415, 2404, 2398, 2397, 2364, 2359, 2358, 2330, 2325, 2310, 2288, 2267, 2255, 2241, 2240, 2221, 2217, 2213, 2208, 2189, 2173, 2169, 2134, 2116, 2100, 2098, 2089, 2066, 2063, 2043, 2024, 2007, 1993, 1989, 1986, 1979, 1961, 1959, 1933, 1931, 1912, 1908, 1900, 1898, 1864, 1850, 1831, 1824, 1803, 1793, 1792, 1790, 1785, 1783, 1776, 1769, 1768, 1764, 1760, 1754, 1740, 1735, 1721, 1717, 1716, 1713, 1699, 1674, 1672, 1669, 1667, 1666, 1650, 1638, 1620, 1597, 1581, 1573, 1571, 1568, 1552, 1537, 1531, 1523, 1460, 1439, 1427, 1422, 1412, 1393, 1389, 1356, 1348, 1339, 1337, 1303, 1265, 1254, 1252, 1249, 1235, 1232, 1229, 1225, 1212, 1211, 1204, 1202, 1198, 1196, 1183, 1149, 1146, 1144, 1122, 1109, 1107, 1086, 1081, 1067, 1063, 1059, 1047, 1046, 1033, 1026, 1022, 1012, 984, 980, 968, 964, 945, 937, 927, 918, 912, 909, 907, 882, 873, 859, 854, 852, 847, 845, 839, 818, 813, 806, 793, 784, 779, 772, 764, 746, 743, 734, 733, 732, 711, 707, 701, 689, 686, 662, 646, 628, 627, 625, 590, 585, 583, 582, 556, 555, 543, 536, 504, 494, 492, 481, 477, 474, 462, 450, 440, 433, 414, 400, 399, 394, 373, 371, 366, 365, 361, 351, 344, 334, 318, 317, 307, 306, 304, 298, 293, 281, 280, 278, 264, 263, 225, 219, 194, 193, 191, 182, 164, 158, 125, 119, 95, 89, 88, 82, 79, 71, 67, 66, 59, 53, 50, 40, 39, 20, 12]

1. 降順に並んだデータの処理時間

課題2

同じデータで30%が並べ替え済みのデータを挿入法で並べ替えます。

ここでは課題1の処理時間と比べてどの程度速くなっているかを調べます。

処理時間の短縮の割合を時間比として次の計算で求めることにします。

時間比 = 処理時間 ÷ 課題1の処理時間

(小数点以下四捨五入)

時間比が「0.5」になれば、2倍速くなって時間は半分に短縮されていることを表します。

以下の30%並べ替え済みのデータを使ったときの処理時間と時間比を求めましょう。

data = [2221, 5686, 2981, 764, 4777, 6902, 4938, 4025, 1229, 8036, 3893, 7040, 4468, 9032, 7448, 6208, 9173, 1674, 806, 66, 6451, 8368, 194, 7847, 7941, 2722, 371, 7590, 1122, 2624, 3811, 1573, 4857, 9896, 847, 2098, 3000, 334, 2241, 9406, 7241, 1225, 366, 1067, 873, 9273, 7911, 2530, 182, 5180, 701, 2089, 7866, 4707, 6947, 3027, 5178, 3406, 504, 2208, 3525, 4743, 1427, 8435, 3720, 6076, 3835, 543, 5473, 6242, 88, 793, 6355, 7088, 2548, 4632, 8047, 8461, 9235, 6089, 5396, 6319, 3466, 4380, 293, 1523, 6410, 4009, 3585, 1716, 6034, 5662, 4989, 8402, 4840, 7270, 4040, 6237, 6471, 3350, 4557, 7577, 4319, 8231, 6915, 8439, 9684, 5713, 6257, 3595, 4136, 12, 6566, 4407, 8493, 9906, 5173, 6373, 6129, 7336, 3814, 5896, 3670, 7097, 6490, 1149, 1183, 9941, 9020, 1202, 7710, 5080, 6446, 590, 5762, 9085, 5563, 7187, 5641, 7548, 1265, 9604, 1337, 9633, 8687, 1356, 6608, 5271, 8688, 2397, 8084, 984, 9780, 5736, 6887, 3308, 6321, 2100, 9179, 6313, 2554, 2830, 8416, 1638, 5698, 4212, 3356, 8454, 4690, 2063, 4697, 5842, 5184, 8510, 7409, 1597, 414, 7479, 1764, 1933, 2700, 9738, 2578, 5768, 5414, 4967, 5174, 6699, 7059, 8458, 4055, 2457, 5993, 6748, 7680, 3325, 1912, 7549, 6726, 3378, 6611, 2173, 8844, 6812, 7558, 909, 6467, 4036, 7194, 2066, 4013, 1740, 9556, 9796, 3876, 67, 89, 3147, 3412, 2596, 2217, 3495, 3015, 2794, 9946, 4561, 6517, 1303, 4877, 7322, 2043, 9026, 4087, 6364, 3629, 7983, 4628, 1026, 5506, 9349, 9302, 4817, 3184, 3981, 4459, 5638, 9370, 8004, 9570, 859, 3423, 1046, 7232, 9565, 6159, 9160, 1568, 4270, 4215, 1650, 2643, 7026, 1412, 5146, 5322, 2686, 6075, 4089, 1552, 9868, 3245, 3975, 50, 9315, 2906, 8702, 3057, 5661, 6041, 2415, 7149, 3999, 2841, 9247, 9919, 5925, 399, 1620, 4761, 6247, 2960, 8464, 3297, 1571, 5412, 1252, 2575, 6735, 1986, 9830, 7452, 2978, 3042, 6429, 6916, 3817, 6646, 732, 191, 6238, 351, 1012, 3648, 4429, 2240, 6804, 556, 6010, 1735, 6544, 1389, 582, 1790, 4814, 1669, 3503, 6691, 4378, 7980, 3335, 1850, 845, 1146, 7780, 7158, 9492, 1144, 40, 9178, 1249, 779, 3894, 1961, 3783, 4905, 7321, 4316, 2267, 400, 3507, 8657, 1196, 4779, 9609, 8601, 3652, 5448, 3859, 2507, 3577, 5743, 3583, 7202, 394, 5511, 1979, 3628, 8905, 3471, 3414, 6523, 5619, 8699, 912, 5056, 3712, 9374, 2449, 2903, 2656, 9754, 8577, 2829, 3069, 4533, 6787, 6203, 494, 9879, 9766, 6281, 3862, 4674, 1107, 5934, 8029, 3860, 9885, 7015, 5263, 4296, 20, 5289, 474, 2460, 3985, 3040, 7193, 3490, 6026, 2679, 5211, 9127, 7735, 536, 813, 3996, 2455, 6148, 2440, 4739, 2255, 5149, 9682, 9997, 7928, 2677, 9614, 6790, 9221, 278, 225, 4242, 79, 9223, 1460, 3801, 2359, 3636, 2731, 3911, 2826, 7071, 5962, 4853, 4896, 8980, 4524, 9048, 3282, 8724, 1198, 3500, 7256, 5361, 1348, 7237, 8523, 6356, 4506, 9497, 4045, 3353, 5979, 3285, 1792, 8878, 2675, 7675, 4558, 1900, 8259, 9415, 3789, 373, 1959, 4723, 361, 5726, 1793, 2471, 4756, 627, 7102, 3966, 8758, 3089, 5009, 918, 4826, 4829, 1785, 7938, 9451, 5063, 3021, 2116, 2946, 298, 6795, 4766, 4664, 4515, 3935, 7531, 1824, 1803, 4385, 3726, 7665, 4815, 1022, 2834, 9541, 2330, 7310, 7125, 1699, 9423, 7066, 5060, 1232, 7195, 5876, 2819, 8024, 5181, 8641, 5374, 625, 8869, 8203, 3917, 9428, 1081, 2358, 5278, 4945, 5294, 3592, 743, 2519, 9733, 9003, 95, 8298, 9351, 980, 8366, 9225, 6226, 882, 8478, 5459, 3142, 4972, 8512, 585, 6158, 7304, 5532, 6772, 5204, 6077, 6738, 3181, 818, 854, 6137, 9976, 4298, 1339, 5814, 6927, 3229, 8680, 4012, 686, 907, 852, 6497, 1211, 8946, 7355, 5547, 1931, 7150, 945, 5802, 53, 1063, 5854, 4735, 628, 1059, 3575, 3565, 7247, 8967, 7201, 5122, 5447, 3393, 3677, 6505, 5622, 6583, 6038, 9692, 2541, 7096, 1086, 5680, 3439, 7835, 3116, 7922, 2169, 264, 1033, 5402, 119, 689, 927, 2810, 9934, 4397, 4624, 733, 8312, 2134, 4113, 344, 1717, 1235, 9382, 6509, 304, 6036, 2423, 5885, 7978, 5191, 8258, 7898, 5926, 2688, 492, 9073, 6418, 6494, 71, 6074, 2288, 5783, 4210, 2845, 5308, 8196, 2364, 3043, 365, 2531, 5574, 9293, 9033, 3547, 9569, 4639, 5520, 9244, 8300, 937, 7032, 3148, 6660, 6673, 9582, 462, 9050, 8494, 8665, 772, 2985, 2714, 6737, 7226, 6722, 3699, 7841, 7057, 3535, 1783, 646, 555, 8669, 125, 1581, 5488, 2512, 3332, 3896, 5792, 9108, 8209, 4064, 6275, 7050, 9501, 4970, 5582, 9447, 7541, 9309, 6758, 8275, 3097, 6897, 4630, 5959, 9683, 4953, 3468, 1212, 4080, 2325, 7118, 2491, 6354, 1908, 2732, 3374, 5919, 2024, 9710, 9485, 1531, 6898, 158, 7254, 9542, 9264, 4328, 8442, 7030, 4626, 5947, 5275, 4418, 3133, 6954, 7453, 4361, 9867, 3569, 4175, 2780, 3905, 5510, 440, 7366, 7399, 968, 7775, 4098, 7537, 6607, 2007, 7389, 9578, 7505, 1768, 1721, 2537, 8884, 5671, 8954, 5381, 1439, 1393, 4751, 5757, 6022, 7704, 4617, 4940, 39, 3234, 9432, 9084, 3174, 8684, 6183, 1667, 7848, 1831, 8718, 3799, 9193, 9930, 8377, 7288, 2917, 281, 9421, 9232, 8660, 964, 3165, 4983, 9403, 6234, 481, 839, 7139, 3646, 7014, 8179, 5104, 5689, 8204, 5151, 8080, 82, 8174, 3256, 5964, 4695, 9628, 6476, 5193, 6841, 4619, 8356, 2553, 5326, 5584, 8108, 5458, 7956, 2862, 1776, 9482, 583, 4077, 8624, 1760, 4414, 193, 4660, 6880, 2213, 4672, 6438, 3853, 1422, 307, 3866, 8611, 8460, 5077, 3221, 219, 1109, 6779, 6315, 9206, 7207, 8902, 1254, 4076, 8710, 7325, 9294, 59, 2770, 2189, 3522, 8040, 318, 8318, 6820, 164, 8953, 6960, 9400, 8960, 9187, 8804, 3716, 9013, 6084, 8327, 263, 4947, 3842, 9538, 2404, 6524, 2310, 2999, 1898, 9083, 2398, 3558, 3578, 9148, 4885, 4509, 3943, 5223, 9098, 1047, 1864, 1989, 450, 2441, 8228, 2922, 9518, 1204, 3526, 3016, 9701, 8391, 8947, 9519, 280, 5656, 7727, 1993, 9253, 6769, 1754, 9375, 7501, 6492, 2968, 4144, 4839, 5336, 6520, 7258, 3369, 9442, 1666, 2827, 9909, 6833, 7826, 433, 4594, 662, 6336, 7323, 7500, 6081, 3622, 9022, 4050, 9265, 5051, 4168, 4861, 8500, 317, 8994, 784, 6990, 9659, 6125, 746, 6579, 1769, 8355, 7569, 306, 6941, 7255, 1713, 1672, 3225, 5890, 6998, 9840, 707, 4343, 9507, 9680, 7278, 9900, 7497, 734, 8359, 1537, 5549, 7889, 711, 7808, 477]

処理時間

時間比(小数点以下四捨五入)　※電卓を使って計算しましょう。

課題3

同じデータで50%が並べ替え済みのデータを挿入法で並べ替えます。

ここでは課題1の処理時間と比べてどの程度速くなっているかを調べます。

処理時間の短縮の割合を時間比として次の計算で求めることにします。

時間比 = 処理時間 ÷ 課題1の処理時間

(小数点以下四捨五入)

以下の50%並べ替え済みのデータを使ったときの処理時間と時間比を求めましょう。

data = [686, 7255, 3575, 40, 4970, 4459, 3507, 400, 9232, 9542, 8391, 1986, 701, 2686, 1356, 307, 6769, 5919, 164, 8402, 3412, 9221, 8435, 543, 1769, 7232, 1339, 3622, 6041, 5959, 8036, 2089, 5211, 306, 4558, 9148, 1650, 3148, 344, 4136, 5619, 2519, 2999, 6722, 5925, 9976, 8947, 9754, 7014, 9244, 371, 4639, 462, 7125, 2189, 89, 1721, 4215, 1211, 536, 7336, 6075, 813, 8174, 9541, 8624, 590, 7453, 5768, 219, 7558, 4343, 4660, 6074, 3859, 7500, 625, 9400, 733, 5934, 9225, 6505, 5661, 3116, 7735, 784, 3325, 806, 556, 7149, 945, 907, 8494, 852, 6159, 9919, 6915, 182, 8687, 2310, 5638, 918, 8318, 707, 1109, 1803, 968, 6355, 1989, 1012, 7187, 2827, 4695, 912, 9578, 1059, 4113, 4743, 1081, 5396, 5447, 9451, 3406, 5056, 7409, 5271, 2537, 1202, 779, 7030, 1204, 2906, 3378, 9432, 2116, 1249, 3975, 8878, 9482, 9570, 4972, 5686, 5063, 6226, 1348, 9293, 6646, 1393, 6779, 5122, 1427, 4087, 1523, 4861, 6238, 373, 1552, 7980, 5184, 8980, 3308, 8669, 1620, 4697, 5896, 6748, 6036, 1669, 5656, 9351, 6608, 9867, 984, 8953, 2134, 2679, 4626, 8710, 9738, 5698, 7548, 5308, 6673, 627, 5051, 5854, 585, 9492, 9309, 264, 3468, 6790, 582, 1898, 1900, 4624, 6737, 3535, 7118, 5361, 9701, 2455, 1933, 847, 6315, 3670, 2829, 8884, 5191, 746, 8258, 8905, 7780, 4594, 8298, 5680, 4619, 1597, 9946, 2507, 4940, 1912, 3860, 6738, 2554, 1047, 9766, 1699, 4664, 9421, 2358, 2359, 95, 2397, 7102, 4777, 3069, 4766, 8458, 2441, 2449, 9885, 6941, 2460, 7537, 158, 1337, 4905, 3629, 2530, 4270, 9659, 7848, 8029, 9633, 318, 3547, 4144, 8040, 2624, 4397, 3648, 3646, 8047, 4826, 5402, 4756, 3495, 7835, 1422, 1254, 1265, 6010, 6336, 4839, 2423, 2819, 3985, 6611, 5574, 980, 9582, 8461, 4045, 9447, 7531, 7452, 9247, 5814, 9193, 2960, 8196, 8228, 854, 5488, 2575, 8688, 5964, 6607, 53, 3027, 3040, 3042, 9840, 662, 772, 3089, 3097, 1033, 3133, 6916, 3147, 293, 6471, 88, 3181, 3184, 3221, 5689, 6438, 3911, 1754, 9173, 4077, 8179, 3783, 2471, 5979, 7911, 5294, 9501, 3716, 1198, 474, 2491, 3789, 1107, 8004, 1046, 481, 2830, 6257, 882, 4040, 3471, 8660, 3720, 5178, 4055, 6520, 1067, 8359, 9684, 4361, 1931, 8327, 39, 3569, 2457, 3577, 3578, 9033, 3585, 9518, 9609, 4735, 492, 4953, 7278, 4938, 1122, 4468, 1252, 2267, 2213, 9406, 4378, 6125, 2578, 3466, 1146, 5412, 4076, 2024, 1235, 9683, 4009, 964, 9941, 7866, 4557, 8024, 3866, 4817, 2731, 6275, 3896, 5146, 9235, 5520, 8577, 278, 1717, 6077, 3225, 5077, 3996, 9160, 5204, 6034, 4739, 3000, 7501, 3356, 5060, 5511, 5736, 5080, 1831, 3282, 5104, 5181, 6429, 9223, 4050, 4089, 3726, 732, 4947, 4210, 4012, 4945, 4242, 6787, 6758, 7704, 4316, 2810, 4328, 2903, 366, 8523, 2688, 4385, 1149, 4896, 4414, 4418, 4429, 9868, 8259, 7057, 3353, 9022, 5802, 7150, 6897, 1638, 4296, 743, 4617, 8084, 9896, 6990, 6544, 3174, 3905, 4853, 9556, 2288, 4672, 2946, 6735, 225, 2255, 191, 2968, 5532, 9569, 1908, 4751, 555, 3966, 9415, 2404, 7194, 4814, 8275, 5173, 2100, 4829, 3500, 5563, 7071, 3297, 2007, 9003, 1979, 7928, 2173, 2675, 5326, 9098, 4175, 1581, 6234, 4723, 6583, 4983, 9519, 4707, 361, 1232, 4885, 5783, 6410, 909, 4319, 7889, 3142, 5149, 5151, 9507, 4632, 5757, 5743, 6772, 1531, 1764, 5193, 9083, 2217, 5223, 1850, 9879, 6880, 9538, 1961, 8960, 6820, 5322, 2098, 494, 1959, 5458, 2780, 8680, 3021, 1735, 5414, 281, 5448, 3699, 2770, 5473, 8758, 1229, 7139, 7549, 8946, 8967, 2643, 4036, 3256, 5547, 5582, 5584, 477, 5671, 2826, 2325, 6364, 5374, 6356, 7254, 2922, 5289, 9733, 2714, 365, 2512, 4013, 9048, 2596, 440, 628, 3414, 5792, 8657, 5876, 5842, 1022, 3835, 5885, 8869, 9020, 263, 3423, 2208, 8601, 5275, 859, 5962, 3335, 2862, 5009, 8366, 5506, 8416, 6158, 6354, 9253, 2841, 5336, 4533, 6927, 764, 8684, 6084, 7256, 7096, 7680, 1864, 1389, 2794, 8724, 2440, 9302, 6208, 937, 7826, 3592, 6691, 689, 8512, 3439, 6313, 433, 1790, 8108, 6319, 4967, 7201, 6476, 9934, 1144, 3057, 6373, 5726, 6418, 193, 3229, 4630, 3583, 6467, 2531, 927, 8300, 6492, 2553, 6497, 1439, 3374, 1824, 9349, 6523, 6524, 9900, 4025, 3565, 4524, 7665, 1768, 1026, 5662, 2978, 2169, 1760, 9294, 9370, 7247, 6148, 5180, 711, 7226, 304, 6947, 2981, 1412, 3712, 4761, 5993, 9375, 6812, 1776, 119, 6841, 7322, 6137, 2240, 6898, 504, 334, 1716, 6089, 8994, 7399, 2548, 6960, 8454, 6998, 9032, 9382, 7026, 7922, 4064, 399, 2541, 7448, 3503, 6566, 3801, 1792, 3853, 66, 2398, 7505, 1713, 4168, 4515, 414, 5622, 8665, 1674, 3652, 6490, 5549, 125, 8203, 3893, 3894, 7237, 8231, 2834, 5762, 9178, 6076, 9374, 7577, 2066, 7288, 3814, 7310, 7321, 5947, 7032, 7325, 4690, 8902, 7366, 7389, 7590, 2845, 5459, 394, 9614, 7479, 7497, 7808, 7304, 8611, 5510, 7040, 7541, 3799, 3999, 9997, 7569, 7270, 9085, 9906, 7675, 3943, 3525, 9692, 7727, 3490, 6242, 298, 9179, 2917, 8478, 5278, 7956, 6446, 1667, 6726, 1740, 6517, 6038, 8464, 4098, 7941, 6183, 3981, 3245, 79, 7978, 4674, 7059, 6804, 6451, 4380, 8080, 3016, 1993, 6902, 3285, 1571, 9565, 8204, 3015, 839, 3862, 2732, 7207, 8493, 59, 6494, 8312, 6954, 7193, 9273, 8356, 2063, 8355, 8368, 8377, 4877, 3234, 6081, 3817, 8439, 2415, 6579, 2700, 4212, 818, 7710, 2330, 7015, 1672, 3369, 4628, 6247, 194, 3935, 3636, 5641, 4815, 8641, 873, 7323, 8442, 1183, 5381, 7241, 845, 3628, 8699, 8702, 2722, 2985, 7088, 1785, 4509, 3526, 1303, 9428, 3043, 7355, 3522, 450, 8510, 9485, 8460, 1212, 1460, 7983, 3842, 9073, 6321, 9127, 7195, 2677, 9013, 9628, 280, 9050, 6281, 4561, 9084, 7938, 1568, 7202, 1196, 9108, 4840, 734, 1783, 3332, 9187, 646, 9206, 1225, 6237, 3677, 583, 82, 7847, 7775, 7898, 9264, 3876, 4080, 4506, 9442, 6203, 8954, 9315, 6833, 6699, 7158, 7258, 2656, 317, 71, 4989, 1793, 1573, 2364, 9423, 6026, 8844, 5890, 351, 4298, 1063, 3350, 3165, 9497, 1666, 12, 20, 9403, 3811, 3558, 6660, 9682, 1086, 7097, 9909, 5713, 4857, 8718, 6129, 2043, 3393, 9680, 9710, 6022, 3595, 67, 9930, 4407, 9026, 5174, 793, 7841, 6795, 9265, 9780, 8209, 9830, 6509, 8804, 9604, 5263, 7066, 2241, 7050, 1537, 3917, 9796, 6887, 2221, 50, 5926, 4779, 8500]

処理時間

時間比(小数点以下四捨五入)　※電卓を使って計算しましょう。

課題4

同じデータで80%が並べ替え済みのデータを挿入法で並べ替えます。

ここでは課題1の処理時間と比べてどの程度速くなっているかを調べます。

処理時間の短縮の割合を時間比として次の計算で求めることにします。

時間比 = 処理時間 ÷ 課題1の処理時間

(小数点以下四捨五入)

以下の80%並べ替え済みのデータを使ったときの処理時間と時間比を求めましょう。

data = [8994, 9050, 2310, 40, 50, 53, 59, 66, 67, 6319, 79, 82, 88, 89, 95, 8478, 8174, 6898, 5762, 182, 351, 6321, 2827, 219, 225, 968, 264, 3308, 7727, 281, 9485, 298, 6208, 8391, 394, 9351, 318, 7030, 344, 191, 4175, 8259, 9565, 9273, 8688, 9415, 399, 400, 414, 433, 9264, 450, 462, 4777, 4674, 481, 492, 3142, 1568, 8402, 1898, 555, 8684, 1993, 4009, 7841, 590, 625, 627, 4533, 71, 9225, 686, 5689, 1669, 164, 6509, 5051, 2208, 2553, 2507, 3935, 764, 2169, 3234, 4397, 4761, 3165, 813, 711, 839, 845, 847, 852, 854, 2903, 873, 2288, 907, 7202, 912, 918, 8036, 937, 945, 6238, 263, 6769, 3894, 1012, 1022, 1026, 6183, 1046, 8967, 2024, 1063, 3999, 7040, 1086, 1107, 1109, 3535, 307, 1146, 2116, 6524, 2189, 1198, 8669, 1204, 1211, 9692, 9582, 4013, 7735, 1235, 733, 1252, 1254, 6336, 784, 1337, 1339, 7409, 1356, 7665, 1393, 9868, 5959, 7014, 6812, 882, 1523, 9680, 1537, 1552, 9604, 1571, 5104, 9221, 1597, 4418, 9701, 8905, 1666, 8454, 701, 9293, 3147, 1699, 4076, 7237, 3225, 1721, 9442, 1740, 3652, 1760, 2100, 7453, 1769, 1776, 1783, 1785, 7050, 1792, 7558, 4632, 1824, 1831, 6779, 6418, 7288, 5361, 1908, 6313, 1931, 1933, 1959, 2359, 4989, 1986, 1989, 5582, 2007, 5925, 2043, 2063, 2066, 2089, 5402, 6247, 7322, 2134, 4045, 9733, 4840, 5458, 2213, 2217, 6242, 9235, 9542, 6074, 2173, 5511, 39, 2325, 2330, 5656, 1961, 2364, 2255, 2398, 2404, 293, 2423, 2440, 2441, 2449, 7278, 7889, 5926, 2471, 2491, 6275, 3507, 2519, 4055, 2531, 2537, 1793, 2548, 3184, 732, 2575, 5174, 2596, 2624, 7071, 2656, 361, 3043, 9085, 2686, 2688, 2700, 2714, 2722, 7059, 2732, 4385, 4826, 2794, 5890, 6355, 304, 5814, 2829, 6738, 2834, 306, 2845, 3985, 6941, 2968, 2917, 3569, 2946, 2960, 2415, 8844, 7847, 779, 2999, 5473, 3015, 3016, 3021, 3027, 9013, 6954, 689, 3057, 3069, 3089, 3097, 3116, 5146, 4707, 9492, 9482, 806, 3174, 984, 6607, 3221, 7336, 3229, 4328, 3245, 3256, 3282, 1573, 3297, 6517, 7255, 6804, 6257, 6990, 474, 3356, 7366, 3374, 9160, 3393, 3406, 3412, 3414, 4735, 3439, 3466, 3468, 3471, 3490, 3495, 3500, 3503, 2512, 3522, 3525, 3526, 6041, 4361, 4723, 3565, 2922, 3133, 3577, 3578, 9518, 3585, 3592, 9570, 3622, 7139, 7187, 3636, 3646, 3423, 1864, 4316, 3677, 3699, 3712, 3716, 3720, 3726, 3783, 9507, 4751, 3801, 9382, 3814, 3866, 3835, 3842, 6281, 3859, 964, 3862, 2530, 3876, 9906, 9370, 3896, 3905, 9309, 3917, 746, 7980, 3966, 3975, 3981, 6748, 6084, 1067, 583, 1144, 927, 4025, 4036, 4040, 7032, 4050, 7304, 4064, 8460, 7201, 1389, 3911, 4089, 6476, 4113, 4967, 5184, 4168, 5757, 2906, 4212, 4215, 4242, 4270, 4296, 4298, 3670, 8204, 440, 4343, 3547, 8702, 4380, 2770, 4639, 4407, 4414, 1620, 4429, 3369, 4468, 4506, 734, 9193, 4524, 6897, 4557, 4558, 4561, 4594, 4617, 4619, 3817, 4626, 4628, 4630, 5414, 1303, 4660, 4664, 4672, 1638, 9556, 4695, 7577, 8356, 7207, 3648, 4739, 3860, 5063, 4756, 9497, 4766, 5661, 4779, 4814, 4815, 8312, 2541, 4829, 4839, 1196, 4853, 9946, 7780, 4877, 7537, 4896, 5448, 4938, 4940, 4945, 9633, 4953, 9022, 4970, 4080, 4983, 9084, 5009, 2554, 125, 2457, 3799, 5077, 5080, 2841, 5122, 2862, 5149, 7680, 5173, 2578, 1183, 5180, 5181, 4144, 5191, 5193, 5204, 5211, 5223, 5263, 5271, 8494, 9896, 5885, 5294, 5308, 5322, 2731, 1667, 1803, 5374, 5381, 5396, 5993, 5412, 2985, 5336, 4905, 6129, 5459, 3811, 5488, 6691, 5510, 1460, 5520, 5532, 5547, 5549, 5934, 5574, 743, 5584, 5619, 7848, 5638, 5641, 9187, 4210, 2830, 8500, 5680, 5686, 3350, 5698, 9738, 556, 5736, 5743, 3285, 707, 5768, 5783, 1850, 5802, 8960, 5842, 5854, 5876, 5289, 2810, 5896, 5919, 1059, 2460, 5563, 5947, 1422, 7321, 9519, 5979, 7938, 7389, 6022, 6026, 6034, 1768, 8040, 1122, 2397, 8641, 6076, 6077, 6081, 158, 6089, 6566, 3996, 5662, 6148, 8804, 6159, 4509, 9569, 5056, 334, 6234, 6237, 4743, 8680, 582, 3335, 1764, 7826, 1912, 6315, 6125, 9173, 194, 3583, 2819, 6356, 6364, 6373, 6410, 494, 6429, 7590, 2675, 536, 6467, 6737, 4098, 8108, 6492, 2221, 6497, 8523, 818, 278, 7194, 6523, 9934, 6544, 5060, 6579, 6583, 371, 6608, 6611, 6646, 7102, 6673, 1081, 6699, 859, 6726, 6735, 6471, 8318, 5726, 7096, 980, 6820, 5792, 6787, 6790, 504, 7355, 1439, 6772, 6833, 9374, 6880, 6887, 628, 1249, 6902, 6915, 6916, 6927, 8458, 6947, 3042, 3353, 2677, 6998, 8209, 7015, 7026, 6226, 3148, 2098, 1790, 7057, 5326, 7066, 793, 7088, 6758, 1713, 5151, 7118, 7125, 3628, 1716, 7150, 7158, 7911, 7193, 6520, 7195, 4077, 909, 3558, 7226, 7232, 8355, 7241, 7247, 7254, 3325, 2267, 9206, 7270, 2455, 543, 1202, 7310, 9628, 8047, 8687, 6960, 3000, 6660, 6137, 6010, 7399, 1348, 7448, 7452, 9083, 7479, 7497, 7500, 7501, 5962, 7531, 8359, 7541, 7548, 7549, 2780, 1735, 3181, 6438, 4515, 7675, 5506, 7704, 7710, 280, 1232, 7325, 4861, 7808, 7097, 7835, 585, 2981, 5622, 7866, 8902, 7898, 3629, 7922, 7928, 4319, 9447, 9682, 7775, 3943, 7983, 8004, 8024, 8029, 1229, 9073, 1149, 8080, 9400, 6490, 9003, 8179, 3789, 8203, 3332, 1427, 8228, 8231, 8258, 365, 4459, 1900, 8300, 4817, 8275, 8327, 7149, 3853, 4885, 8366, 8368, 8377, 4697, 6841, 4012, 8435, 1717, 8442, 8084, 8980, 1754, 8461, 8464, 119, 8493, 6494, 5671, 8510, 8512, 6505, 8577, 8601, 8611, 8624, 9026, 8657, 8660, 8665, 6446, 5275, 3575, 2358, 373, 8699, 9997, 8710, 8718, 8724, 8758, 6158, 2978, 8869, 5713, 8884, 646, 1650, 7323, 9780, 8953, 1265, 8954, 1047, 6722, 12, 7978, 1581, 9020, 4136, 6075, 5447, 9033, 9048, 20, 6038, 6036, 1979, 2679, 9098, 9108, 9127, 9148, 3378, 193, 9178, 9684, 9032, 772, 7258, 1531, 9223, 662, 9796, 2240, 9244, 9247, 9253, 8298, 9265, 1033, 1672, 9294, 9302, 4087, 9315, 9349, 317, 3040, 6451, 9375, 8439, 8946, 9403, 9406, 8416, 9421, 9423, 5964, 9432, 7569, 7941, 9451, 4972, 2826, 1674, 2643, 6795, 8196, 6354, 9428, 9538, 9541, 2241, 4690, 366, 6203, 3595, 9578, 1225, 9501, 9609, 9614, 7505, 4947, 9659, 4624, 7956, 9683, 9179, 8878, 477, 9710, 7256, 1212, 9754, 9766, 8947, 9232, 9830, 9840, 9867, 1412, 9879, 9885, 5278, 9900, 3893, 9909, 9919, 9930, 5178, 9941, 4857, 9976, 4378]

処理時間

時間比(小数点以下四捨五入)　※電卓を使って計算しましょう。

※この再現版では提出は行いません（送信先は未接続です）

Well done!

次のステップに進みましょう！

次のステップに進む

← 前のステップにもどる