Learn quicksort to sort random FizzBuzz columns

Introduction

I decided to learn quicksort to sort a random FizzBuzz column.

What is quicksort (quoted from other sites)

Quicksort is characterized by a very small number of data comparisons and exchanges, and is the most efficient way to sort common disjointed data (randomly scattered data).

Quicksort is a sorting algorithm that is considered to be the fastest in practice and is used in many programs. http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html

code

I replaced the Java code on the above site with python (probably almost as it is).

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)

Concerns about sorting FizzBuzz columns

There are too many places to judge the size relationship. What should I do?

Recommended Posts

Learn quicksort to sort random FizzBuzz columns
Sort random FizzBuzz columns with quicksort
I tried to sort a random FizzBuzz column with bubble sort.
The first algorithm to learn with Python: FizzBuzz problem
Quicksort without using sort