著者
新森 修一, 荒谷 遙香
雑誌名
鹿児島大学理学部紀要
巻
53
ページ
1-15
発行年
2020-12-31
URL
http://hdl.handle.net/10232/00031550
ᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつ ᶍᛂࡌ࡚ィ⟬㔞ࡀࡢࡼ࠺ኚࡍࡿࡢ㸪ࡑࡢ㛵ᩘᙧࢆồࡵࡿࡇࡀ㔜せ࡛࠶ࡿࠋ୍⯡㸪ၥ㢟 ࡢつᶍࡣࡑࢀࢆධຊࡍࡿࡓࡵࡢࢹ࣮ࢱࡢ㛗ࡉn
㸦ධຊࢧࢬ࠸࠺㸧࡛ホ౯ࡍࡿ㸦[9], [13]㸧ࠋ 㛫ィ⟬㔞(time complexity)ࡣ㸪ࣝࢦࣜࢬ࣒ࡢᇶᮏ᧯సࡣ㸪ᅄ๎₇⟬ࡸẚ㍑࡞ࡢᇶᮏࢫࢸࢵࣉ ศゎ࡛ࡁࡿࡀ㸪ࣝࢦࣜࢬ࣒ࡀ⤊ࡍࡿࡲ࡛ࡢᇶᮏࢫࢸࢵࣉࡢᐇ⾜ᅇᩘࡢࡇ࡛࠶ࡿࠋࣝࢦࣜࢬ ࣒ࡢ㛫ィ⟬㔞ࡣධຊࢧࢬ౫Ꮡࡍࡿሙྜࡀከ࠸ࠋࡲࡓ㸪࠶ࡿධຊࢧࢬn
࠾࠸࡚㸪㐺ᙜ࡞᮲௳ ୗ࡛᭱ࡶ㏿ࡃࣝࢦࣜࢬ࣒ࢆᐇ⾜࡛ࡁࡿሙྜࡢ㛫ィ⟬㔞ࢆ᭱Ⰻ㛫ィ⟬㔞ࡼࡧ㸪ࣝࢦࣜࢬ࣒ࡢ ᐇ⾜᭱ࡶ㛫ࡢࡿሙྜࡢ㛫ィ⟬㔞ࢆ᭱ᝏ㛫ィ⟬㔞ࡼࡪࠋ ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡘ࠸࡚ࡣ㸪㛫ィ⟬㔞ࡢࣝࢦࣜࢬ࣒ࡢࢹ࣮ࢱ⏝㔞ࢆ⾲ࡍ㡿ᇦィ⟬ 㔞(space complexity)ࡀ࠶ࡿࠋࡇࡢ㡿ᇦィ⟬㔞ࡶ್ࡀᑠࡉ࠸Ⰻ࠸ࣝࢦࣜࢬ࣒ゝ࠼ࡿࠋࡋࡋ㸪ᐇ 㝿ࡢィ⟬࡛ࡣ㸪㡿ᇦィ⟬㔞ẚ㛫ィ⟬㔞ࡢ᪉ࡀ㔜せ࡞ࡿሙྜࡀከ࠸ࡢ࡛㸪༢ຠ⋡ࡢⰋ࠸ࣝ ࢦࣜࢬ࣒࠸࠼ࡤ㸪㛫ィ⟬㔞ࡢᑠࡉ࠸ࣝࢦࣜࢬ࣒ࢆᣦࡍሙྜࡀከ࠸ࠋ ࡲࡓ㸪㛫ィ⟬㔞ࡘ࠸࡚ࡶ㸪ධຊᑐࡍࡿ㛫ィ⟬㔞ࡢᮇᚅ್ࢆ⪃࠼ࡿሙྜࡀ࠶ࡿࠋࡇࡢሙྜࡢ 㛫ィ⟬㔞ࢆᖹᆒ㛫ィ⟬㔞ࡪࠋከࡃࡢሙྜ㸪ᖹᆒ㛫ィ⟬㔞ࡣ᭱ᝏ㛫ィ⟬㔞➼ࡋ࠸ࡇࡀ▱ ࡽࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[7], [8]㸧ࠋ ࡉ࡚㸪ࣝࢦࣜࢬ࣒ࡢຠ⋡ᛶࢆホ౯ࡍࡿ㝿ࡣ㸪ධຊࢧࢬn
ࡀ࠶ࡿ⛬ᗘࡁ࠸ሙྜࢆᐃࡋ࡚࠸ࡿ ࡀ㸪ࡇࢀࡽࡢホ౯⏝࠸ࡽࢀࡿࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞ࢆ㏆ⓗ࡞㛫ィ⟬㔞ࡼࡪࠋࡇࡢ㏆ⓗ ࡞㛫ィ⟬㔞ࡣ㸪௨ୗᐃ⩏ࡉࢀࡿ࣮࢜ࢲグἲࢆ⏝࠸࡚⾲ࢃࡉࢀࡿ㸦[8], [13]㸧ࠋ ሾᐃ⩏ ͳሿ 㸦࣮࢜ࢲグἲ㸧 ධຊࢧࢬ ݊ ࡢ㛵ᩘࡋ࡚⾲ࢃࡉࢀࡿ㛫ィ⟬㔞 ܶሺ݊ሻ ࡀ㸪࠶ࡿ㛵ᩘ ݂ሺ݊ሻ ᑐࡋ࡚ߍ൫݂ሺ݊ሻ൯ ࡛࠶ࡿࡣ㸪㐺ᙜ࡞ ʹ ࡘࡢṇࡢᐃᩘ ݊ ܿ ࡀᏑᅾࡋ㸪݊ ௨ୖࡢࡍ ࡚ࡢ ݊ ࡘ࠸࡚ ܶሺ݊ሻ ܿ ή ݂ሺ݊ሻ ࡀᡂࡾ❧ࡘࡇࢆ࠸࠺ࠋ ǤǤ ܶሺ݊ሻ ൌ ߍ൫݂ሺ݊ሻ൯ ܿ Ͳǡ ݊ א Գ ǡ ݊ ݊ ǡ ܶሺ݊ሻ ܿ ή ݂ሺ݊ሻ ࡲࡓ㸪ܶሺ݊ሻ ൌ ߍ൫݂ሺ݊ሻ൯ ࡛࠶ࡿሙྜ㸪Dzࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞ࡣ ߍ൫݂ሺ݊ሻ൯ ࡛࠶ࡿdzࡶࡋࡃࡣDzࣝ ࢦࣜࢬ࣒ࡣ ߍ൫݂ሺ݊ሻ൯ 㛫࡛ᐇ⾜࡛ࡁࡿdz࠸࠺ࠋ㸰㸰㸬ᩚิࣝࢦࣜࢬ࣒Ᏻᐃᛶ
ᩚิ㸦࠶ࡿ࠸ࡣࢯ࣮ࢺ ሺሻ㸧ࡣ㸪ḟᐃ⩏ࡉࢀࡿࡼ࠺ Dz࠼ࡽࢀࡓࢹ࣮ࢱࢆỴࡵࡽࢀࡓ㡰␒ ୪᭰࠼ࡿdz ࠸࠺᧯స࡛࠶ࡾ㸪ࡇࡢ᧯సࡸᡭ㡰ࢆཝᐦᐃ⩏ࡋࡓࡶࡢࡀᩚิ㸦ࢯ࣮ࢺ㸧ࣝࢦࣜࢬ࣒ ࡛࠶ࡿࠋ ሾᐃ⩏ ʹሿ ᩚิ㸦࠶ࡿ࠸ࡣࢯ࣮ࢺ㸧ࡣ㸪ධຊࡉࢀࡓ ݊ ಶࡢࢹ࣮ࢱ ݀ǡ ݀ଵǡ ڮ ǡ ݀ିଵ ࡀ࠼ࡽࢀࡓ ࡁ㸪ࡑࡢࢹ࣮ࢱࢆ᪼㡰㸪ࡲࡓࡣ㝆㡰୪᭰࠼ࡿ᧯సࡢࡇ࡛࠶ࡿࠋ ୍⯡ⓗᩚิࣝࢦࣜࢬ࣒ࡢධຊ࡛ࡣྠࡌ್ࢆᣢࡗࡓࢹ࣮ࢱࡀከᩘᏑᅾࡍࡿሙྜࡀ⪃࠼ࡽࢀࡿࠋᩚ ิࣝࢦࣜࢬ࣒ࡘ࠸࡚ࡣ㸪ࡇࡢྠࡌ್ࢆᣢࡗࡓࢹ࣮ࢱࢆ࠺࠸࠺㡰ᗎ࡛୪ࡿ࠸࠺Ⅼὀពࡍ ࡿᚲせࡀ࠶ࡿࠋḟࡢᐃ⩏࡛♧ࡍࡼ࠺㸪ྠࡌ್ࡢࢹ࣮ࢱࡀࢯ࣮ࢺࡢ๓ᚋ࡛ኚࡋ࡞࠸ᩚิࣝࢦࣜࢬ ࣒ࢆᏳᐃ࡞ࣝࢦࣜࢬ࣒࠸࠺ࠋ ሾᐃ⩏ ͵ሿ Ᏻᐃ࡞ᩚิࣝࢦࣜࢬ࣒ࡣ㸪௨ୗࡢ᮲௳ࢆ‶ࡓࡍࣝࢦࣜࢬ࣒ࡢࡇ࡛࠶ࡿࠋ ሺሻ ࠼ࡽࢀࡓࢹ࣮ࢱࢆ᪼㡰㸪ࡲࡓࡣ㝆㡰୪᭰࠼ࡿࠋ ሺሻ ྠࡌ್ࡢࢹ࣮ࢱࡣ㸪ᙜึࡢධຊࡢ㡰ᗎ࠾ࡾ୪᭰࠼ࡿࠋ ᩚิࣝࢦࣜࢬ࣒ࡣຠ⋡ⓗ࡛࠶ࡿࡀᏳᐃ࡛࡞࠸ࡶࡢ㸪ຠ⋡ᛶࡣ㧗ࡃ࡞࠸ࡀᏳᐃᛶࡢ᮲௳ࢆ‶ࡓࡋ ࡚࠸ࡿࡶࡢ࡞ከࡃࡢ✀㢮ࡀ࠶ࡿࠋࣝࢦࣜࢬ࣒ࡢຠ⋡ᛶ㸦ᐇ⾜㏿ᗘ㸧ࡔࡅ࡛࡞ࡃ㸪ሙྜࡼࡗ࡚ࡣᏳ ᐃᛶࡶ⪃៖ࡋ࡚㸪ࢯ࣮ࢺࡢ┠ⓗᛂࡌࡓᩚิࣝࢦࣜࢬ࣒ࢆ㑅ᢥࡍࡿᚲせࡀ࠶ࡿࠋ (1)ᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつ㸱 ௦⾲ⓗ࡞ᩚิࣝࢦࣜࢬ࣒ࡑࡢ㛵ᩘᙧ
ᮏ⠇࡛ࡣ㸪௦⾲ⓗ࡞ᩚิࣝࢦࣜࢬ࣒ࡢཎ⌮㸪㛫ィ⟬㔞ࡼࡿホ౯㸪C ゝㄒࡼࡿ㛵ᩘࣉࣟࢢ࣒ࣛ ࡢᐇࡘ࠸࡚㏙ࡿࠋᮏㄽᩥ࡛ᢅ࠺ࣝࢦࣜࢬ࣒ࡸࣉࣟࢢ࣒ࣛඹ㏻ࡋ࡚࠸ࡿࡇࡣ㸪ᩚิࡢᑐ ㇟ࡋ࡚ࡢࢹ࣮ࢱࡣᩚᩘᆺ㸦㠀㈇ᩚᩘ್㸧࡛࠶ࡾ㸪ᑐ㇟࡞ࡿࢹ࣮ࢱࡣ㓄ิD ᱁⣡ࡉࢀ࡚࠸ࡿࡶ ࡢࡋ࡚࠸ࡿⅬ࡛࠶ࡿࠋࡲࡓ㸪ࢹ࣮ࢱᩘࡣኚᩘn
ࢆ⏝࠸࡚࠾ࡾ㸪ࡑࡢࡓࡵᩚิࣝࢦࣜࢬ࣒ࡢᑐ㇟ࡣ㸪 D[0], D[1],㺃㺃㺃, D[n-1]࡛࠶ࡿࠋࡇࢀࡽࡢࢹ࣮ࢱ㸪࠶ࡿᩚิࣝࢦࣜࢬ࣒ࡀ㐺⏝ࡉࢀࡿ㸪㓄ิ D ࡢࢹ ࣮ࢱࡣ᪼㡰୪᭰࠼ࡽࢀࡿࡇ࡞ࡿࠋ㸱㸯㸬
O(n
2)
ࡢᩚิࣝࢦࣜࢬ࣒
O(n
2)
ࡢᩚิࣝࢦࣜࢬ࣒ࡋ࡚㸪ࣂࣈࣝࢯ࣮ࢺ㸪ᤄධࢯ࣮ࢺ㸪㑅ᢥࢯ࣮ࢺࡢ㡰㏙ࡿࠋࡑࢀࡒࢀ ᩚิࣝࢦࣜࢬ࣒ࡢᴫせC ゝㄒࡼࡿ㛵ᩘᙧᘧࡢࣉࣟࢢ࣒ࣛࢆ♧ࡋ㸪ྛᩚิࣝࢦ࣒ࣜࡢヲ⣽ࡘ ࠸࡚ㄝ᫂ࡍࡿࠋ (1) ࣂࣈࣝࢯ࣮ࢺ ࣂࣈࣝࢯ࣮ࢺ (Bubble sort) ࡣ㸪ᚋ᪉ࡽ๓᪉㞄ྠኈࡢࢹ࣮ࢱࢆẚ㍑࣭ࡍࡿࡇ࡛ᑠࡉ࠸ࢹ ࣮ࢱࢆ㡰๓㏦ࡗ࡚࠸ࡃ᪉ἲ࡛࠶ࡾ㸪ࡇࢀࢆ⧞ࡾ㏉ࡍࡇࡼࡾ㸪ࢹ࣮ࢱయࡀ᪼㡰㸦࠶ࡿ࠸ࡣ㝆 㡰㸧ࢯ࣮ࢺࡉࢀࡿࠋࡇࡢࣝࢦࣜࢬ࣒ࢆC ゝㄒࡼࡾࣉࣟࢢ࣒ࣛࡍࡿ௨ୗࡢࡼ࠺࡞ࡿࠋ ࣉࣟࢢ࣒ࣛ1 ࣂࣈࣝࢯ࣮ࢺ 1 2 3 4 5 6 7 8 9 // --- ࣂࣈࣝࢯ࣮ࢺ --- // void Bubblesort(int D[], int n){int i, j; for(i = 0 ; i < n-1 ; i++){ for(j = n-1 ; j > i ; j--){ if(D[j-1] > D[j]){ swap(D[j-1], D[j]); } } } } ୖࡢࣂࣈࣝࢯ࣮ࢺࡢࣉࣟࢢ࣒ࣛࡘ࠸࡚ㄝ᫂ࡍࡿࠋfor ᩥࡢධࢀᏊᵓ㐀ࡼࡾྑ➃ࡽ㞄ྠኈࡢ್ࢆ ẚ㍑ࡋᕥഃ㸪ࡘࡲࡾ㸪ῧᏐࡢᑠࡉ࠸᪉ࡢ್ࡀࡁࡅࢀࡤswap 㛵ᩘࢆᐇ⾜ࡍࡿࠋswap(x,y)ࡣ㸪ኚᩘ x y ࡢ್ࢆࡍࡿ㛵ᩘ࡛࠶ࡿࠋࡇࢀࢆ⧞ࡾ㏉ࡍࡇ࡛㸪ࢯ࣮ࢺࡉࢀ࡚࠸࡞࠸⠊ᅖࡢ᭱ᑠ್ࢆᕥ➃⛣ື ࡉࡏࡿࡇࡀฟ᮶ࡿࠋࡇࢀࢆఱᅇࡶ⧞ࡾ㏉ࡋ㸪ୖࡢࣉࣟࢢ࣒ࣛࡢ㔜ࡢfor ᩥࡀ⤊ࡍࡿ㸪㓄ิ D ࡢ ࢹ࣮ࢱࡣ᪼㡰୪᭰࠼ࡽࢀࡓࡇ࡞ࡿࠋ ࣂࣈࣝࢯ࣮ࢺࡢ㛫ィ⟬㔞ࡘ࠸࡚⪃࠼ࡿࠋࣂࣈࣝࢯ࣮ࢺ༢యࡢ㛫ィ⟬㔞ࢆ⪃࠼ࡿࡓࡵ㸪ࣉࣟࢢ ࣒ࣛ1 ࡢ for ᩥࡢືసὀ┠ࡍࡿࠋࣂࣈࣝࢯ࣮ࢺࡢሙྜ㸪ࢹ࣮ࢱࢆẚ㍑ࡋ㸪᪼㡰ࡍࡿࡓࡵࡍࡿ ᧯సࡣ ߍሺͳሻ ࡛࠶ࡿࡓࡵ㸪᭱Ⰻ㛫ィ⟬㔞᭱ᝏ㛫ィ⟬㔞ࡣࡶ 2 ࡘࡢ for ᩥ౫Ꮡࡍࡿࠋ4 ⾜┠ ࡽጞࡲࡿ ݅ 㛵ࡍࡿ for ᩥࡣ ݊ െ ͳ ᅇᐇ⾜ࡉࢀ㸪5 ⾜┠ࡽጞࡲࡿ ݆ 㛵ࡍࡿ for ᩥࡣ ݊ െ ݅ ᅇᐇ ⾜ࡉࢀࡿࡓࡵ㸪㛫ィ⟬㔞ࡣ ܶሺ݊ሻ ൌ ߍሺͳሻ ൈ ݇ ିଵ ୀଵ ൌ ܱሺͳሻ ൈ݊ሺ݊ െ ͳሻʹ ൌ ܱሺ݊ଶሻ ࡛࠶ࡿࠋྠᵝࡢ⌮⏤࡛㸪ᖹᆒ㛫ィ⟬㔞ࡶ ߍሺ݊ଶሻ ࡛࠶ࡿࠋ ࡲࡓ㸪ࣉࣟࢢ࣒ࣛ1 ࡢ 6 ⾜┠ࡢ᮲௳ᩥ“ሾ݆ െ ͳሿ ሾ݆ሿ”ࡽศࡿࡼ࠺㸪ࣂࣈࣝࢯ࣮ࢺࡣ㞄ྠኈࡢ ್ࡀྠࡌሙྜධࢀ᭰࠼ࡣⓎ⏕ࡋ࡞࠸ࠋࡑࡢࡓࡵ㸪ᐃ⩏3 ࡢ᮲௳(b)ࢆ‶ࡓࡍࠋࡼࡗ࡚㸪ࣂࣈࣝࢯ࣮ࢺ ࡣᏳᐃ࡞ᩚิࣝࢦࣜࢬ࣒࡛࠶ࡿゝ࠼ࡿࠋ (2) ᤄධࢯ࣮ࢺ ᤄධࢯ࣮ࢺ (Insertion sort) ࡣ㸪᪤ࢯ࣮ࢺࡉࢀࡓ㒊ศ㸪᪂ࡓ࡞ࢹ࣮ࢱࢆࢹ࣮ࢱࡢ್ࡢࡁࡉ (2)
ᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつ ᛂࡌࡓ㐺ษ࡞ሙᡤࢆぢࡘࡅ࡚ࡑࡇࢹ࣮ࢱࢆᤄධࡋ࡚࠸ࡃ᪉ἲ࡛࠶ࡾ㸪ࡇࢀࢆ᭱ᚋᑿࡲ࡛⧞ࡾ㏉ࡍ ࢯ࣮ࢺࡀࡍࡿࠋࣉࣟࢢ࣒࡛ࣛグ㏙ࡍࡿ㸪௨ୗࡢࡼ࠺࡞ࡿࠋ ࣉࣟࢢ࣒ࣛ2 ᤄධࢯ࣮ࢺ 1 2 3 4 5 6 7 8 9 10 11 12 // --- ᤄධࢯ࣮ࢺ --- // void Insertsort(int D[], int n){int i, j, x; for(i = 1 ; i < n ; i++){ x = D[i]; j = i; while ((D[j-1] > x) && (j > 0)){ D[j] = D[j-1]; j = j-1; } D[j] = x; } return; } ࣉࣟࢢ࣒ࣛ2 ࡘ࠸࡚ㄝ᫂ࡍࡿࠋ4 ⾜┠࡛ ݅ ൌ ͳ ึᮇࡋ㸪݅ ൏ ݊ ࡀᡂ❧ࡋ࡞ࡃ࡞ࡿࡲ࡛ ݅ ࢆ ࣥࢡ࣓ࣜࣥࢺࡋ࡞ࡀࡽfor ᩥࢆᐇ⾜ࡍࡿࠋ5 ⾜┠࡛᪂ࡋ࠸ࢹ࣮ࢱࢆ ݔ ൌ ሾ݅ሿ㸪݆ ൌ ݅ ࡋ㸪ḟࡢ while ᩥ ⛣ືࡍࡿࠋሾ݆ െ ͳሿ ݔ ࡘ ݆ Ͳ ࡢሙྜ㸪7 ⾜┠ࢆᐇ⾜ࡋ࡚ ሾ െ ͳሿ ࡢ್ࢆྑࡎࡽࡋ㸪݆ ࢆࢹ ࢡ࣓ࣜࣥࢺࡉࡏࡿࠋࡑࢀ௨እࡢሙྜ㸪ࡘࡲࡾ㸪ᤄධࡍࡿ್ ݔ ࡀẚ㍑ࡍࡿ್ࡼࡾࡁ࠸ሙྜ㸪ࡲࡓࡣ ሾͲሿ ࡼࡾࡶ್ࡀᑠࡉ࠸ሙྜ㸪ࢹ࣮ࢱࡢ᱁⣡ࡉࢀࡿሙᡤࡀ D[j]࡛࠶ࡿࡢ࡛㸪9 ⾜┠ࢆᐇ⾜ࡍࡿࠋ ᤄධࢯ࣮ࢺࡢ㛫ィ⟬㔞ࡘ࠸࡚⪃࠼ࡿࠋࣉࣟࢢ࣒ࣛ2 ࡣ for ᩥࡑࢀྵࡲࢀࡿ while ᩥ࡛ᵓᡂࡉ ࢀ࡚࠾ࡾ㸪ධຊࡼࡗ࡚㛫ィ⟬㔞ࡣኚࡍࡿࠋ᭱ࡶࣝࢦࣜࢬ࣒ࡢືసࡀ㧗㏿࡞ሙྜࡣ㸪࠼ࡽࢀࡓ ࢹ࣮ࢱࡀ᪤ࢯ࣮ࢺࡉࢀ࡚࠸ࡿሙྜ࡛࠶ࡿࠋࡇࡢሙྜ㸪6 ⾜┠ࡢ ሾ݆ െ ͳሿ ݔ ࠸࠺᮲௳ࡣ୍ᗘࡶᡂ ❧ࡋ࡞࠸ࠋࡋࡓࡀࡗ࡚㸪while ᩥࡢ୰ࡢฎ⌮ࡣ୍ᗘࡶᐇ⾜ࡉࢀࡎ㸪for ᩥࡢฎ⌮ࡣ ݊ െ ͳ ᅇࡋᐇ⾜ࡉ ࢀ࡞࠸ࡇ࡞ࡿࠋfor ᩥࡢ୰ࡢ᧯సࡣ㸪ᩘᅇࡢẚ㍑࣭௦ධ᧯సࡢࡳ࡛࠶ࡾ㸪ߍሺͳሻ ࡞ࡿࠋࡼࡗ࡚㸪᭱ Ⰻ㛫ィ⟬㔞ࡣḟࡢࡼ࠺࡞ࡿࠋ ܶሺ݊ሻ ൌ ሺ݊ െ ͳሻ ൈ ߍሺͳሻ ൌ ߍሺ݊ሻ ୍᪉㸪ࣝࢦࣜࢬ࣒ࡀ᭱ࡶ㐜࠸ሙྜࡣ㸪ධຊࢹ࣮ࢱࡀ㝆㡰ࢯ࣮ࢺࡉࢀ࡚࠸ࡿሙྜ࡛࠶ࡿࠋࡇࡢሙ ྜ㸪ᤄධࡍࡿࢹ࣮ࢱࡢ᱁⣡ሙᡤࡣᖖ㓄ิࡢᕥ➃࡞ࡾ㸪 ݅ ൌ ݇ ࡢሙྜ㸪while ᩥࡣ ݇ ᅇ⧞ࡾ㏉ࡉࢀ ࡿࠋwhile ᩥࡢ୰ࡢ᧯సࡶᩘᅇࡢẚ㍑࣭௦ධ᧯సࡢࡳ࡛࠶ࡾ㸪 ߍሺͳሻ ࡞ࡿࠋୖࡢ᭱Ⰻ㛫ィ⟬㔞࡛㏙ ࡓࡼ࠺㸪while ᩥࢆ㝖࠸ࡓ for ᩥࡢ㛫ィ⟬㔞ࡣ ߍሺ݊ሻ ࡛࠶ࡿࡢ࡛㸪᭱ᝏ㛫ィ⟬㔞ࡣ ܶሺ݊ሻ ൌ ߍሺͳሻ ൈ ݇ ୀଵ ߍሺ݊ሻ ൌ ܱሺ݊ଶሻ ࡛࠶ࡿࠋࡲࡓ㸪ド᫂ࡣ┬␎ࡍࡿࡀ㸪ᖹᆒ㛫ィ⟬㔞ࡶ ߍሺ݊ଶሻ ࡛࠶ࡿࡇࡀศࡗ࡚࠸ࡿࠋ ᤄධࢯ࣮ࢺࡢᏳᐃᛶࡣ㸪ྠࡌ್ࡀྵࡲࢀ࡚࠸ࡿࡣ㸪ධຊࡢ㡰ᗎ࠾ࡾ୪᭰࠼ࡽࢀࡿࡓࡵᡂ❧ ࡋ࡚࠸ࡿࠋࡇࢀࡣ㸪ࣉࣟࢢ࣒ࣛ2 ࡢ 6 ⾜┠ࡀ㛵ಀࡋ࡚࠸ࡿࠋሾ݆ െ ͳሿ ݔ ࡢሙྜࡣ್ࢆྑࡎࡽࡋ㸪ࡑ ࢀ௨እࡢሙྜࡣ ሾ݆ሿ ್ࢆᤄධ㸪ࡘࡲࡾ㸪ሾ݆ െ ͳሿ ൌ ݔ ࡢሙྜࡣ ሾ݆ െ ͳሿ ࡢᚋ ݔ ࢆᤄධࡍࡿࠋ௨ ୖࡽ㸪ᐃ⩏3 ࡢ᮲௳(b)ࢆ‶ࡓࡍࡓࡵ㸪ᤄධࢯ࣮ࢺࡣᏳᐃ࡞ᩚิࣝࢦࣜࢬ࣒࡛࠶ࡿゝ࠼ࡿࠋ (3) 㑅ᢥࢯ࣮ࢺ 㑅ᢥࢯ࣮ࢺ(Selection sort) ࡣ㸪ධຊࢹ࣮ࢱࡽ್᭱ࢆぢࡘࡅ࡚᭱ᚋᑿ㸪ṧࡾࡢࢹ࣮ࢱᑐࡋ࡚ ࡶྠᵝࡢ᧯సࢆ⧞ࡾ㏉ࡋ࡚ࢯ࣮ࢺࡍࡿ᪉ἲ࡛࠶ࡿࠋ㑅ᢥࢯ࣮ࢺࡢࣝࢦࣜࢬ࣒ࢆࣉࣟࢢ࣒࡛ࣛグ㏙ࡍ ࡿ௨ୗࡢࡼ࠺࡞ࡿࠋ ࣉࣟࢢ࣒ࣛ3 㑅ᢥࢯ࣮ࢺ 1 2 3 // --- 㑅ᢥࢯ࣮ࢺ --- // void Selectionsort (int D[] , int n){
int max, max_index, i, j;
(3)
ᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつ 4 5 6 7 8 9 10 11 12 13 14 for(i = n-1 ; i > 0 ; i--){ max = D[0]; max_index = 0; for(j = 1 ; j <= i ; j++){ if(D[j] >= max){ max = D[j]; max_index = j; } } swap(D[max_index], D[i]); } return; } ࣉࣟࢢ࣒ࣛ3 㛵ࡋ࡚ㄝ᫂ࡍࡿࠋࢧࢬ ݊ ࡢ㓄ิ D ࢆࢯ࣮ࢺࡍࡿࡓࡵ㸪㛵ᩘࡢ௬ᘬᩘࡣ㓄ิ D ࢹ࣮ࢱࡢಶᩘ ݊ ࡛࠶ࡿࠋ4 ⾜┠࡛ ݅ ൌ ݊ െ ͳ ึᮇࡋ㸪݅ Ͳ ࡀᡂ❧ࡋ࡞ࡃ࡞ࡿࡲ࡛ ݅ ࢆࢹࢡࣜ ࣓ࣥࢺࡋ࡞ࡀࡽfor ᩥࡢ୰㌟ࢆᐇ⾜ࡉࡏࡿࠋ5 ⾜┠࡛ ݉ܽݔ ൌ ሾͲሿ㸪݉ܽݔௗ௫ ൌ Ͳ ࡋ㸪6 ⾜┠ࡢ for ᩥ ⛣ືࡍࡿࠋ݆ ൌ ͳ ึᮇࡋ㸪݆ ݅ ࡀᡂ❧ࡋ࡞ࡃ࡞ࡿࡲ࡛ ݆ ࢆࣥࢡ࣓ࣜࣥࢺࡋ࡞ࡀࡽ for ᩥࡢ୰ ㌟ࢆᐇ⾜ࡉࡏࡿࠋ7 ⾜┠࡛ ሾ݆ሿ ݉ܽݔ ࢆẚ㍑ࡋ㸪ሾ݆ሿ ݉ܽݔ ࡢሙྜࡣ 8 ⾜┠࡛ ݉ܽݔ ൌ ሾ݆ሿ㸪 ݉ܽݔௗ௫ ൌ ݆ ࢆᐇ⾜ࡍࡿࠋෆഃࡢ for ᩥࢆᐇ⾜ࡋ㸪ࢯ࣮ࢺࡉࢀ࡚࠸࡞࠸㓄ิࡢ୰್࡛᭱ࢆぢࡘࡅࡓ ࡽ㸪11 ⾜┠ࡢ swap 㛵ᩘ࡛㸪್᭱ࢯ࣮ࢺࡉࢀ࡚࠸࡞࠸㓄ิࡢྑ➃ࡢ್ࢆࡍࡿࠋࡇࢀࢆ ݅ Ͳ ࡀᡂ❧ࡋ࡞ࡃ࡞ࡿࡲ࡛⧞ࡾ㏉ࡍࡇࡼࡾ㸪㑅ᢥࢯ࣮ࢺࡣࡍࡿࠋ 㑅ᢥࢯ࣮ࢺࡢ㛫ィ⟬㔞ࡘ࠸࡚⪃࠼ࡿࠋࣉࣟࢢ࣒ࣛ 3 ࡣ㸪ධຊࡼࡗ࡚ࣝࢦࣜࢬ࣒ࡢᐇ⾜㛫 㸦ẚ㍑ᅇᩘ㸧ࡀኚࡋ࡞࠸ࡓࡵ㸪᭱Ⰻ㛫ィ⟬㔞᭱ᝏ㛫ィ⟬㔞ࡣ➼ࡋ࠸ࠋ࠸࠺ࡢࡣ㸪್᭱ࢆ᥈ ⣴ࡍࡿ㝿㸪ࢯ࣮ࢺࡉࢀ࡚࠸࡞࠸㓄ิࢆ࡚ᬻᐃࡢ್᭱ᚲࡎẚ㍑ࡍࡿࡓࡵ࡛࠶ࡿࠋ ࡛ࡣ㸪㛫ィ⟬㔞ࡘ࠸࡚⪃࠼࡚࠸ࡃࠋࣉࣟࢢ࣒ࣛ3 ࡣ㔜ࡢ for ᩥࡼࡾᵓᡂࡉࢀ࡚࠸ࡿࠋእഃࡢ for ᩥࡢ⧞ࡾ㏉ࡋᅇᩘࡣ ݊ െ ͳ ᅇ࡛࠶ࡾ㸪ෆഃࡢ for ᩥࡣእഃࡢ for ᩥࡢኚᩘ ݅ ౫Ꮡࡋ㸪݇ ൌ ݅ ࡢሙ ྜ㸪for ᩥࡣ ݇ ᅇ⧞ࡾ㏉ࡉࢀࡿࠋྛ for ᩥࡢ୰ࡢ᧯సࡣ㸪ᩘᅇࡢẚ㍑࣭௦ධ᧯సࡢࡳ࡛࠶ࡾ㸪ߍሺͳሻ ࡞ࡿࠋࡼࡗ࡚㸪㛫ィ⟬㔞ࡣḟࡢࡼ࠺࡞ࡿࠋ ܶሺ݊ሻ ൌ ݇ ൈ ߍሺͳሻ ൌ ܱሺͳሻ ൈ݊ሺ݊ െ ͳሻʹ ିଵ ୀଵ ൌ ܱሺ݊ଶሻ ḟ㸪㑅ᢥࢯ࣮ࢺࡢᏳᐃᛶࡘ࠸࡚ㄝ᫂ࡍࡿࠋ㑅ᢥࢯ࣮ࢺࡣ್᭱ྑ➃ࡢ್ࢆࡍࡿࡓࡵ㸪ࢹ࣮ ࢱࡢ㡰ᗎࡣࣂࣛࣂࣛ࡞ࡿࠋࡼࡗ࡚㸪୍⯡ⓗࡣ㑅ᢥࢯ࣮ࢺࡣᏳᐃᛶࡢ᮲௳ࢆ‶ࡓࡋ࡚࠸࡞࠸ࡢ࡛㸪Ᏻ ᐃ࡞ࢯ࣮ࢺࡍࡿࡓࡵࡣᕤኵࡀᚲせ࡞ࡿࠋ㸱
.㸰㸬
O(nlog n)
ࡢᩚิࣝࢦࣜࢬ࣒
O(n
log n
)
ࡢᩚิࣝࢦࣜࢬ࣒ࡋ࡚㸪ࢡࢵࢡࢯ࣮ࢺ㸦[2]㸧㸪ࣄ࣮ࣉࢯ࣮ࢺ㸦[3]㸧㸪࣐࣮ࢪࢯ࣮ࢺ 㸦[7]㸧ࡢ㡰㏙ࡿࠋࡑࢀࡒࢀᩚิࣝࢦࣜࢬ࣒ࡢᴫせ C ゝㄒࡼࡿ㛵ᩘᙧᘧࡢࣉࣟࢢ࣒ࣛࢆ♧ࡋ㸪 ྛᩚิࣝࢦ࣒ࣜࡢヲ⣽ࡘ࠸࡚ㄝ᫂ࡍࡿࠋ (1) ࢡࢵࢡࢯ࣮ࢺ ࢡࢵࢡࢯ࣮ࢺ(Quick sort)ࡣ㸪࠶ࡿࢹ࣮ࢱࢆᇶ‽್(ࣆ࣎ࢵࢺ)ࡋ㸪ᑐ㇟࡞ࡿࢹ࣮ࢱ㞟ྜࢆᇶ‽ ್ࡼࡾࡁ࠸ࢢ࣮ࣝࣉᑠࡉ࠸ࢢ࣮ࣝࣉศ㢮ࡋ㸪ྛࢢ࣮ࣝࣉࡘ࠸࡚ྠᵝࡢ᧯సࢆ⧞ࡾ㏉ࡍࡇ ࡼࡗ࡚ࢯ࣮ࢺࡍࡿ᪉ἲ࡛࠶ࡾ㸪ࡇࢀࢆྛࢢ࣮ࣝࣉᖐⓗᐇ⾜ࡍࡿࡇࡼࡾࢯ࣮ࢺࡀࡍࡿࠋ ࡇࡢᖐⓗ࡞㒊ศࢆᐇ⌧ࡍࡿࣉࣟࢢ࣒ࣛࡣ௨ୗࡢࡼ࠺࡞ࡿࠋ ࣉࣟࢢ࣒ࣛ4-1 ࢡࢵࢡࢯ࣮ࢺࡢᖐ㒊ศ 1 2 3 // --- Quick sort 㛵ᩘ --- // void Quicksort(int D[], int left, int right){int pivot_index;
ᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつ 4 5 6 7 8if(left >= right) return;
pivot_index = partition(D, left, right); Quicksort(D, left, pivot_index - 1); Quicksort(D, pivot_index + 1, right); } ࣉࣟࢢ࣒ࣛ4-1 ࢆㄝ᫂ࡍࡿࠋࡲࡎ㸪㓄ิ D ࡢᕥ➃ࡢῧᏐࢆ left㸪ྑ➃ࡢῧᏐࢆ right タᐃࡋ࡚࠸ࡿࠋ 4 ⾜┠࡛ left right ࡢ್ࢆẚ㍑ࡋ㸪 ࡘࡲࡾ㸪㓄ิ D ྵࡲࢀࡿ್ࡀ 1 ࡘ௨ୗࡢሙྜࡣࣝ ࢦࣜࢬ࣒⤊ࡍࡿࠋ5 ⾜┠ࡢ partition 㛵ᩘ࡛ᇶ‽್ࡀ᱁⣡ࡉࢀ࡚࠸ࡿ㓄ิࡢῧᏐ pivot_index ࢆ⟬ฟࡍ ࡿࠋpartition 㛵ᩘෆ࡛ࡣ㸪ᇶ‽್ࢆỴᐃࡍࡿ᧯స㸪㓄ิ D ࢆ 2 ࡘศࡅࡿ᧯సࢆ⾜ࡗ࡚࠸ࡿࡀ㸪ヲࡋࡃ ࡣᚋ㏙ࡍࡿࠋpartition 㛵ᩘෆ࡛㓄ิ D ࢆᇶ‽್ᮍ‶ࡢࢹ࣮ࢱࡢ㞟ྜ ଵ 㸪ᇶ‽್௨ୖࡢࢹ࣮ࢱࡢ㞟ྜ ଶ ศࡅࡿࡇࡀ࡛ࡁࡿࡓࡵ㸪ࡇࢀࢆྛࠎ6, 7 ⾜┠࡛ᖐⓗᐇ⾜ࡉࡏ࡚࠸ࡿࠋ ࢡࢵࢡࢯ࣮ࢺࡣ㸪ḟヲ㏙ࡍࡿ partition 㛵ᩘࡀ㔜せ࡞ᙺࢆᣢࡗ࡚࠾ࡾ㸪ࡇࡢ㛵ᩘࡢࣉࣟࢢ࣒ࣛ ࡣ௨ୗࡢࡼ࠺࡞ࡿࠋ ࣉࣟࢢ࣒ࣛ4-2 partition 㛵ᩘ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // --- partition 㛵ᩘ --- // int partition(int D[], int left, int right){
int k, i, j;
k = rand() % (right - left + 1) + left; swap(D[k],D[right]);
i = left; j = right - 1; while(i <= j){
while(D[i] < D[right]) i++;
while((D[j] >= D[right]) && (j>=i)) j--; if(i < j){ swap(D[i],D[j]);} } swap(D[i],D[right]); return i; } ࣉࣟࢢ࣒ࣛ4-2 ࡘ࠸࡚ㄝ᫂ࡍࡿࠋ4 ⾜┠࡛ ሾ݈݂݁ݐሿ ࡽ ሾݎ݄݅݃ݐሿ ࡢ㛫࡛ᇶ‽್ࢆࣛࣥࢲ࣒Ỵࡵ ࡿࠋ5 ⾜┠࡛ᇶ‽್ྑ➃ࡢ್ࢆධࢀ᭰࠼㸪6 ⾜┠࡛ ݅ ݆ ࡢ್ࢆึᮇࡍࡿࠋ7 ⾜┠ࡽ 11 ⾜┠ࡢ while ᩥ࡛ᇶ‽್ᮍ‶ࡢࢹ࣮ࢱࢆᕥ㸪ᇶ‽್௨ୖࡢࢹ࣮ࢱࢆྑ⛣ືࡉࡏࡿࠋ݅ ݆ ࡞ࡗ࡚ while ᩥ ࢆᢤࡅฟࡋ㸪12 ⾜┠࡛ ሾ݅ሿ㸪ࡘࡲࡾᇶ‽್௨ୖࡢࢹ࣮ࢱࡢ㞟ྜࡢᕥ➃ᇶ‽್ࡀ᱁⣡ࡉࢀ࡚࠸ࡿ ሾݎ݄݅݃ݐሿ ࢆࡍࡿࠋ13 ⾜┠࡛ᇶ‽್ࡀ᱁⣡ࡉࢀ࡚࠸ࡿῧᏐ ݅ ࢆ Quicksort 㛵ᩘ㏉ࡍࠋ ࢡࢵࢡࢯ࣮ࢺࡢ㛫ィ⟬㔞ࡘ࠸࡚⪃࠼ࡿࠋࡲࡎ㸪partition 㛵ᩘࡢ㓄ิࡢࢧࢬࢆ ሺݎ݄݅݃ݐ െ ݈݂݁ݐ ͳሻ ൌ ݊ ௬ᐃࡍࡿࠋࡇࡢ㛵ᩘࡣ 2 㔜ࡢ while ᩥ࡛ᵓᡂࡉࢀ࡚࠸ࡿࡀ㸪እഃࡢ while ᩥࡢ⧞ࡾ㏉ࡋ ᅇᩘ㛵ࢃࡽࡎ㸪ෆഃࡢ2 ࡘࡢ while ᩥࡢ⧞ࡾ㏉ࡋᅇᩘࡣྜࢃࡏ࡚᭱ ݊ െ ͳ ᅇ࡛࠶ࡿࠋ࡞ࡐ࡞ࡽ㸪 ᭱ึ ݊ െ ͳ ࡔࡅ㞳ࢀ࡚࠸ࡿ ݅ ݆ ࡣෆഃࡢ while ᩥࢆᐇ⾜ࡍࡿࡓࡧ 1 ࡘࡎࡘ㏆࡙ࡁ㸪᭱ ݊ െ ͳ ᅇࡢᐇ⾜ࡼࡾ ݅ ݆ ࡞ࡾ㸪እഃࡢ while ᩥࡢ⤊᮲௳ࡀ‶ࡓࡉࢀࡿࡽ࡛࠶ࡿࠋwhile ᩥ௨እࡢ᧯ సࡣᐃᩘ㛫࡛ᐇ⾜ྍ⬟࡞ࡢ࡛㸪partition 㛵ᩘࡢ᭱㛫ィ⟬㔞ࡣ ܶሺ݊ሻ ൌ ߍሺͳሻ ή ሺ݊ െ ͳሻ ൌ ߍሺ݊ሻ ࡞ࡿࠋ௨ୗ㸪㛫ィ⟬㔞ࢆィ⟬ࡋࡸࡍࡃࡍࡿࡓࡵ㸪ࢧࢬ ݊ ࡢሙྜࡢ partition 㛵ᩘࡢ㛫ィ⟬㔞ࡣ㸪 ᐃᩘ ܿ ࢆ⏝࠸࡚ ߍሺ݊ሻ ൌ ܿ݊ ࡍࡿࠋ ḟ㸪ࢡࢵࢡࢯ࣮ࢺࡢᖐࢆ㋃ࡲ࠼࡚㛫ィ⟬㔞ࢆ⪃࠼ࡿࠋࢡࢵࢡࢯ࣮ࢺࡣ㸪ᇶ‽್ࡢ㑅ࡧ᪉ ࡼࡗ࡚㛫ィ⟬㔞ࡀኚࡍࡿࠋࣝࢦࣜࢬ࣒ࡀ᭱ࡶ㐜࠸ሙྜࡣ㸪ᇶ‽್ࡋ࡚ᖖ᭱ᑠ್ࡶࡋࡃࡣ᭱ ್ࡀ㑅ࡤࢀࡿሙྜ࡛࠶ࡿࠋࡇࡢࡁ㸪㓄ิD ࡣ“ᇶ‽್ᇶ‽್௨ୖࡢࢹ࣮ࢱ”ࡶࡋࡃࡣ“ᇶ‽್ᇶ ‽್௨ୗࡢࢹ࣮ࢱ”ศࡉࢀࡿࠋᅇࡣ㸪ᇶ‽್ẖᅇ᭱ᑠ್ࡀ㑅ࡤࢀࡿሙྜࢆ⪃࠼ࡿࠋヲ⣽ࡣ┬␎ ࡍࡿࡀ㸪ࡇࡢሙྜࡢᖐᮌࢆᵓ⠏ࡋ㸪ᖐᮌࡽ㛫ィ⟬㔞ࢆồࡵࡿᖐᮌࡢ㧗ࡉࡣ ݊ ࡛࠶ࡾ㸪⠇ (6)
ᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつ Ⅼࡢ㛫ィ⟬㔞ࡣ ܿ݊ǡ ܿሺ݊ െ ͳሻǡ ڮ ǡ ܿ ࡞ࡗ࡚࠸ࡿࠋᖐࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞ࡣ㸪ᖐᮌࡢࡍ ࡚ࡢ⠇Ⅼࡀ⾲ࡍ㛫ィ⟬㔞ࡢ➼ࡋ࠸ࡓࡵ㸪ࢡࢵࢡࢯ࣮ࢺࡢ᭱ᝏ㛫ィ⟬㔞ࡣḟࡢࡼ࠺࡞ࡿࠋ ܶሺ݊ሻ ൌ ܿሺ݊ െ ݅ሻ ൌ ܿ݅ ୀଵ ൌ ܿ݊ሺ݊ ͳሻʹ ൌ ߍሺ݊ଶሻ ିଵ ୀ ୍᪉㸪᭱ࡶࣝࢦࣜࢬ࣒ࡢືసࡀ㧗㏿࡞ሙྜࡣ㸪ᇶ‽್ࡋ࡚ᖖ୰ኸ್ࡀ㑅ࡤࢀࡿሙྜ࡛࠶ࡿࠋࡇ ࡢሙྜ㸪“ᇶ‽್ᮍ‶ࡢࢹ࣮ࢱ”“ᇶ‽್௨ୖࡢࢹ࣮ࢱ”ࡢࢧࢬࡣࡰ➼ࡋࡃ࡞ࡾ㸪ᆒ➼ศࡉࢀࡿࠋ ࡇࡢሙྜࡢᖐᮌࢆᵓ⠏ࡍࡿ㸪ⴥࡢᩘࡣࢹ࣮ࢱᩘ ݊ ࡛࠶ࡾ㸪ᮌࡢ㧗ࡉࡣ ߍሺ ݊ሻ ࡛࠶ࡿࠋࡲࡓ㸪 ᖐᮌࡢྛࣞ࣋ࣝࡢ⠇Ⅼྵࡲࢀࡿ㛫ィ⟬㔞ࡢࡣࡍ࡚ ܿ݊ ࡛࠶ࡿࠋࡼࡗ࡚㸪᭱Ⰻ㛫ィ⟬㔞ࡣ ܶሺ݊ሻ ൌ ܿ݊ ή ߍሺ ݊ሻ ൌ ߍሺ݊ ݊ሻ ࡛࠶ࡿࠋࡲࡓ㸪݊ ಶࡢࢹ࣮ࢱࡽᇶ‽್ࢆ㑅ࡪ᪉ἲࡣࣛࣥࢲ࣒࡞ࡓࡵ㸪ᇶ‽್ࡀྛῧᏐ᱁⣡ࡉࢀࡿ ☜⋡ࡣ ͳ ݊Τ ࡛࠶ࡿࠋࡇࡢࡇࡽ㸪ᖹᆒ㛫ィ⟬㔞ࡶ ߍሺ݊ ݊ሻ ࡛࠶ࡿࡇࡀド᫂ࡉࢀ࡚࠸ࡿࠋ ࢡࢵࢡࢯ࣮ࢺࡢᏳᐃᛶࡘ࠸࡚⪃࠼ࡿࠋࢡࢵࢡࢯ࣮ࢺࡢሙྜ㸪ࢹ࣮ࢱࡀࡢ⨨᱁⣡ࡉࢀ࡚ ࠸ࡿࢆ⪃៖ࡏࡎࡢ᧯సࢆ⾜࠺ࡓࡵ㸪ྠࡌ್ࡢࢹ࣮ࢱࡀධຊࡢ㡰ᗎ࠾ࡾ୪᭰ࡽࢀࡿࡣ ࠸࠼࡞࠸ࠋࡑࡢࡓࡵ㸪୍⯡ⓗࢡࢵࢡࢯ࣮ࢺࡣᏳᐃᛶࡢ᮲௳ࢆ‶ࡓࡋ࡚࠸࡞࠸ࡢ࡛㸪Ᏻᐃ࡞ࢯ࣮ࢺ ࡍࡿࡓࡵࡣᕤኵࡀᚲせ࡞ࡿࠋ (2) ࣄ࣮ࣉࢯ࣮ࢺ ࣄ࣮ࣉࢯ࣮ࢺ(Heapsort)ࡣ㸪2 ศᮌࡢྛ⠇Ⅼࣄ࣮ࣉࡢ᮲௳ࢆ‶ࡓࡍࡼ࠺ࢹ࣮ࢱࢆ᱁⣡ࡋ㸪᰿ ࠶ࡿ್᭱ࡢࢹ࣮ࢱࢆྲྀࡾฟࡋࡓᚋ㸪ࣄ࣮ࣉࡢᵓᡂࢆ⾜࠺ࠋࡇࢀࢆ⧞ࡾ㏉ࡍࡇࡼࡾࢯ࣮ࢺࡍࡿ ᪉ἲ࡛࠶ࡿࠋࣄ࣮ࣉࡣࢹ࣮ࢱᵓ㐀ࡢࡦࡘ࡛㸪௨ୗࡢࡼ࠺ᐃ⩏ࡉࢀࡿࠋ ᐃ⩏4 㸦ࣄ࣮ࣉ㸧 ḟࡢ 2 ࡘࡢ᮲௳ࢆ‶ࡓࡍ 2 ศᮌࢆࣄ࣮ࣉࡪࠋ (a) 2 ศᮌࡢ᭱ࡢࣞ࣋ࣝࢆ ݈ ࡍࡿ㸪Ͳ ݇ ݈െ ͳ ࢆ‶ࡓࡍྛࣞ࣋ࣝ ݇ ࡣ㸪ʹ ಶࡢ⠇ ⅬࡀᏑᅾࡋ㸪ࣞ࣋ࣝ ݈Ꮡᅾࡍࡿⴥࡣࡑࡢࣞ࣋ࣝᕥワࡵࡉࢀ࡚࠸ࡿࠋ (b) ྛ⠇ⅬಖᏑࡉࢀ࡚࠸ࡿࢹ࣮ࢱࡣ㸪ࡑࡢᏊಖᏑࡉࢀࡿࢹ࣮ࢱࡼࡾࡁ࠸ࠋ ᐃ⩏4 ࡋࡓࡀࡗ࡚ 2 ศᮌࢹ࣮ࢱࢆಖᏑࡋ࡚࠸ࡃ㸪ᚲࡎ᰿್᭱ࡀ᱁⣡ࡉࢀࡿࡇ࡞ࡿࠋ ࡇࡢࣄ࣮ࣉࢆ⏝ࡋ㸪௨ୗࡢ2 ࡘࡢ㛵ᩘࢆ⏝࠸ࡿࡇ࡛ࢯ࣮ࢺࡀࡍࡿࠋ (a) push_heap 㛵ᩘ 㓄ิ᱁⣡ࡉࢀࡓ ݊ ಶࡢࢹ࣮ࢱࡘ࠸࡚㸪ᐃ⩏ 4 (b) ࡢ᮲௳ࢆ‶ࡓࡍࡼ࠺୪᭰࠼ࡢ᧯స ࢆ⾜࠸㸪ࣄ࣮ࣉࡢᛶ㉁ࢆ‶ࡓࡍ2 ศᮌࢆసᡂࡍࡿࠋ (b) delete_maximum 㛵ᩘ (a) ࡛సᡂࡉࢀࡓࣄ࣮ࣉࢆ⾲ࡍ 2 ศᮌᑐࡋ࡚㸪᰿ࡢ್ࡢฟຊࣄ࣮ࣉࡢᵓᡂࢆ ݊ ᅇ⧞ࡾ ㏉ࡋ㸪ࢹ࣮ࢱࢆྲྀࡾฟࡋࡓ㡰୪ࡿࠋ ୖࡢࣝࢦࣜࢬ࣒ࢆࣉࣟࢢ࣒࡛ࣛグ㏙ࡍࡿ௨ୗࡢࡼ࠺࡞ࡿࠋ ࣉࣟࢢ࣒ࣛ5-1 ࣄ࣮ࣉࢯ࣮ࢺ 1 2 3 4 5 6 7 8 9 10 // --- Heapsort 㛵ᩘ --- // void Heapsort(int D[], int n){int i, *T; // ࣏ࣥࢱᆺࡢኚᩘࢆసᡂ (int ᆺ) T = (int*)malloc(sizeof(int)*n+1);
push_heap(D, T, n); for(i = n-1 ; i >= 0 ; i--){
D[i] = delete_maximum(T, i+1); }
free(T); }
(7)
ᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつ ࣉࣟࢢ࣒ࣛ5-1 㛵ࡋ࡚ㄝ᫂ࡍࡿࠋࡲࡎ㸪4 ⾜┠࡛ malloc 㛵ᩘࢆ⏝࠸࡚ࢧࢬ ݊ ͳ ࡢ㓄ิ ࢆ⏕ ᡂࡍࡿࠋ5 ⾜┠࡛ push_heap 㛵ᩘࢆࡧฟࡋ࡚ࣄ࣮ࣉࢆ⏕ᡂࡋ㸪6 ⾜┠⛣ࡿࠋfor ᩥෆࡢ᮲௳ࢆ‶ࡓࡉ ࡞ࡃ࡞ࡿࡲ࡛7 ⾜┠ࢆᐇ⾜ࡉࡏࡿࠋ7 ⾜┠࡛ delete_maximum 㛵ᩘࢆࡧฟࡋ㸪ሾ݅ሿ ᰿ࡢ್ࢆ௦ධࡍ ࡿࠋࡲࡓ㸪push_heap 㛵ᩘࡣ௨ୗࡢࡼ࠺࡞ࡿࠋ ࣉࣟࢢ࣒ࣛ5-2 push_heap 㛵ᩘ 1 2 3 4 5 6 7 8 9 10 11 12 // --- push_heap 㛵ᩘ --- // void push_heap(int D[], int T[], int n){int k, i, size = 1; for(i = 0 ; i < n ; i++){ T[size] = D[i]; k = size; while((T[k] > T[k/2])&&(k > 1)){ swap(T[k], T[k/2]); k = k/2; } size++; } } ࣉࣟࢢ࣒ࣛ5-2 㛵ࡋ࡚㸪ࡲࡎ 4 ⾜┠ࡢ for ᩥෆࡢ᮲௳ࢆ‶ࡓࡉ࡞ࡃ࡞ࡿࡲ࡛ 5 ⾜┠ࡽ 11 ⾜┠ࡲ ࡛ࢆᐇ⾜ࡉࡏࡿࠋ5 ⾜┠࡛ࢹ࣮ࢱࡢ㏣ຍ㸪6 ⾜┠࡛ῧᏐࡢึᮇࢆ⾜࠸㸪7 ⾜┠࡛ぶᏊࡢ್ࢆẚ㍑ࡍ ࡿࠋᏊ (ሾ݇ሿ) ぶ (ሾہ݇ ʹΤ ۂሿ) ࡘ ݇ ͳ ࡀᡂ❧ࡋ࡞ࡃ࡞ࡿࡲ࡛ 8 ⾜┠ࡢ࣭ῧᏐࡢ᭦᪂ࢆ⾜࠺ࠋ while ᩥࢆᢤࡅࡓࡽ 10 ⾜┠࡛ ݏ݅ݖ݁ ࢆࣥࢡ࣓ࣜࣥࢺࡋ㸪ࡇࢀࢆ⧞ࡾ㏉ࡍࡇ࡛ࣄ࣮ࣉࢆసᡂࡍࡿࠋ ࣉࣟࢢ࣒ࣛ5-1 ࡢ 7 ⾜┠ࡢ delete_maximum 㛵ᩘࡣ௨ୗࡢࡼ࠺࡞ࡿࠋ ࣉࣟࢢ࣒ࣛ5-3 delete_maximum 㛵ᩘ 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 // --- delete_maximum 㛵ᩘ --- // int delete_maximum(int T[], int i){
int k, size, big; size = i; T[0] = T[1]; T[1] = T[size]; k = 1; while(2*k <= size){ if(2*k == size){ if(T[k] < T[2*k]){ swap(T[k], T[2*k]); k = 2*k; } else{ break; } } else{ if(T[2*k] < T[2*k+1]) { big = 2 * k + 1; } else{ big = 2 * k; } if(T[k] < T[big]){
swap(T[k], T[big]); k = big; } else{ break; } } } return T[0]; } ࣉࣟࢢ࣒ࣛ5-3 㛵ࡋ࡚ㄝ᫂ࡍࡿࠋ4㹼7 ⾜┠್࡛᭱ࡢྲྀࡾฟࡋ㸪್ࡢ⛣ືࢆ⾜࠸㸪8 ⾜┠ࡽࣄ࣮ ࣉࡢᵓᡂࢆ⾜࠺ࠋ8 ⾜┠࡛Ꮚࡢ᭷↓ࢆ☜ㄆࡋ㸪Ꮚࡀ࠶ࡿሙྜࡣ 9 ⾜┠⛣ືࡍࡿࠋ9 ⾜┠ࡢ if ᩥࡀᡂ
ᩚิࣝࢦࣜࢬ࣒ࡢẚ㍑ホ౯ศ᥈⣴ᤄධࢯ࣮ࢺࡢᥦ
Comparative Evaluation of Some Sorting Algorithms and Proposal of
Binary Search Insertion Sort
ਁ रҲ ʀߧ୫ ᴶߵ̏ʥ
Shuichi SHINMORI1)ː, Haruka ARATANI1)
㮵ඣᓥᏛᏛ㝔⌮ᕤᏛ◊✲⛉ᩘ⌮ሗ⛉Ꮫᑓᨷ
1)Graduate School of Science Engineering, Kagoshima University, Kagoshima 890-0065 * ஸं e-mail address : [email protected]
Abstract: We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new
sorting algorithm. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort)
and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.
Keywords: Sorting algorithm, Insertion sort, Quicksort, Data structure, Numerical experiments.
ࡣࡌࡵ
ᩚิ(sorting) ࡣ㸪㡰ᗎ㞟ྜࡢせ⣲࡛࠶ࡿ」ᩘࡢࢹ࣮ࢱࢆ㸪㡰ᗎࠕӌࠖᚑࡗ࡚ᑠࡉ࠸ࢹ࣮ࢱ ࡽࡁ࠸ࢹ࣮ࢱ୪᭰࠼ࡿࡇ㸦᪼㡰࠸࠺㸧㸪࠶ࡿ࠸ࡣ㏫㸪ࡁ࠸ࢹ࣮ࢱࡽᑠࡉ࠸ࢹ࣮ࢱ ୪᭰࠼ࡿࡇ㸦㝆㡰࠸࠺㸧ࢆ࠸࠸㸪ࢯ࣮ࢺ㸪ࢯ࣮ࢸࣥࢢࡶ࠸࠺ࠋࢡࢵࢡࢯ࣮ࢺ㸪ࣂࣈࣝࢯ ࣮ࢺ㸪ᤄධࢯ࣮ࢺ࡞㸪ᩚิࡢࡓࡵࡢᩘከࡃࡢࣝࢦࣜࢬ࣒ࡀ◊✲ࡉࢀ࡚࠸ࡿࡀ㸪ࡇࢀࡽࢆ⥲⛠ࡋ࡚ᩚ ิࣝࢦࣜࢬ࣒࠸࠺㸦[14], [15]㸧ࠋᡃࠎࡢ㌟㏆࡞ࡇࢁࡣ㸪ᵝࠎ࡞ከࡃࡢࢹ࣮ࢱࡀᏑᅾࡍࡿࠋࡇࢀ ࡽࡢࢹ࣮ࢱࡢ୰ࡣ㸪㡰ᗎӌ࡛㡰ᗎࡅࡽࢀࡿࡶࡢࡀᩘከࡃ࠶ࡿࠋ࠼ࡤ㸪ᩚᩘࡸᐇᩘࡢᩘ್ࢹ࣮ࢱ ࡛࠶ࢀࡤᑠ㡰㸪᪥ᮏㄒࡸⱥㄒࡢ༢ㄒ࡞ࡢᩥᏐࢹ࣮ࢱ࡛࠶ࢀࡤ㸪༑㡢㡰ࡸࣝࣇ࣋ࢵࢺ㡰࡞ ࡢ㎡᭩ᘧ㡰ᗎ࡛ᑠ㛵ಀࡀ࠼ࡽࢀࡿࠋࢹ࣮ࢱࢆຠ⋡Ⰻࡃᩚิࡉࡏࡿ᪉ἲࡣࢹ࣮ࢱࢆ᥈⣴ࡍࡿ᪉ἲ࡞ ୪ࢇ࡛ᇶᮏⓗ࡞ၥ㢟࡛࠶ࡾ㸪௨๓ࡽከࡃࡢ◊✲ࡀ࡞ࡉࢀ࡚࠸ࡿ㸦࠼ࡤ㸪[1], [2], [3], [6], [12]㸧ࠋ ᮏㄽᩥ࡛ࡣ㸪ᩚิࣝࢦࣜࢬ࣒ࡢ୰࡛ࡶ௦⾲ⓗ࡞ 6 ✀㢮ࡢࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ྛࣝࢦࣜࢬ࣒ ࡢᴫせࡢㄝ᫂ࡑࡢC ゝㄒࡼࡿ㛵ᩘᙧ㸦ࣉࣟࢢ࣒ࣛ㸧ࡸࣝࢦࣜࢬ࣒ࡢ⌮ㄽⓗ࡞ᛶ㉁ࢆ♧ࡋ㸪ᐇ㝿 つᶍ࡞ᩘ್ࢹ࣮ࢱᑐࡋ࡚㸪ࡇࢀࡽࡢࣉࣟࢢ࣒ࣛࢆᐇ⾜ࡉࡏࡿᩘ್ᐇ㦂ࡼࡾྛᩚิࣝࢦࣜࢬ ࣒ࡢຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋᚋ༙࡛ࡣ㸪ᤄධࢯ࣮ࢺࡇࢀࢆᨵⰋࡋࡓศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪C ゝ ㄒ࡛ࡢࣉࣟࢢ࣒ࣛࡢ᪉ἲ㸪ᐇ㝿ࡢࢹ࣮ࢱࢆ⏝࠸ࡓᩘ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢホ౯ࢆ⾜࠺ࠋ ➨ 2 ⠇࡛ࡣ㸪ࣝࢦࣜࢬ࣒ࡢホ౯᪉ἲ࡛࠶ࡿ㛫ィ⟬㔞ᩚิࣝࢦࣜࢬ࣒ࡢᏳᐃᛶࡘ࠸࡚㏙ ࡿࠋ➨3㸪4 ⠇࡛ࡣ㸪௦⾲ⓗ࡞ 6 ✀㢮ࡢᩚิࣝࢦࣜࢬ࣒ὀ┠ࡋ㸪ࡇࢀࡽࢆ㛫ィ⟬㔞ࡼࡾ 2 ࡘࡢ ࢢ࣮ࣝࣉศ㢮ࡍࡿࠋࡑࡋ࡚㸪ྛᩚิࣝࢦࣜࢬ࣒ࡢᴫせࡢㄝ᫂㸪C ゝㄒࢆ⏝࠸࡚ࡢࣉࣟࢢ࣒ࣛ㸪ᩘ ್ᐇ㦂ࡼࡿຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨5㸪6 ⠇࡛ࡣ㸪ศ᥈⣴ᤄධࢯ࣮ࢺࢆᥦࡋ㸪ᩘ್ᐇ㦂ࡼ ࡾ㸪ᚑ᮶ࡢᤄධࢯ࣮ࢺࡢຠ⋡ᛶࡢẚ㍑ホ౯ࢆ⾜࠺ࠋ➨㸵⠇ࡣࡲࡵᚋࡢㄢ㢟࡛࠶ࡿࠋ㸰 㛫ィ⟬㔞ࢯ࣮ࢺࡢᏳᐃᛶ
㸰㸯㸬ࣝࢦࣜࢬ࣒ࡢ㛫ィ⟬㔞
ࣝࢦࣜࢬ࣒ࡢィ⟬㔞ࡣಶࠎࡢၥ㢟ࡼࡗ࡚ኚࡍࡿࡢ࡛㸪యⓗ࡞ホ౯ࢆ⾜࠺ࡣၥ㢟ࡢつ ࡾ❧ࡘሙྜ㸪ࡘࡲࡾ㸪Ꮚࡀ1 ࡘࡢሙྜࡣ 10㹼14 ⾜┠ࢆᐇ⾜ࡋ㸪࣭௦ධ᧯సࡶࡋࡃࡣ 24 ⾜┠⛣ ືࡍࡿࠋ9 ⾜┠ࡢ᮲௳ࡀᡂࡾ❧ࡓ࡞࠸ሙྜ㸪ࡘࡲࡾ㸪Ꮚࡀ 2 ࡘࡢሙྜࡣ 16㹼21 ⾜┠ࢆᐇ⾜ࡋ㸪࣭ ௦ධ᧯సࡶࡋࡃࡣ24 ⾜┠⛣ືࡍࡿࠋ8㹼23 ⾜┠ࢆ⧞ࡾ㏉ࡍࡇࡼࡾࣄ࣮ࣉࡀᵓᡂࡉࢀࡓࡽ㸪24 ⾜┠ࢆᐇ⾜ࡋ ሾͲሿ ࡢ್ࢆ Heapsort 㛵ᩘࡢ 7 ⾜┠㏉ࡍࠋ ࣄ࣮ࣉࢯ࣮ࢺࡢ᭱ᝏ㛫ィ⟬㔞ࡘ࠸࡚⪃࠼ࡿࠋࡲࡎ㸪Heapsort 㛵ᩘࡣ 1 ᅇࡢ push_heap 㛵ᩘࡢ ࡧฟࡋ ݊ ᅇࡢ delete_maximum 㛵ᩘࡢࡧฟࡋ࡛ᵓᡂࡉࢀ࡚࠸ࡿࠋpush_heap 㛵ᩘࡣ㸪for ᩥࡼ ࡿ⧞ࡾ㏉ࡋᅇᩘࡀ ݊ ᅇ㸪for ᩥࡢኚᩘ ݅ ౫Ꮡࡋ࡚࠸ࡿ while ᩥࡢ⧞ࡾ㏉ࡋᅇᩘࡣ㸪݇ ൌ ݅ ࡍࡿ᭱ ଶ݇ ᅇ࡛࠶ࡿࠋఱᨾ࡞ࡽ㸪while ᩥࡣⴥ᱁⣡ࡉࢀࡓ್ࢆ᭱ᝏࡢሙྜࡣ᰿ࡲ࡛⛣ືࡉࡏࡿࡶࡢ࡞ ࡢ࡛㸪ᮌࡢࣞ࣋ࣝࡀwhile ᩥࡢ⧞ࡾ㏉ࡋᅇᩘ࡞ࡿࡽ࡛࠶ࡿࠋࡲࡓ㸪delete_maximum 㛵ᩘࡣ heapsort 㛵ᩘࡢfor ᩥࡢኚᩘ ݅ ౫Ꮡࡋ࡚࠸ࡿࠋ݇ ൌ ݅ ࡍࡿ㸪while ᩥࡢ⧞ࡾ㏉ࡋᅇᩘࡣ᭱ ଶ݇ ᅇ࡛࠶ ࡿࠋࡇࢀࡣ㸪push_heap 㛵ᩘྠᵝ࡛㸪while ᩥࡣ᰿⛣ືࡋࡓ್ࢆ᭱ᝏࡢሙྜࡣⴥࡲ࡛⛣ືࡉࡏࡿࡶ ࡢ࡞ࡢ࡛㸪ᮌࡢࣞ࣋ࣝࡀwhile ᩥࡢ⧞ࡾ㏉ࡋᅇᩘ࡞ࡿࡽ࡛࠶ࡿࠋ ௨ୖࡼࡾ㸪ࣄ࣮ࣉࢯ࣮ࢺࡢ᭱ᝏ㛫ィ⟬㔞ࡣḟࡢࡼ࠺࡞ࡾ㸪ド᫂ࡣ┬␎ࡍࡿࡀ㸪᭱Ⰻ㛫ィ⟬㔞ࡶ ߍሺ݊ ݊ሻ ࡛࠶ࡿࡇࡀศࡗ࡚࠸ࡿࠋ ൫ߍሺͳሻ ൈ ሺଶ݇ ଶ݇ሻ൯ ିଵ ୀଵ ൌ ߍሺͳሻ ൈ ʹ ଶ݇ ିଵ ୀଵ ߍሺͳሻ ൈ ʹሺ݊ െ ͳሻ ଶሺ݊ െ ͳሻ ൌ ߍሺ݊ ݊ሻ ᭱ᚋ㸪ࣄ࣮ࣉࢯ࣮ࢺࡢᏳᐃᛶࡘ࠸࡚⪃࠼ࡿࠋࣉࣟࢢ࣒ࣛࡢືసࡽศࡿࡼ࠺㸪ࣄ࣮ࣉࡣධຊ ࡢ㡰ᗎࢆ⪃៖ࡏࡎ್ࡢࢆ⾜࠺ࠋࡑࡢࡓࡵ㸪୍⯡ⓗࣄ࣮ࣉࢯ࣮ࢺࡣᏳᐃᛶࡢ᮲௳ࢆ‶ࡓࡋ࡚࠸ ࡞࠸ࡢ࡛㸪Ᏻᐃ࡞ࢯ࣮ࢺࡍࡿࡓࡵࡣᕤኵࡀᚲせ࡞ࡿࠋ (3) ࣐࣮ࢪࢯ࣮ࢺ ࣐࣮ࢪࢯ࣮ࢺ(Merge sort)ࡣ㸪ධຊࡋࡓࢹ࣮ࢱࢆせ⣲ࡀ 1 ࡘ࡞ࡿࡲ࡛ศࡋ㸪ࡑࡢᚋ㸪࣐࣮ࢪ㸦ే ྜ㸧࠸࠺᧯స࡛ࢯ࣮ࢺࡋ࡞ࡀࡽ⤌ࡳྜࢃࡏࡿࡇࡼࡗ࡚ࢯ࣮ࢺࢆᡂࡉࡏࡿ᪉ἲ࡛࠶ࡿࠋ ࡲࡎ㸪࣐࣮ࢪࡣ㸪ࢯ࣮ࢺ῭ࡳࡢ2 ࡘࡢࢹ࣮ࢱิࢆ 1 ࡘࡢࢯ࣮ࢺࡉࢀࡓࢹ࣮ࢱิేྜࡍࡿࡇ࡛ ࠶ࡿࠋ࣐࣮ࢪࢯ࣮ࢺࡣ㸪௨ୗࡢ2 ࡘࡢ㛵ᩘࢆ⏝࠸ࡿࡇ࡛ࢯ࣮ࢺࡀࡍࡿࠋ (a) Mergesort 㛵ᩘ㸦ศ㸧 ධຊࡋࡓࢹ࣮ࢱࢆ㸪ଵൌ ൛݀ǡ ݀ଵǡ ڮ ǡ ݀ ଶΤ ିଵൟ㸪ଶൌ ൛݀ ଶΤ ǡ ݀ ଶΤ ାଵǡ ڮ ǡ ݀ିଵൟ ࠸࠺ 2 ࡘࡢ㞟ྜ ศࡍࡿࠋせ⣲ࡀ1 ࡘ࡞ࡿࡲ࡛ᖐ㛵ᩘࢆ⏝࠸࡚⧞ࡾ㏉ࡍࠋ (b) merge 㛵ᩘ 㞄ྠኈࡢ㞟ྜ ଵ 㞟ྜ ଶ ࢆ࣐࣮ࢪࡍࡿࠋࡇࡢ᧯సࢆ㞟ྜࡀ 1 ࡘ࡞ࡿࡲ࡛⧞ࡾ㏉ࡍࠋ ୖࡢศࡍࡿMergesort 㛵ᩘࢆࣉࣟࢢ࣒࡛ࣛグ㏙ࡍࡿ௨ୗࡢࡼ࠺࡞ࡿࠋ ࣉࣟࢢ࣒ࣛ6-1 Mergesort 㛵ᩘ 1 2 3 4 5 6 7 8 9 // --- Mergesort --- // void Mergesort(int D[], int left, int right){int mid;
if(left >= right) return; mid = (left + right) / 2;
if(left<mid) Mergesort(D, left, mid);
if(mid+1<right) Mergesort(D, mid + 1, right); merge(D, left, mid, right);
}
ࣉࣟࢢ࣒ࣛ6-1 ࡘ࠸࡚ㄝ᫂ࡍࡿࠋ4 ⾜┠࡛㓄ิ ྵࡲࢀࡿせ⣲ࡢᩘࢆ☜ㄆࡋ㸪せ⣲ᩘࡀ 2 ࡘ௨ ୖࡢሙྜ5 ⾜┠㐍ࡴࠋ5 ⾜┠࡛ ݉݅݀ ࡢ್ࢆィ⟬ࡋ㸪6࣭7 ⾜┠࡛㓄ิࢆ 2 ࡘศࡅࡿࠋࡇࡢ᧯సࢆ⧞
