Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Preference based sorting
#1
Given a text file as input with each line representing an element (a, b, c, d... for the sake of this example), how would you write a python script that when executed prompts the user to choose between two of the elements of the list (eg "a or b", "a or c", ..., "c or d") enough times to return an "ordered" list based on your preferences?

Additionally, could you make the program continuously listen for left/right keystrokes for example when each choice is prompted? Instead of doing some sort of "Input 0 for left choice and 1 for right choice" and having to hit enter every time.

Thanks!
Reply
#2
What have you thought about or tried? We're happy to help, but aren't here to do the work for you.
Reply
#3
Sure, forgot to add that. Here is what I've tried so far, but I think it asks for too many comparisons...

And I haven't managed to make it listen for left/right keypresses...

import sys
 
def lt(a, b):
    resp = input("{} or {}? (0 for left, 1 for right)".format(a, b))
    return resp == '0'
 
fname = sys.argv[1] # get the filename
 
with open(fname) as f:
    lines = [l.strip() for l in f.readlines()]
 
idx = 0
complete = [lines[0]]
lines = lines[1:]
 
for item in lines:
    for i, val in enumerate(complete):
        if not lt(item, val):
            # need to insert item as i+1
            if i < len(complete) - 1:
                a = complete[:i+1]
                b = complete[i+1:]
                complete = a + [item] + b
            else:
                complete.append(item)
            break
 
print(complete)
Reply
#4
The number of comparisons will vary on what sort you use, but it is going to grow quickly no matter what. You are using an insertion sort which is a good choice for minimizing the number of comparisons. The worst case scenario for the insertion sort is equal to the number of comparisons required for a bubble sort, but because you are inserting items into a sorted list, the actual number of comparisons needed is usually much less.

The worst case scenario is the items are already sorted. Assuming the list is already sorted, it takes 0 comparisons to place the first element, 1 comparison to place the second, 2 for the third, 3 for the fourth, etc... For a 5 items the maximum number of comparisons is 4+3+2+1=10. For 10 elements it is 9+8+7+6+5+4+3+2+1=45. However if the list is presorted in reverse order, each element you insert requires only one comparison. A 5 element list will need 4 comparisons and the 10 element list only 9.
def insertion_sort(x):
    y = []
    for a in x:
        for index, b in enumerate(y):
            if input(f'{a} > {b} (y/n): ') != 'y':
                y.insert(index, a)
                break;
        else:
            y.append(a)
    return y
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Sorting a copied list is also sorting the original list ? SN_YAZER 3 2,997 Apr-11-2019, 05:10 PM
Last Post: SN_YAZER
  sorting a list of tuples based on date bluefrog 2 5,727 Aug-10-2018, 02:31 AM
Last Post: ichabod801

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020