下から上に行く

新卒エンジニアが書くブログです

Pythonの練習でソートをかく

CTFとかセキュリティの勉強してるとPythonしかででこないので代表的なソートアルゴリズムで練習してみる
Pythonは普段全く書かないから汚いコードでも許して、、、

ソートの説明は割愛します!!!

BubleSort

まずはバブルソートから

import random

def buble_sort(seq):
  seq_n = len(seq)
  for i in range(seq_n):
    for k in range(1, seq_n):
      if seq[seq_n - (k + 1)] > seq[seq_n - k]:
        tmp = seq[seq_n - k]
        seq[seq_n - k] = seq[seq_n - (k + 1)]
        seq[seq_n - (k + 1)] = tmp
  return seq



seq = list(range(10))
random.shuffle(seq)

print (buble_sort(seq))

>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

MergeSort

次はマージソート

import random

def merge(seq):
  if len(seq) <= 1:
    return seq

  middle = len(seq) // 2
  left = merge(seq[:middle])
  right = merge(seq[middle:])
  return sort(left, right)

def sort(left, right):
  seq = []

  while True:
    if len(left) == 0:
      seq += right
      break
    elif len(right) == 0:
      seq += left
      break

    left_head = left[0]
    right_head = right[0]

    if left_head <= right_head:
      seq.append(left_head)
      left.pop(0)
    else:
      seq.append(right_head)
      right.pop(0)

  return seq

seq = list(range(10))
random.shuffle(seq)

print (merge(seq))

>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

QuickSort

最後にクイックソート

import random

def quick_sort(seq):
  if len(seq) <= 1:
    return seq

  pivot = seq[0]
  left = []
  right = []

  for i in range(1, len(seq)):
    if seq[i] <= pivot:
      left.append(seq[i])
    else:
      right.append(seq[i])

  left = quick_sort(left)
  right = quick_sort(right)

  return left + [pivot] + right


seq = list(range(10))
random.shuffle(seq)

print (quick_sort(seq))

>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

おまけ

奇跡の可能性を持つボゴソートの実装してみる

import random

def is_sorted(seq):
  for i in range(len(seq) - 1):
    if seq[i] > seq[i + 1]:
      return False
  return True

def bogosort(seq):
  count = 0
  while True:
    random.shuffle(seq)
    count += 1
    if is_sorted(seq):
      print(count)
      return seq


seq = list(range(10))
random.shuffle(seq)

print (bogosort(seq))

>> 6520947
>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

1回のシャッフルで終わる場合があるとかロマンあるな
今回は6520947回シャッフルしたけど、、、


久しぶりにいろんなソート書いたけど良い復習になった
最近Python,Scala,C++,Rustやりたいって思ってたけど全くできてなかったからPythonだけでもやれてよかった
Pythonでなんか作ってみるか〜