I tried to sort a random FizzBuzz column with bubble sort.
Introduction
I wanted to learn algorithms such as bubble sort, so I started by sorting a random FizzBuzz column.
Create a random FizzBuzz column of interest.
I defined a function fzbz () that changes a numerical value to FizzBuzz as appropriate, and make_random_fizzbuzz () that changes it in a random order.
def fzbz(n):
if (n%15) == 0:
return "FizzBuzz"
elif (n%5) == 0:
return "Buzz"
elif (n%3) == 0:
return "Fizz"
else:
return n
import random
def make_random_fizzbuzz(start=1,finish=100):
seq = range(start,finish+1)
random_fizzbuzz = []
while seq:
random_fizzbuzz.append(fzbz(seq.pop(random.randint(0,len(seq)-1))))
return random_fizzbuzz
More specifically, the solution to this article is to sort the list like the one below in a FizzBuzz style.
(List created by the above function)
What is bubble sort in the first place (quoted from other sites)
Bubble sort is an alignment algorithm that compares the values of the base element and other elements in a list and exchanges them according to conditions.
The condition is the magnitude relationship of the value. Sort the list in descending order (descending order) or ascending order (ascending order).
This sort is called a bubble sort because it looks like elements with higher or lower values emerge when you perform this sort.
Algorithm analysis Steps to sort the list in ascending order.
Extract one element from the list-base element'A' Compare the values of element'A'and the next element'B' Swap the values of element'A'and element'B' if element'A'is greater than element'B' Compare / exchange with each element like element'A'and element'C', element'A' and element'D' until the end of the list The element with the highest value or the element with the smallest value in the list emerges at the base point. Proceed to the base element (element'B') and repeat steps 2-6 until the end of the list Alignment is completed by performing a brute force comparison as described above and executing an exchange that matches the conditions. http://www.codereading.com/algo_and_ds/algo/bubble_sort.html
I wrote a bubble sort in python that may be slightly different from the above, but probably the same in essence.
First, a function that generates a random sequence.
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
A function that sorts the sequence created by the above function, whose significance is not well understood.
def bubble_sort(target):
limit = len(target)-1
while limit > 0:
i = 0
while i<limit:
if target[i]>target[i+1]:
target[i], target[i+1] = target[i+1], target[i]
i += 1
limit -= 1
return target
Points to be corrected
The problem with random FizzBuzz columns seems to be the magnitude relationship.
if target[i]>target[i+1]:
In other words, it seems that we should do something about this area where the size is judged.
Summary of correction
Therefore, the code that defines the counters f, b, fb for digitizing the character strings Fizz, Buzz, FizzBuzz, and
(f,b,fb) = (3,5,15)
Functions that digitize Fizz, Buzz, FizzBuzz based on counters,
def zbzf(n,f,b,fb):
n = str(n)
if n == 'FizzBuzz':
return fb
elif n == 'Buzz':
return b
elif n == "Fizz":
return f
else:
return int(n)
With functions that update the counter when Fizz, Buzz, FizzBuzz appears
def next_count(n,f,b,fb):
if n == 'FizzBuzz':
fb += 15
elif n == 'Buzz':
if (b%15) == 10:
b += 10
else:
b += 5
elif n == "Fizz":
if (f%15) == 12:
f += 6
else:
f += 3
return f, b, fb
I made, and tried to compare each element and update the counter using these.
(f,b,fb) = (3,5,15)
while i<limit:
if zbzf(target[i],f,b,fb)>zbzf(target[i+1],f,b,fb):
target[i], target[i+1] = target[i+1], target[i]
f,b,fb = next_count(target[i],f,b,fb)
code
import random
def fzbz(n):
if (n%15) == 0:
return "FizzBuzz"
elif (n%5) == 0:
return "Buzz"
elif (n%3) == 0:
return "Fizz"
else:
return n
def zbzf(n,f,b,fb):
n = str(n)
if n == 'FizzBuzz':
return fb
elif n == 'Buzz':
return b
elif n == "Fizz":
return f
else:
return int(n)
def make_random_fizzbuzz(start=1,finish=100):
seq = range(start,finish+1)
random_fizzbuzz = []
while seq:
random_fizzbuzz.append(fzbz(seq.pop(random.randint(0,len(seq)-1))))
return random_fizzbuzz
def next_count(n,f,b,fb):
if n == 'FizzBuzz':
fb += 15
elif n == 'Buzz':
if (b%15) == 10:
b += 10
else:
b += 5
elif n == "Fizz":
if (f%15) == 12:
f += 6
else:
f += 3
return f, b, fb
def fizzbuzz_sort(target):
limit = len(target)-1
while limit > 0:
i = 0
(f,b,fb) = (3,5,15)
while i<limit:
if zbzf(target[i],f,b,fb)>zbzf(target[i+1],f,b,fb):
target[i], target[i+1] = target[i+1], target[i]
f,b,fb = next_count(target[i],f,b,fb)
i += 1
limit -= 1
return target
print fizzbuzz_sort(make_random_fizzbuzz())
result
Random FizzBuzz has been sorted! !!
Recommended Posts