Why not login to Qiita and try out its useful features?

We'll deliver articles that match you.

You can read useful information later.

8
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

【アルゴリズム】色々なソートと計算量をGo言語でまとめてみた

Last updated at Posted at 2023-08-31

名前は聞いたことあるけれどソートアルゴリズムの違いが分からない

普段業務中にソートロジックが必要になる機会は少なくありません。特に立ち上がって間もないスタートアップ等、小規模なサービスにおいて、基本的には各言語・Frameworkが用意している関数を利用するだけで問題無いことが多いです。

一方で、計算量・アルゴリズムの理解の第一歩として、ソートアルゴリズムを改めて勉強してみると、今まであまり意識せずとも済んでいたアルゴリズムの分野への理解が深まるためとても良い機会になります。

本記事では、ソートアルゴリズムのみに着目、各ソートの特徴とサンプルコード(Go言語)を用いて紹介していきます。

ご留意ください
筆者はアルゴリズムの専門家ではありません。本記事も自分のインプットの備忘的な意味合いも込めているため見にくい点はご容赦ください。正式な情報は各種文献にお任せいたします。

ソートアルゴリズムとは

ソートアルゴリズムとは、データを特定の順序(通常は昇順または降順)に並べ替えるための手法やプロセスのことを指します。有名なものとしては以下のようなものがあります。

  • バブルソート(Bubble Sort)
  • クイックソート(Quick Sort)
  • マージソート(Merge Sort)
  • インサーションソート(Insertion Sort)
  • ヒープソート(Heap Sort)
    ..etc

それぞれのアルゴリズムは、特定のケースやデータ構造において効率的な場合があります。一般的に、ソートアルゴリズムはその性能(時間計算量)や安定性などによって評価されます。

昇順にソートするサンプルコード
package main

import (
	"fmt"
	"sort" // Goのソート用標準ライブラリ
)

func main() {
	// ソートしたい整数のスライス
	numbers := []int{5, 2, 9, 1, 5, 6}

	// 昇順にソート
	sort.Ints(numbers)

	// ソート後のスライスを出力
	fmt.Println("Sorted:", numbers)
}

// 回答:[1, 2, 5, 5, 6, 9]

プログラムの計算量

本記事において計算量はそれぞれ、以下の項目で整理してみました。

  • 平均計算量: アルゴリズムがランダムな入力に対して要する平均的な計算時間やステップ数。
  • 最悪計算量: アルゴリズムが最も非効率な場合に要する計算時間やステップ数の上限。
  • 最良計算量: アルゴリズムが最も効率的な場合に要する計算時間やステップ数の下限。
  • 空間計算量:空間計算量: アルゴリズムが実行中に使用する追加メモリの量を表す指標。

また、計算量の記述方法についてはオーダー記法を用いています。
例として、入力サイズnの関数として表される時間計算量T(n)が以下のように与えられる場合、

T(n)=10n2+100n+1000
$${T(n)=10n2+100n+1000 }$$

オーダー記法では最も次数の高い項の係数を省いてこのように表します。

O(n^2)
$${O(n^2) }$$

最も次数の高い項(主要項)の係数を省く評価を行う背景として、入力サイズnが十分に大きい場合は、時間計算量は主要項にのみ依存するためです。

詳細は以下のラクスさんの記事が非常にシンプルで分かり易いのでおすすめです。

名称 計算量 概要
線形時間複雑度 O(n) 入力サイズ n に比例して処理時間が増加します。例として、配列内の要素の合計を計算する単純なループがあります。
(二次)時間複雑度 O(n^2) 入力サイズ n の二重ループを持ちます。
対数時間複雑度 O(log n) 入力サイズ n に対して対数的に増加します。n=8の場合は3です。
線形対数時間複雑度 O(n log n) この計算量のアルゴリズムは、nlog n の関係を持ちます。n=8の場合は8×3=24になります。

Go言語を用いて代表的なソートアルゴリズムを書いてみる

ここからが本題になります。本記事ではGo言語を用いて代表的なソートアルゴリズムを紹介していきます。ここでは、ライブラリ等は用いずスクラッチでソートアルゴリズムを記述してみます。全項目で以下の項目でまとめていきます。

  • 各ソートの特徴と概要
  • サンプルコード
  • 計算量

1. 選択ソート(Selection Sort)

選択ソートは、未ソート部分から最小(または最大)の要素を探して、先頭(または末尾)と交換することを繰り返して配列をソートするアルゴリズムです。簡単で直感的な手法ですが、一般には非効率な方法とされています。

1-1. サンプルコード

func SelectionSort(nums []int) []int {
	// 配列の長さを取得
	n := len(nums)

	// 外側のループ(このループが終わると、i番目の要素はソート済みになる)
	for i := 0; i < n-1; i++ {
		// 最小値の位置を見つけるための変数。初期値としてiを設定
		minIndex := i

		// 内側のループ(最小値の位置を探す)
		for j := i + 1; j < n; j++ {
			// より小さい値を見つけた場合、minIndexを更新
			if nums[j] < nums[minIndex] {
				minIndex = j
			}
		}

		// i番目と最小値の位置を交換
		if i != minIndex {
			nums[i], nums[minIndex] = nums[minIndex], nums[i]
		}
	}

	return nums
}

1-2. 処理の流れ

このコードは、選択ソート(Selection Sort)というアルゴリズムを実装したものです。選択ソートは、配列の中から最小値(または最大値)を見つけて、それを配列の先頭に移動するという操作を繰り返すことで配列全体をソートするアルゴリズムです。

具体的な配列のサンプルを用いて説明します。例えば、次のような整数の配列があるとします:

nums := []int{64, 25, 12, 22, 11}

この配列を選択ソートでソートすると以下のようになります:

  1. 最初に、配列全体から最小値を見つけます。この場合、最小値は11で、その位置(インデックス)は4です。この最小値を配列の先頭(0番目)と交換します:

    nums := []int{11, 25, 12, 22, 64}
    
  2. 次に、先頭の要素を除いた残りの部分(25, 12, 22, 64)から最小値を見つけます。この場合、最小値は12で、その位置は2です。この最小値を残りの部分の先頭(1番目)と交換します:

    nums := []int{11, 12, 25, 22, 64}
    
  3. 同様に、残りの部分(25, 22, 64)から最小値を見つけて先頭と交換し、以下同様に続けます:

    nums := []int{11, 12, 22, 25, 64}
    
  4. 最終的に、全ての要素がソートされた状態になります:

    nums := []int{11, 12, 22, 25, 64}
    

以上が選択ソートの基本的な動作です。このコードでは、外側のループでソート済みの部分と未ソートの部分を分け、内側のループで未ソート部分から最小値を見つけています。

1-3. 計算量

  • 最悪計算量:
O(n^2)
$${O(n^2) }$$
  • 最良計算量:
O(n^2)
$${O(n^2) }$$
  • 平均計算量:
O(n^2)
$${O(n^2) }$$
  • 空間計算量:
O(1)
$${O(1) }$$

外側のループ: n回のイテレーションが必要です。具体的には、iは0からn-2までのn-1回のイテレーションが行われます。

内側のループ: 最初のイテレーションではn-1回、次のイテレーションではn-2回、…、最後のイテレーションでは1回の比較が行われます。これは累計で約n(n-1)/2、つまりO(n^2)の比較となります。

選択ソートにおいては、最良のケースでも計算量は O(n^2)です。これは選択ソートが未ソート部分から最小(または最大)の要素を選ぶ操作を(n-1)回行わなければならないため、最良のケースでもO(n^2)の計算量が必要となります。

2. バブルソート(Bubble Sort)

バブルソートは、隣接する要素を比較して入れ替えを繰り返す、非常に基本的なソートアルゴリズムです。最も簡単に実装できる一方で、効率は低いとされています。一方で、安定なソートが可能で"インプレース"、つまり追加のメモリをほとんど使用しないソート方法になります。選択ソートはインプレースアルゴリズムであり、追加のメモリをほとんど必要としないため、その空間計算量はO(1)です。

2-1. サンプルコード

func BubbleSort(nums []int) []int {
	// 配列の長さを取得
	n := len(nums)
	// 外側のループ	
	for i := 0; i < n; i ++ {
		// 内側のループ"n-i-1"は右側のソート済みの部分を無視して、未ソート部分だけを効率的に処理するため
		for j := 0; j < n-i-1; j ++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}

	return nums
}

2-2. 処理の流れ

バブルソートの具体的な動作を配列の例を用いて説明します。例えば、次のような整数の配列があるとします:

nums := []int{64, 25, 12, 22, 11}

この配列をバブルソートでソートすると以下のようになります:

  1. 最初に、配列全体を左から右へと見ていきます。隣接する要素を比較し、左側が右側よりも大きければ交換します。この操作を繰り返すと、最大値が配列の右端に移動します:

    nums := []int{25, 12, 22, 11, 64}
    
  2. 次に、先頭から右端の一つ手前まで同様の操作を行います。すると、2番目に大きな値が右端から2番目の位置に移動します:

    nums := []int{12, 22, 11, 25, 64}
    
  3. 同様に、先頭から右端から3番目までの部分で操作を行います:

    nums := []int{12, 11, 22, 25, 64}
    
  4. 最後に、先頭から右端から4番目までの部分で操作を行います:

    nums := []int{11, 12, 22, 25, 64}
    

以上がバブルソートの基本的な動作です。このコードでは、外側のループでソート済みの部分と未ソート部分を分け、内側のループで未ソート部分を左から右へと見ていき、隣接する要素を比較して順序が逆であれば交換しています。

2-3. 計算量

  • 最悪計算量:
O(n^2)
$${O(n^2) }$$
  • 最良計算量:
O(n)
$${O(n) }$$
  • 平均計算量:
O(n^2)
$${O(n^2) }$$
  • 空間計算量:
O(1)
$${O(1) }$$

バブルソートにおいては、最良のケースでも計算量が O(n)となり得ます。これは、入力配列が既にソートされている場合、バブルソートは一回の走査でソートが完了するためです。ただし、最悪ケースでは、隣接する要素を比較・交換する操作が一定回数以上実行される可能性があるため、計算量はO(n^2)となります。

3. 挿入ソート(Insertion Sort)

挿入ソート(Insertion Sort)は、データを順序付けるためのアルゴリズムです。このアルゴリズムは、リスト内で一つずつ要素を選び、その要素をリストの既にソートされた部分に適切な位置に移動させていくという操作を繰り返します。

3-1. サンプルコード

func insertionSort(nums []int) []int {
	// 二番目の要素から開始
	for i := 1; i < len(nums); i++ {
		// (1)基準となる要素
		key := nums[i]
		// (2)(1)の基準となる要素の左側に位置する要素を選択する用のインデックス
		j := i - 1
        // (3)(2)が0より大きい=内側に要素が存在する && 内側の要素の方が対象となるキーより大きい
		for j >= 0 && nums[j] > key {
			// (4)(2)の内側の要素の右側に値を格納する
			nums[j+1] = nums[j]
			// (5)(2)を左に一つずらす
			j--
		}
		
		// ループが終了した際の内側の最初の位置を指定して値を格納する
		nums[j+1] = key
	}
	return nums
}

3-2. 処理の流れ

このコードは挿入ソート(Insertion Sort)というアルゴリズムを実装したものです。挿入ソートは、未ソートの部分から要素を一つずつ取り出し、ソート済みの部分に適切な位置に挿入することで配列全体をソートします。

具体的な配列の例を用いて説明します。例えば、次のような整数の配列があるとします:

nums := []int{64, 25, 12, 22, 11}

この配列を挿入ソートでソートすると以下のようになります:

  1. 最初に、25i=1の位置)を取り出し、それが64より小さいため6425を交換します:

    nums := []int{25, 64, 12, 22, 11}
    
  2. 次に、12i=2の位置)を取り出し、それが6425より小さいため、これらの要素を右にシフトして12を先頭に挿入します:

    nums := []int{12, 25, 64, 22, 11}
    
  3. 同様に、22i=3の位置)を取り出し、それが適切な位置(2564の間)に挿入します:

    nums := []int{12, 22, 25, 64, 11}
    
  4. 最後に、11i=4の位置)を取り出し、それが全ての要素より小さいため先頭に挿入します:

    nums := []int{11, 12, 22, 25, 64}
    

以上が挿入ソートの基本的な動作です。このコードでは、外側のループで未ソート部分から要素を一つずつ取り出し、内側のループでその要素をソート済み部分の適切な位置に挿入しています。

3-3. 計算量

  • 最悪計算量:
O(n^2)
$${O(n^2) }$$
  • 最良計算量:
O(n)
$${O(n) }$$
  • 平均計算量:
O(n^2)
$${O(n^2) }$$
  • 空間計算量:
O(1)
$${O(1) }$$

挿入ソートでも、最良のケースで計算量がO(n)となります。これは、入力配列が既にソートされている場合、内部のループが不要となるためです。しかし、平均ケースと最悪ケースでは、各要素を適切な位置に挿入するための比較・移動が一定回数行われる可能性があるため、計算量はO(n^2)となります。

4. マージソート(Merge Sort)

マージソートは分割統治法に基づくソートアルゴリズムです。元のデータをより扱いやすい小さな単位に分割し、それぞれをソートした後で統合(マージ)していきます。このアルゴリズムは安定なソートを提供し、大量のデータにも効率的に適用できます。

4-1. サンプルコード

// マージソート関数
func mergeSort(arr []int) []int {
	// 配列の要素数が1以下の場合、そのまま返す
	if len(arr) <= 1 {
		return arr
	}

	// 配列を中央で2つに分割
	mid := len(arr) / 2
	left := arr[:mid]
	right := arr[mid:]

	// 左右の配列をそれぞれ再帰的にソート
	left = mergeSort(left)
	right = mergeSort(right)

	// 2つのソート済み配列をマージ(結合)して返す
	return merge(left, right)
}

// 2つのソート済み配列をお互いの要素を一つずつ比較してマージする関数
func merge(left, right []int) []int {
	// 結果格納スライス
	result := make([]int, 0, len(left)+len(right))
	
	// 左右のソート済み配列のループ用のイテレーター
	l, r := 0, 0

	// leftとrightのどちらも要素が残っている間は、小さい方の要素をresultに追加
	for l < len(left) && r < len(right) {
		if left[l] < right[r] {
			result = append(result, left[l])
			l++
		} else {
			result = append(result, right[r])
			r++
		}
	}
	
	/*
	各left, rightともにスライスは既にソート済みであるため、
	先に処理が完了した後に残っている配列は最後尾に追加可能
	 */

	// leftに残った要素があればresultに追加
	result = append(result, left[l:]...)

	// rightに残った要素があればresultに追加
	result = append(result, right[r:]...)

	return result
}

4-2. 処理の流れ

このコードはマージソート(Merge Sort)というアルゴリズムを実装したものです。マージソートは、配列を2つに分割し、それぞれをソートした後で結合(マージ)することで配列全体をソートします。

具体的な配列の例を用いて説明します。例えば、次のような整数の配列があるとします:

nums := []int{64, 25, 12, 22, 11}

この配列をマージソートでソートすると以下のようになります:

  1. 最初に、配列全体を2つに分割します。この場合、{64, 25}{12, 22, 11}の2つの部分配列になります。

  2. 各部分配列を再帰的にソートします。まず、{64, 25}をソートすると{25, 64}になります。次に、{12, 22, 11}をソートすると{11, 12, 22}になります。

  3. ソート済みの2つの部分配列をマージします。この場合、{25, 64}{11, 12, 22}をマージすると、{11, 12, 22, 25, 64}というソート済みの配列が得られます。

以上がマージソートの基本的な動作です。このコードでは、mergeSort関数で配列を分割し、それぞれを再帰的にソートしています。そして、merge関数で2つのソート済み部分配列をマージしています。

4-3. 計算量

  • 最悪計算量:
O(n \log n)
$${O(n \log n) }$$
  • 最良計算量:
O(n \log n)
$${O(n \log n) }$$
  • 平均計算量:
O(n \log n)
$${O(n \log n) }$$
  • 空間計算量:
O(n)
$${O(n) }$$

マージソートでは、最悪ケースでも最良ケースでも計算量はO(n log n) です。これは、分割と統合の過程が均一であるため、データの初期状態に依存しない計算量が確保されます。空間計算量は、新たな配列(スライス)を作成する際に必要なメモリは、入力配列のサイズnに比例するため、O(n)になります。

以下の表記の補足

O(n \log n)
$${O(n \log n) }$$

マージソートの計算量がO(n log n)とされるのは、以下の2つの主な要因からです:

  1. 分割のステップ: 入力配列がlog 2 n のレベルで分割されます。たとえば、要素数が8の配列は、3回の分割log 2 8 = 3を経て、最終的に個々の要素に分解されます。

  2. マージのステップ: 各レベルで、分割された配列(またはサブ配列)をマージする操作が行われます。マージ操作は線形時間、すなわちO(n)、で実行されるので、(n)個の要素が存在する場合、マージ操作には (n) ステップが必要です。

これらを組み合わせると、全体で n × log 2 n ステップが必要になり、オーダー記法では上記のような表現になるようです。

5. クイックソート(Quick Sort)

クイックソートは、分割統治法を基にしたソートアルゴリズムです。ピボットと呼ばれる要素を選び、ピボットより小さい要素と大きい要素にデータを分割します。この分割を繰り返し、最終的に全体がソートされた状態になります。クイックソートはインプレース(in-place)と非インプレース(not in-place)の両方の形で実装することができるようです。ここでのサンプルは、各再帰呼び出しで新しいスライスを作成しているため、非インプレースになります。

5-1. サンプルコード

// quickSort関数
func quickSort(nums []int) []int {
	// 配列の長さが1以下の場合は、すでにソートされているとみなし、そのまま返す。
	if len(nums) <= 1 {
		return nums
	}

	// ピボットを選ぶ(中央の要素をピボットとして選ぶ)
	pivot := nums[len(nums)/2]

	// ピボットより小さい要素を格納するスライス
	var left []int
	// ピボットと等しい要素を格納するスライス
	var middle []int
	// ピボットより大きい要素を格納するスライス
	var right []int

	// 入力されたスライスをピボットに基づいて3つのスライス(left, middle, right)に分割
	for _, value := range nums {
		if value < pivot {
			left = append(left, value)
		} else if value == pivot {
			middle = append(middle, value)
		} else {
			right = append(right, value)
		}
	}

	// left と right スライスを再帰的にソート
	left = quickSort(left)
	right = quickSort(right)

	// 分割したスライスを結合して、ソートされたスライスを作成
	left = append(left, middle...)
	left = append(left, right...)
	return left
}

5-2. 処理の流れ

このコードはクイックソート(Quick Sort)というアルゴリズムを実装したものです。クイックソートは、配列をピボットと呼ばれる要素を基準に2つに分割し、それぞれを再帰的にソートすることで配列全体をソートします。

具体的な配列の例を用いて説明します。例えば、次のような整数の配列があるとします:

nums := []int{64, 25, 12, 22, 11}

この配列をクイックソートでソートすると以下のようになります:

  1. 最初に、ピボット(中央の要素)を選びます。この場合、ピボットは12です。

  2. ピボットより小さい要素(11)、ピボットと等しい要素(12)、ピボットより大きい要素(64, 25, 22)をそれぞれ別のスライスに分割します。

  3. ピボットより小さい要素と大きい要素を含むスライスをそれぞれ再帰的にソートします。この場合、それぞれのスライスは1つの要素しか含まないため、すでにソートされているとみなせます。

  4. ソート済みの3つのスライスを結合します。これにより、{11, 12, 22, 25, 64}というソート済みの配列が得られます。

以上がクイックソートの基本的な動作です。このコードでは、quickSort関数で配列をピボットを基準に分割し、それぞれを再帰的にソートしています。そして、3つのスライス(ピボットより小さい要素、ピボットと等しい要素、ピボットより大きい要素)を結合しています。

5-3. 計算量

  • 最悪計算量:
O(n^2)
$${O(n^2) }$$
  • 最良計算量:
O(n \log n)
$${O(n \log n) }$$
  • 平均計算量:
O(n \log n)
$${O(n \log n) }$$
  • 空間計算量:
O(\log n)
または
O(n)
$${O(\log n) または O(n) }$$

最悪計算量: O(n^2)
最悪の場合は、配列がすでにソートされているか、逆順にソートされている場合です。この場合、ピボットとして選ばれる要素は常に配列の最小値または最大値となります。その結果、配列は「1つの要素」と「残りのすべての要素」の2つの部分配列に偏って分割されます。これにより、再帰的な呼び出しの深さ(すなわち、分割のステップ数)がnになり、各ステップでn個の要素を処理するため、全体の計算量はO(n^2)となります。

最良計算量: O(n log n)
最良の場合は、各ステップで配列が均等に分割される場合です。つまり、ピボットが常に中央値となる場合です。これにより、再帰的な呼び出しの深さ(すなわち、分割のステップ数)がlog nとなります。各ステップではn個の要素を処理するため、全体の計算量はO(n log n)となります。

平均計算量: O(n log n)
平均的な場合でも、クイックソートはほぼ均等に配列を分割します。したがって、最良の場合と同様に、平均計算量もO(n log n)となります。

空間計算量: O(log n)またはO(n)
クイックソートはインプレースソートであり、追加のメモリを必要としないため、空間計算量は通常O(log n)です。ただし、これは最良の場合であり、最悪の場合(すなわち、再帰的な呼び出しの深さがnである場合)ではO(n)となります²。

6. ヒープソート(Heap Sort)

ヒープソートは、比較に基づくソートアルゴリズムの一つです。このアルゴリズムは、バイナリヒープ(通常は最大ヒープ)を使用して配列をソートします。ヒープソートは、内部ソートと外部ソートの両方に使用でき、データの大きさによらず安定した速度でソートを行うことができます。

ヒープソートは主に2つのフェーズからなります:

  1. ビルドフェーズ: 元の配列を最大ヒープに変換します。
  2. ソートフェーズ: ヒープから最大要素を取り出し、配列の末尾に移動させます。その後、残ったヒープを再ヒープ化します。このステップをヒープが空になるまで繰り返します。

またヒープソートの理解のためには最大ヒープという概念を理解する必要があります。

最大ヒープとは

最大ヒープとは、各ノードの値がその子ノードの値よりも大きい、完全二分木の一種です。例として、以下のような数値を持つ配列が考えられます。

配列: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

この配列は最大ヒープのプロパティを満たしています。これをツリー形式で表すと以下のようになります。

       16
     /    \
   14      10
  /  \    /   \
 8    7  9     3
/ \  / \
2  4 1

6-1. サンプルコード

// heapify は部分配列を最大ヒープに変換します。
// arr: 元の配列, n: 配列のサイズ, i: ヒープのルートとする要素のインデックス
func heapify(arr []int, n int, i int) {
	largest := i               // 最大値を持つ要素のインデックスを初期化
	l := 2*i + 1               // 左の子ノードのインデックス
	r := 2*i + 2               // 右の子ノードのインデックス

	// 左の子ノードが存在し、その値が現在の「最大値」よりも大きいかどうか
	if l < n && arr[l] > arr[largest] {
		largest = l
	}

	// 右の子ノードが存在し、その値が現在の「最大値」よりも大きいかどうか
	if r < n && arr[r] > arr[largest] {
		largest = r
	}

	// largestがiから変更された場合、要素を交換してサブツリーをヒープ化
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i] // 交換
		heapify(arr, n, largest)                    // 交換後のサブツリーをヒープ化
	}
}

// heapSort は配列をヒープソートでソートします。
func heapSort(arr []int) []int {
	n := len(arr) // 配列のサイズ

	// ビルドフェーズ: 全体を最大ヒープに変換
	// 配列の後半部分(中央から末尾)はすべて葉(子ノードを持たないノード)であるた不要
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}

	// ソートフェーズ: ヒープから一つずつ最大要素を取り出して配列の後ろから埋めていく
	for i := n - 1; i >= 0; i-- {
		arr[0], arr[i] = arr[i], arr[0] // ルートと最後の要素を交換

        // 交換後のサブツリー、すなわち最大値を除いた範囲で再びヒープ化
		heapify(arr, i, 0)              
	}

	return arr
}

補足

	// ビルドフェーズ: 全体を最大ヒープに変換
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}

配列の中央から先頭に向かって各要素に対してheapify関数を呼び出しています。これにより、各要素をルートとする部分木が最大ヒープの性質を満たすようになります。

なぜ中央から先頭に向かって処理するのかというと、ヒープは完全二分木であり、配列の後半部分(中央から末尾)はすべて葉(子ノードを持たないノード)であるためです。したがって、これらの要素はすでに最大ヒープの性質を満たしています(自身が唯一の要素であるため)。そのため、実際には配列の前半部分(中央から先頭)だけを対象にheapify関数を呼び出す必要があります。

6-3. 処理の流れ

このコードはヒープソート(Heap Sort)というアルゴリズムを実装したものです。ヒープソートは、配列を最大ヒープ(親ノードが子ノードよりも大きい完全二分木)に変換し、その最大値(ルート)を取り出して配列の最後に移動することを繰り返すことで配列全体をソートします。

具体的な配列の例を用いて説明します。例えば、次のような整数の配列があるとします:

nums := []int{64, 25, 12, 22, 11}

この配列をヒープソートでソートすると以下のようになります:

  1. 最初に、配列全体を最大ヒープに変換します。これはheapify関数を用いて行います。この場合、最大値(64)がルートになります。具体的には、以下のような最大ヒープが構築されます:

        64
       /  \
     25    12
    /  \
    22   11
    
  2. ヒープから最大値を取り出し(ルートと最後の要素を交換し、ヒープのサイズを1つ減らす)、その最大値を配列の最後に移動します:

    nums := []int{25, 22, 12, 11, 64}
    
  3. ヒープが空になるまで、ヒープから最大値を取り出して配列の未ソート部分の先頭に移動する操作を繰り返します:

    nums := []int{22, 12, 11, 25, 64}
    nums := []int{12, 11, 22, 25, 64}
    nums := []int{11, 12, 22, 25, 64}
    

以上がヒープソートの基本的な動作です。このコードでは、heapSort関数で配列全体をヒープソートし、heapify関数で部分配列を最大ヒープに変換しています。

6-3. 計算量

  • 最悪計算量:
O(n \log n)
$${O(n \log n) }$$
  • 最良計算量:
O(n \log n)
$${O(n \log n) }$$
  • 平均計算量:
O(n \log n)
$${O(n \log n) }$$
  • 空間計算量:
O(1)
$${O(1) }$$

ヒープソートは、最悪、最良、平均のすべてのケースでO(n log n)の時間計算量を持っています。これは、ビルドフェーズでのヒープ構築がO(n)、ソートフェーズでの各要素の取り出しがO(log n)であり、合計n回取り出す必要があるためです。これらを合計するとO(n log n)になります。ヒープソートは、安定なソートではありません。つまり、等しい値の元の順序が保持されるわけではありません。本実装はインプレース(元の配列内での操作)であり、追加のメモリを使用しないため、空間計算量はO(1)です。

8
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up

Comments

No comments

Let's comment your feelings that are more than good

8
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Login to continue?

Login or Sign up with social account

Login or Sign up with your email address