アルゴリズムとデータ構造 - ソート編

はじめに

こんにちは、BRANU開発部でバックエンドエンジニアを担当している遠藤です。

近年、面接内でコーディングテストを取り入れている企業が増えております。

その中で、ソートアルゴリズムは頻繁に質問される分野になるかと思います。

そこで今回は、簡単にではありますがソートアルゴリズムの一部についてご紹介させていただきます。

環境

• Windows10
• Ruby

ソートの種類

• バブルソート
• 選択ソート
• 挿入ソート
• クイックソート
• マージソート

バブルソート

特徴 :

配列の隣合う値の大小を比較し、もし前の値が大きければ値の前後を入れ替える。

この処理を繰り返し、一番大きい値を配列の一番後ろに移動させ後ろの方から並び順を確定させて並び替えを行っていきます。

実装自体は簡単ですが、最悪計算量がo(n²)となり時間を要するソート手法になります。

動画 :

www.youtube.com

コード :

def bubble_sort(nums)
    nums.size.times do |i|
        (nums.size - i - 1).times do |j|
            # 現在の値と次の値を比較し、現在の値が大きければ入れ替え
            if nums[j] > nums[j + 1]
                nums[j],nums[j + 1] = nums[j + 1],nums[j]
            end
        end
    end
    nums
end

nums = [2,5,4,3,1])
print(bubble_sort(nums))

選択ソート

特徴 :

配列の中から最小値を検索し、配列の先頭の値と入れ替えていきます。

次のループでは、ループ回数の位置の値と最小値を交換することで徐々に先頭の方から小さい順に値を並び順確定させていきます。

こちらも、実装は比較的簡単なものになっておりますが、最悪計算量がo(n²)と時間がかかるものになっています。

動画 :

www.youtube.com

コード :

def select_sort(nums)
    nums.size.times do |i|
　　　　# 現在の先頭の位置を取得
        min_index = i
        (nums.size - i - 1).times do |j|
            compare_index = j + i + 1
            # 現在の先頭と値と次の値を比較し、先頭の値より大きければ先頭の値を入れ替え
            if nums[min_index] > nums[compare_index]
                min_index = compare_index
            end
        end
        # 値を入れ替え
    　　　# もし、先頭が最小値の場合は [min_index]と[i]が同じ値のため入れ替えは行われない
        nums[i],nums[min_index] = nums[min_index],nums[i]
    end
    nums
end

nums = [2,5,4,3,1]
print(select_sort(nums))

挿入ソート

特徴 :

値の入れ替えをした場合は、一つ前に戻り入れ替えした値と一つ前の値を比較し再度後の値が大きければ入れ替えを行います。

こうして、一つ一つ値の位置を確定させていきます。

これを配列の要素分繰り返して最後の要素まで処理を行っていきます。

動画 :

www.youtube.com

コード :

def insertion_sort(nums)
    i = 0
    while i < nums.size - 1
                # 現在の値と一つ後ろの値を比較
        if nums[i] > nums[i + 1]      
                        # 現在の値より、後ろの値が小さければ現在の位置と入れ替え                
            nums[i],nums[i + 1] = nums[i + 1], nums[i]
            if i > 0
　　　　　　　　 # 現在の位置から一つ前に戻り、入れ替えた値と現在の位置の一つ前の値と比較する
                i = i - 1
                next
            end
        end
        i = i + 1
    end
    nums
end

nums = [2,5,4,3,1]
print(select_sort(nums))

クイックソート

特徴 : 一番後ろを基準値とし、「基準値より大きい値」「基準値より小さい値」の分割・ソートをすべての要素が並び終えるまで繰り返すソート手法になります。

一般的に一番高速に動作するアルゴリズムだと言われていますが、データによっては処理に時間がかかります。

動画 :

www.youtube.com

コード :

def quick_sort(nums,left,right)
    # leftがrightより大きければソートが完了したとみなし再帰呼び出しを終了
    if left < right
        partion_index = partition(nums, left,right)
        quick_sort(nums,left,partion_index - 1 )
        quick_sort(nums,partion_index + 1  ,right)
    end
    nums
end
 
# 基準値を求める 
def partition(nums,left,right)
    j = left -1
    # 基準値を取得
    pivot = nums[right]
    (right - left).times  do |i|
        current_index = i + left
        if nums[current_index] <= pivot
            j += 1
            nums[j],nums[current_index] = nums[current_index],nums[j]
        end
    end
    nums[j + 1],nums[right] = nums[right],nums[j + 1]
    return j + 1
end

nums = [2,5,4,3,1]
print(quick_sort(nums,0, nums.size - 1))

マージソート

特徴 : 配列を分割して分割がこれ以上できないようになったら、分割した配列を利用し大小を比較して並び替えを行いながら新しい配列を作成していきます。

こちらのアルゴリズムの最悪計算量はo(N log N)と早いですが、実行速度はクイックソートより遅いものとなっています。

動画 :

www.youtube.com

コード :

def merge_sort(nums)
    if nums.size <= 1
        return nums
    end
    center = nums.size / 2
    left_side = nums.slice!(0..center - 1)
    right_side = nums.slice!(0..nums.size)

    merge_sort(left_side)
    merge_sort(right_side)

    l = r = k = 0
    while left_side.size > l && right_side.size > r
        if left_side[l] <= right_side[r]
            nums[k] = left_side[l]
            l = l + 1
        else
            nums[k] = right_side[r]
            r = r + 1
        end
        k = k + 1
    end

    while left_side.size > l
        nums[k] = left_side[l]
        k = k + 1
        l = l + 1
    end

    while right_side.size > r
        nums[k] = right_side[r]
        k = k + 1
        r = r + 1
    end
    return nums
end

nums = [5,2,4,3,1]
puts(merge_sort(nums))

まとめ

今回は簡単ではありますが、ソートアルゴリズムについてご紹介させていただきました。

実務で実装することは中々ないですが、GAFA等の企業では技術面接などでも聞かれる内容になっており、これから日本国内の企業でも技術面接に取り入れていく企業が増えていくかと思います！

エンジニアとして是非、押さえておいていた方が良いかと思います。

(こんなことを言っていますが、私も全部覚えているわけではないので絶賛勉強中です。^^;)

BRANUではバックエンジニアを積極的に募集しています！Railsを使ったAPI開発に興味がある方、建設業界向けのプロダクト開発に興味がある方はぜひご応募ください！

www.wantedly.com