# Επίλυση Δραστηριοτήτων του μαθήματος Προγραμματισμός Υπολογιστών
# Γ' ΕΠΑΛ
# ΤΟΜΕΑΣ ΠΛΗΡΟΦΟΡΙΚΗΣ
# worked with Python 2.7.10
# @TasosChatz

'''

ΚΕΦΑΛΑΙΟ 5ο ΚΛΑΣΣΙΚΟΙ ΑΛΓΟΡΙΘΜΟΙ

Δραστηριότητα 2 / Σελίδα 87
Να τροποποιήσετε τον αλγόριθμο της ταξινόμησης με επιλογή, ώστε να ταξινομεί
μια λίστα ακεραίων σε φθίνουσα σειρά. Υπάρχει τρόπος να το πετύχετε, χωρίς να
κάνετε καμία απολύτως αλλαγή στον κύριο αλγόριθμο που δίνεται σε αυτή την 
ενότητα; Σε τι οφείλεται αυτό;

'''

## Αρχικός αλγόριθμος ταξινόμησης με επιλογή

# Εύρεση της θέσης του μικρότερου στοιχείου μιας λίστας
# μεταξύ των θέσεων start & end
def findMinPosition(start, end, List):
    position = start
    for i in range(start, end):
        if List[i] < List[position] :
            position = i
    return position

# Αλγόριθμος ταξινόμησης selection sort
def selectionSortAscending(List):
    position = None
    n = len(List)
    for i in range(0,n):
        position = findMinPosition(i, n, List)
        List[i], List[position] = List[position], List [i]
    return List

# Η λύση στην άσκηση μπορεί να δοθεί με τους εξής τρόπους:
# 1ος Pythonic Way με μικροαλλαγή στον αρχικό κώδικα της ταξινόμησης
def selectionSortDescending(List):
    position = None
    n = len(List)
    for i in range(0,n):
        position = findMinPosition(i, n, List)
        List[i], List[position] = List[position], List [i]
    List = List.reverse()
    return List

# 2ος χωρίς αλλαγή στον αρχικό κώδικα της ταξινόμησης
def findMinMaxPosition(start, end, List, AscDesc):
    # Τροποποίηση της εύρεσης θέσης του min ώστε να βρίσκει και τη θέση του max
    # ανάλογα αν επιθυμούμε αύξουσα (Ascending=a) ή φθίνουσα (Descending=d) ταξινόμηση
    position = start
    for i in range(start, end):
        if AscDesc.lower()=='a':
            if List[i] < List[position] :
                position = i
        elif AscDesc.lower()=='d' :
            if List[i] > List[position] :
                position = i
    return position

def selectionSort2(List,AscDesc):
    # Προσθήκη ακόμας μίας παραμέτρου στη συνάρτηση 
	# AscDesc ('a' για αύξουσα, 'd' για φθίνουσα ταξινόμηση)
    position = None
    n = len(List)
    for i in range(0,n):
        position = findMinMaxPosition(i, n, List,AscDesc)
        List[i], List[position] = List[position], List [i]
    return List

#----------------------------------------------------------
# Δοκιμαστικές κλήσεις και αποτελέσματα
import random
start = 0
end = 21
alist = []

for i in range(start, end):
    alist.append(random.randint(1,100))
	
print 'Original List =', alist
print 'Min in alist is', alist[findMinPosition(start,end,alist)], 'his posistion is ', findMinPosition(start,end,alist)
blist = alist[:]

print 'List with selection sort ascending is ', selectionSortAscending(alist)
print 'Original list Min is ', blist[findMinMaxPosition(start,end, blist, 'a')], 'in position ', findMinMaxPosition(start,end, blist, 'a')
print 'Original list Max is ', blist[findMinMaxPosition(start,end, blist, 'd')], 'in position ', findMinMaxPosition(start,end, blist, 'd')
print 'Desc - Sorted list with selectionsort2 is', selectionSort2(blist,'d')
print 'Asc - Sorted list with selectionsort2 is', selectionSort2(blist,'a')
#----------------------------------------------------------