Apprenez le tri rapide pour trier les colonnes FizzBuzz aléatoires

introduction

J'ai décidé d'apprendre un tri rapide pour trier une colonne FizzBuzz aléatoire.

Qu'est-ce que le tri rapide (cité sur d'autres sites)

Le tri rapide se caractérise par un très petit nombre de comparaisons et d'échanges de données et constitue le moyen le plus efficace de trier les données disjointes communes (données dispersées au hasard).

Quick Sort est un algorithme de tri considéré comme le plus rapide en pratique et utilisé dans de nombreux programmes. http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html

code

J'ai remplacé le code Java sur le site ci-dessus par python (probablement presque tel quel).

import random
def make_randoms(start=1,finish=100):
  seq = range(start,finish+1)
  randoms = []
  while seq:
    randoms.append(seq.pop(random.randint(0,len(seq)-1)))
  return randoms

def pivot(target, i, j):
  k = i + 1
  while k <= j and target[i] == target[k]: k += 1
  if k > j: return -1
  if target[i] >= target[k]: 
    return i
  else:
    return k

def partition(target, i, j, x):
  l, r = i, j
  while l <= r:
    while l <= j and target[l] < x: l += 1
    while r >= i and target[r] >= x: r -= 1
    if l > r: break
    target[l], target[r] = target[r], target[l]
    l, r = l + 1, r - 1
  return l

def quick_sort(target,i ,j):
  if i == j: return 
  p = pivot(target, i, j)
  if p != -1:
    k = partition(target, i, j, target[p])
    quick_sort(target, i, k-1)
    quick_sort(target, k, j)

Préoccupations concernant le tri des colonnes FizzBuzz

Il y a trop d'endroits pour juger de la relation de taille. Que devrais-je faire?

Recommended Posts

Apprenez le tri rapide pour trier les colonnes FizzBuzz aléatoires
Trier les colonnes FizzBuzz aléatoires avec un tri rapide
J'ai essayé de trier une colonne FizzBuzz aléatoire avec un tri à bulles.
Tri rapide sans utiliser le tri