Skip to content

added bogobogosort #1258

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
cclauss merged 2 commits into from
Oct 3, 2019
Merged

added bogobogosort #1258

Changes from 1 commit
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
93727c9
added bogobogosort
WilliamHYZhang Oct 2, 2019
3b36097
fix indentation error
WilliamHYZhang Oct 2, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
added bogobogosort
  • Loading branch information
@WilliamHYZhang
WilliamHYZhang committed Oct 2, 2019
commit 93727c9a016aa874b7c3961e422f0fb953bfc1c1
54 changes: 54 additions & 0 deletions sorts/bogo_bogo_sort.py
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,54 @@
"""
Python implementation of bogobogosort, a "sorting algorithm
designed not to succeed before the heat death of the universe
on any sizable list" - https://en.wikipedia.org/wiki/Bogosort.

Author: WilliamHYZhang
"""

import random


def bogo_bogo_sort(collection):
"""
returns the collection sorted in ascending order
Comment thread
WilliamHYZhang marked this conversation as resolved.
Outdated
:param collection: list of comparable items
:return: the list sorted in ascending order

Examples:
>>> bogo_bogo_sort([0, 5, 3, 2, 2])
Copy link
Copy Markdown
Member

@cclauss cclauss Oct 2, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

At least one test should have at least one:

  • negative integer
  • negative float
  • zero
  • positive integer
  • positive float

What happens when we bogo_bogo_sort(list("Hello!")) ?

Copy link
Copy Markdown
Contributor Author

@WilliamHYZhang WilliamHYZhang Oct 2, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Test #2 has negative integer, does that satisfy the requirement?
For bogo_bogo_sort(list("Hello!")) error would be caught has line 53 converts input to integer and would raise ValueError, would you like me to add a try/catch in the algorithm function as well?

Copy link
Copy Markdown
Member

@cclauss cclauss Oct 3, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Mixing pos int, pos float, zero, neg int, neg float in a single test was what I was looking for.

Python/machine_learning/dbscan/dbscan.py

Line 14 in 4617aa7

Traceback (most recent call last):
Tests for a ValueError.

[0, 2, 2, 3, 5]
>>> bogo_bogo_sort([-2, -5, -45])
[-45, -5, -2]
>>> bogo_bogo_sort([420, 69])
[69, 420]
"""

def is_sorted(collection):
if len(collection) == 1:
return True

clone = collection.copy()
while True:
random.shuffle(clone)
ordered = bogo_bogo_sort(clone[:-1])
if clone[len(clone) - 1] >= max(ordered):
break

for i in range(len(ordered)):
clone[i] = ordered[i]

for i in range(len(collection)):
if clone[i] != collection[i]:
return False
return True

while not is_sorted(collection):
random.shuffle(collection)
return collection


if __name__ == "__main__":
user_input = input("Enter numbers separated by a comma:\n").strip()
unsorted = [int(item) for item in user_input.split(",")]
print(bogo_bogo_sort(unsorted))