#coding: cp852
#######################################
# Kr¢tka implementacja quick_sort z pokazem (braku) stabilno˜ci.
# W przypadku tego algorytmu akurat zachowuje stabilno˜†.
#######################################
from random import randint


#---============================[ quick_sort ]==========================================[]
def quick_sort(T):
  '''Sortuje szybko list© T.'''
  L=len(T)							# Ustala dˆugo˜† listy.
  if L<=1:							# Je˜li nie ma wi©cej ni¾ 1 element - jest pusta lub jednoelementowa - jest uporz©dkowana.
    return T							# Zwraca j¥.

  i=randint(0,L-1)						# Losuje element wyr¢¾niony (pivot)
  A=T[i][0]							# Skraca dost©p do zasadniczej warto˜ci elementu wybranego.
  Left=[Item for Item in T if Item[0]<A]			# Wszystkie elementy mniejsze od wybranego przenosi do lewej listy.
  Equal=[Item for Item in T if Item[0]==A]			# Wszystkie elementy r¢wne wybranemu przenosi do listy Equal.
  Right=[Item for Item in T if Item[0]>A]			# Wszystkie elementy mniejsze od wybranego przenosi do lewej listy.
  return quick_sort(Left)+Equal+quick_sort(Right)		# Zwraca posortowan¥ lew¥ list© poˆ¥czon¥ z list¥ r¢wnych (nie trzeba sortowa† bo maja t© sam¥ warto˜†) i posortowan¥ lista praw¥.


#---============================[ __name__ ]==========================================[]
if __name__=="__main__":					# ½eby wykonywaˆo sie tylko, kiedy jest testowane= wywoˆane bepo˜rednio. W wywoˆaniu jako biblioteki - mija to.
  L1=[(5,0),(4,0),(6,0),(2,0),(33,0),(5,1),(22,0),(28,0),(55,0),(5,2),(37,0),(39,0),(49,0),(57,0)]
  print(f'Przed sortowaniem {L1=}')
  L2=quick_sort(L1)
  print(f'Po sortowaniu {L2=}')