# -*- coding: utf-8 -*-
"""
Лабораторна робота №3 з курсу "Теорія алгоритмів"
Спеціальність: Інформаційні управляючі системи та технології

МЕТА: 
    Дослідити метод швидкого сортування.
    
ОПИС РОБОТИ:
    В даній роботі досліджується алгоритм сортування методом швидкого
    сортування (quick sort). Відомо, що в найгіршому випадку цей алгоритм
    має асимптотичну складність O(n^2), проте математичне сподівання часу
    роботи алгоритму (тобто, в середньому) становить O(n*lg(n)).
    
    Втім у даного методу існує один недолік. Він полягає в тому, що метод
    швидкого сортування критично залежить від опорного елементу в процедурі
    розбиття (partition). Щоб обійти цю залежність пропонується опорний 
    елемент обирати випадково, таким чином отримуючи рандомізований 
    (випадковий) алгоритм швидкого сортування (randomized quick search).
    В роботі пропонується визначити, як впливає введення рандомізації на 
    швидкість алгоритму.
    
ЗАВДАННЯ:
    1) Реалізувати алгоритм сортування методом швидкого сортування. Для цього 
    написати функції quick_sort та partition на основі наведеного псевдокоду
    (див. коментарі до функцій).
    
    2) Реалізувати рандомізовану версію алгоритму у вигляді функцій 
    randomized_quicksort та randomized_partition  (див. коментарі до функцій).
    
    3) Порівняти роботи алгоритмів швидкого сортування та рандомізованого
    швидкого сортування один з одним, а також із алгоритмом сортування методом
    злиття та гібридного алгоритму, заснованого на сортуванні злиттям та 
    включенням (див. лабораторну роботу №2 та функцію 
    compare_merge_hybrid_quick). Рекомендовані параметри проведення експериментів:
        - найбільший розмір вхідного масиву n: 5000-10000
        - крок n для різних експериментів: 100-200
        - кількість повторних викликів для фіксованого n: 50-100
    На основі отриманих результатів зробити висновки щодо найкрашого алгоритму 
    сортування.
    
    4) (На додаткові 2 бали) За допомогою методу швидкого сортування 
    розв'зати наступну задачу.
    
    Гайки та болти. Неорганізований тесляр має змішаний набір N гайок та N болтів.
    Ціль полягає в тому, щоб знайти відповідні пари гайок та болтів. Кожна 
    гайка відповідає точно одному болту і кожний болт відповідає точно одній
    гайці. З'єднуючи гайку та болт між собою, тесляр може дізнатись хто з них
    більший (проте він не може порівнювати безпосередньо дві гайки чи два болти).
    Розробіть алгоритм для цієї задачі, який використовує в середньому NlogN
    порівнянь.
    
    Підказка: цю задачу можна звести до наступної. Є два масиви A та B, які 
    містять однакову кількість елементів N. Причому відомо, що елементи в 
    масивах однакові, проте знаходяться у довільному порядку. Необхідно
    відсортувати обидва масиви, але при сортуванні можна порівнювати тільки
    такі елементи, що один з них належить масиву A, а інший - масиву B.

    Для рішення цієї задачі наповніть функції double_quick_sort та 
    double_partition
    
    
ДОКУМЕНТАЦІЯ:
    Python v2.7.3 documentation:
        - http://docs.python.org/2/
        - http://oim.asu.kpi.ua/python/docs (дзеркало, доступне з кафедральних комп'ютерів)
    Книга "Dive Into Python":
        - http://www.diveintopython.net/
        - http://oim.asu.kpi.ua/python/diveintopython/html/ (дзеркало, доступне з кафедральних комп'ютерів)

"""

import random
from plot_data import plot_data
from copy import deepcopy
import numpy as np
import time

counter = 0

def generate_data(n, gen_type="random"):
    """
    Функція генерації масивів для подальшого сортування.
    Параметри:
        n (int) - кількість елементів масиву
        gen_type (string) - тип згенерованих даних:
            "best" - відсортований масив (мінімальний час для сортування)
            "worst" - найгірший варіант для сортування
            "random" - послідовність елементів генерується випадкова 
                        (значення за замовчуванням)
                        
    Повертає:
        Масив (list) довжиною n з елементами від 1 до n
    """
    if gen_type=="best":
        a = [i+1 for i in range(n)]
        return a
    elif gen_type=="worst":
        a = [i+1 for i in reversed(range(n))]
        return a
    else:
        a = [i+1 for i in range(n)]
        random.shuffle(a)
        return a
        
def insertion_sort(seq, p, r):
    """
    Алгоритм сортування методом включення.
    Відсортовує підмасив seq[p..r-1].
    Параметри:
        seq - послідовність для сортування
        p - початковий індекс підмасиву
        r - кінцевий індекс підмасиву (границя не включається у підмасив)
    """
    global counter
    for i in range(p+1, r):
        j = i-1 
        key = seq[i]
        counter += 1
        while (seq[j] > key) and (j >= p):
            counter += 1
            seq[j+1] = seq[j]
            j -= 1
        seq[j+1] = key
        
def merge(seq, p, q, r):
    """
    Процедура злиття для методу сортування злиттям.
    Зливає (з'єднує) дві вже відсортовані частини вхідного масиву seq -
    ліва частина seq[p..q-1] та права seq[q..r-1]. По закінченню роботи 
    підмасив seq[p..r-1] містить елементи у відсортованому порядку.
    Параметри:
        seq - послідовність для сортування
        p - початковий індекс підмасиву
        q - індекс кінця першої половини масиву для злиття
        r - індекс кінця другої половини масиву для злиття
    """
    global counter
    left = seq[p:q]
    left.append(float('inf'))
    right = seq[q:r]
    right.append(float('inf'))
    left_idx, right_idx = 0, 0
    for k in range(p,r):
        counter += 1
        if left[left_idx] <= right[right_idx]:
            seq[k] = left[left_idx]
            left_idx += 1
        else:
            seq[k] = right[right_idx]
            right_idx += 1
    
def merge_sort(seq, p, r):
    """
    Алгоритм сортування злиттям.
    Відсортовує підмасив seq[p..r-1].
    Параметри:
        seq - послідовність для сортування
        p - початковий індекс підмасиву
        r - кінцевий індекс підмасиву (границя не включається у підмасив)
    """
    if r-p<=1:
        return
 
    q = (r+p) / 2
    merge_sort(seq, p, q)
    merge_sort(seq, q, r)
    merge(seq, p, q, r)
    
def hybrid_sort(seq, p, r):
    """
    Гібридний алгоритм сортування, який об'єднує методи сортування злиттям та 
    включенням. Ідея полягає у використанні методу злиття, але при досягненні
    певного розміру задачі використовувати метод включення (для задач малої 
    розмірності). Відсортовує підмасив seq[p..r-1].
    
    Параметри:
        seq - послідовність для сортування
        p - початковий індекс підмасиву
        r - кінцевий індекс підмасиву (границя не включається у підмасив)
    """
    # граничний розмір поточного масиву після якого для сортування буде
    # викликатись метод сортування включенням
    limit = 40
    
    if r-p<=limit:
        insertion_sort(seq, p, r)
    else:
        q = (r+p)/2
        hybrid_sort(seq, p, q)
        hybrid_sort(seq, q, r)
        merge(seq, p, q, r)
        
def partition(seq, p, r):
    """
    Процедура розбиття для методу швидкого сортування.
    Розбиває вхідний масив seq[p..r-1] на дві частини відносно опорного елементу
    наступним чином: ліва частина seq[p..q-1] містить елементи (у довільному 
    порядку), які не більше опорного елементу, права частина seq[q+1..r-1] 
    містить елементи (у довільному порядку), які строго більші опорного 
    елементу (тут індекс q вказує на позицію, яку у відсортованому масиві
    буде займати опорний елемент). При чому в кінці роботи процедури в позиції
    seq[q] буде знаходитись опорний елемент, який надалі не приймає участі у 
    роботи алгоритму сортування. В якості опорного елементу обирається елемент 
    seq[r-1].
    
    Параметри:
        seq - послідовність для сортування
        p - початковий індекс підмасиву для розбиття
        r - кінцевий індекс підмасиву (границя не включається у підмасив)
    Повертає:
        q - індекс опорного елементу
        
    ЗАВДАННЯ:
        Вашим завданням є написання тіла функції, яка реалізує процедуру 
        розбиття методу швидкого сортування за наведеним нижче псевдокодом. 
        Також необхідно додати інструкцію по обрахунку кількості операцій 
        порівняння елементів: при кожному порівнянні лічильник counter 
        повинен збільшуватись на 1.
        
    ПСЕВДОКОД:
        x = A[r-1]
        i = p - 1
        for j = p to r-2
            do if A[j] <= x
                    then i = i + 1
                    Обміняти A[i] та A[j]
        Обміняти A[i+1] та A[r-1]
        return i + 1

    """
    # лічильник кількості операцій порівнянння елементів
    # збільшуйте його при кожному черговому порівнянні елементів масиву
    global counter
    x = seq[r - 1]
    i = p
    j = p
    while j < (r - 1):
        counter += 1
        if seq[j] <= x:
            (seq[j], seq[i]) = (seq[i], seq[j])
            i += 1
        j += 1
    (seq[r - 1], seq[i]) = (seq[i], seq[r - 1])
    return i

def quick_sort(seq, p, r):
    """
    Алгоритм швидкого сортування.
    Відсортовує підмасив seq[p..r-1].
    Параметри:
        seq - послідовність для сортування
        p - початковий індекс підмасиву
        r - кінцевий індекс підмасиву (границя не включається у підмасив)
        
    ЗАВДАННЯ:
        Вашим завданням є написання тіла функції, яка реалізує процедуру 
        швидкого сортування за наведеним нижче псевдокодом. 
        
    ПСЕВДОКОД:
        if p<r-1
            then q = Partition(A, p, r)
                QuickSort(A, p, q)
                QuickSort(A, q+1, r)

    """
    
    if r - p <= 1:
        return
    
    q = partition(seq, p, r)
    quick_sort(seq, p, q)
    quick_sort(seq, q + 1, r)
    
def randomized_partition(seq, p, r):
    """
    Процедура розбиття для методу швидкого сортування.
    Розбиває вхідний масив seq[p..r-1] на дві частини відносно опорного елементу
    наступним чином: ліва частина seq[p..q-1] містить елементи (у довільному 
    порядку), які не більше опорного елементу, права частина seq[q+1..r-1] 
    містить елементи (у довільному порядку), які строго більші опорного 
    елементу (тут індекс q вказує на позицію, яку у відсортованому масиві
    буде займати опорний елемент). При чому в кінці роботи процедури в позиції
    seq[q] буде знаходитись опорний елемент, який надалі не приймає участі у 
    роботи алгоритму сортування.
    На відміну від звичайної процедури розбиття швидкого сортування в якості
    опорного елементу обирає довільний елемент підмасву seq[p..r-1].
    
    Параметри:
        seq - послідовність для сортування
        p - початковий індекс підмасиву для розбиття
        r - кінцевий індекс підмасиву (границя не включається у підмасив)
    Повертає:
        q - індекс опорного елементу
        
    ЗАВДАННЯ:
        Вашим завданням є написання тіла функції, яка реалізує процедуру розбиття
        рандомізованого швидкого сортування аналогічно до процедури partition.
        Також необхідно додати інструкцію по обрахунку кількості операцій 
        порівняння елементів: при кожному порівнянні лічильник counter 
        повинен збільшуватись на 1.
        
        Примітка: в якості генератора псведовипадкових чисел можна 
        використовувати процедуру random.randint(a,b), яка повертає випадкове
        ціле число в проміжку [a, b].
    """
    # лічильник кількості операцій порівнянння елементів
    # збільшуйте його при кожному черговому порівнянні елементів масиву
    global counter
    pos = random.randint(p, r - 1)
    (seq[pos], seq[r - 1]) = (seq[r - 1], seq[pos])
    return partition(seq, p, r)
    
def randomized_quick_sort(seq, p, r):
    """
    Рандомізований (випадковий) алгоритм швидкого сортування. 
    Відсортовує підмасив seq[p..r-1].
    Працює аналогічно до методу швидкого сортування, але в якості опорного
    елементу обирається довільний елемент з поточного підмасиву.
    Параметри:
        seq - послідовність для сортування
        p - початковий індекс підмасиву
        r - кінцевий індекс підмасиву (границя не включається у підмасив)
        
    ЗАВДАННЯ:
        Вашим завданням є написання тіла функції, яка реалізує процедуру 
        рандомізованого швидкого сортування аналогічно до процедури quick_sort
    """
    
    if r - p <= 1:
        return
    
    q = randomized_partition(seq, p, r)
    randomized_quick_sort(seq, p, q)
    randomized_quick_sort(seq, q + 1, r)
    
    
def test(f, data):
    """
    Функція тестування різних алгоритмів сортування в рамках даної лабораторної
    роботи. Підраховує час виконання одного сортування для масиву фіксованої
    довжини.
    Параметри:
        f - функція сортування, яка сама на вхід приймає три параметри:
            seq - масив для сортування
            p - початковий індекс підмасиву
            r - кінцевий індекс підмасиву
        data - список масивів для сортування. Масив data містить декілька 
            тестових масивів і процедура test викликає тестовий алгоритм
            для кожного з тествих підмасивів
    Повертає:
        час роботи алгоритму f на одному екземплярі (у секундах, тип float) 
    """
    global counter
    counter = 0
    repeats = len(data)
    start = time.clock()
    for i in range(repeats):
        # тут можна вивести поточну вхідну послідовність для сортування
        #print data[i]
        f(data[i], 0, len(data[i]))
        # тут можна вивести поточну відсортовану послідовність
        #print data[i], '\n'
    end = time.clock()
    return (end-start)/repeats, counter/repeats
       
def compare_merge_hybrid_quick():
    """
    Процедура порівняння методів сортування: злиттям, гібридного, швидкого та 
    рандомізованого швидкого. Порівння алгоритмів ґрунтуєься на дослідженні 
    часу їх роботи (в сек) та кількості операцій порівнянь елементів. Для
    цього використовується функція test. 
    Тестування проводиться на задачах різної розмірності: від n_begin до n_end
    з кроком n_step (значення цих параметрів встановлюються в середині процедури)
    Для кожної розмірності генерується repeats екземплярів задачі. При чому 
    алгоритми запускаються на одних і тих самих екземплярах задачі.
    """
    
    # параметри для проведення експерименту
    repeats = 10       # кількість запусків для однієї розмірності
    n_begin = 10       # початкова розмірність задачі
    n_end   = 1000      # кінцева розмірність задачі
    n_step  = 50       # крок розмірності
    
    types = ["random"]
    data_plot = {'random': {'merge':{}, 'hybrid':{}, 'quick':{}, 'random_quick':{}}}
    data_plot_2 = {'random': {'merge':{}, 'hybrid':{}, 'quick':{}, 'random_quick':{}}}
    
    for n in range(n_begin,n_end+1,n_step):
        print "\nDATA SIZE: ", n
        
        for gen_type in types:
            data = [generate_data(n) for i in range(repeats)]
            
            t_merge, op_counter = test(merge_sort, deepcopy(data))
            print "Merge time:", t_merge, "op_count:", op_counter
            data_plot[gen_type]['merge'][n] = t_merge
            data_plot_2[gen_type]['merge'][n] = op_counter
            
            t_hybrid, op_counter = test(hybrid_sort, deepcopy(data))
            print "Hybrid time:", t_hybrid, "op_count:", op_counter
            data_plot[gen_type]['hybrid'][n] = t_hybrid
            data_plot_2[gen_type]['hybrid'][n] = op_counter
            
            t_quick, op_counter = test(quick_sort, deepcopy(data))
            print "Quick time:", t_quick, "op_count:", op_counter
            data_plot[gen_type]['quick'][n] = t_quick
            data_plot_2[gen_type]['quick'][n] = op_counter
            
            t_rquick, op_counter = test(randomized_quick_sort, deepcopy(data))
            print "Randomized quick time:", t_rquick, "op_count:", op_counter
            data_plot[gen_type]['random_quick'][n] = t_rquick
            data_plot_2[gen_type]['random_quick'][n] = op_counter
            
    # побудувати графіки швидкості роботи алгоритмів 
    # розкоментуйте наступну інструкцію для виводу графіків
    plot_data(data_plot, logarithmic=False, oneplot=True, data_2=data_plot_2,
              label_sort_type=False, label_data2_label=False,
              data_label='Time in sec', data2_label='Number of operations',
              legend_pos=2, legend2_pos=2, show_markers=False)

def generate_double_data(n):
    """
    Процедура генерації двох масивів довжиною n для завдання 4.
    Параметри:
        n - розмірність масивів
    Повертає:
        два масиви a та b довжиною n, які містять числа від 1 до n у довільному
        порядку
    """
    a = [i+1 for i in range(n)]
    random.shuffle(a)
    b = [i+1 for i in range(n)]
    random.shuffle(b)
    return a, b
    
def double_partition(seq_a, seq_b, p, r):
    """
    Процедура розбиття для подвійного сортування масивів у завданні 4.
    Параметри:
        seq_a - перший масив для сортування
        seq_b - другий масив для сортування
        p - початковий індекс для розбиття
        r - кінцевий індекс (границя не включається у підмасив)
    Повертає:
        q - індекс опорного елементу
    """
    # лічильник кількості операцій порівнянння елементів
    # збільшуйте його при кожному черговому порівнянні елементів масиву
    global counter
    counter += 1
    pos = p
    while seq_a[r - 1] != seq_b[pos]:
        pos += 1
    (seq_b[r - 1], seq_b[pos]) = (seq_b[pos], seq_b[r - 1])
    
    q = partition(seq_a, p, r)
    partition(seq_b, p, r)
    return q
    
    
    
def double_quick_sort(seq_a, seq_b, p, r):
    """
    Процедура одночасного сортування двох масивів seq_a та seq_b у завданні 4.
    Параметри:
        seq_a - перший масив для сортування
        seq_b - другий масив для сортування
        p - початковий індекс підмасиву
        r - кінцевий індекс (границя не включається у підмасив)
    """
    if r - p <= 1:
        return
    
    q = double_partition(seq_a, seq_b, p, r)
    double_quick_sort(seq_a, seq_b, p, q)
    double_quick_sort(seq_a, seq_b, q + 1, r)
    

def check_double_result(seq_a, seq_b):
    """
    Процедура перевірки двох відсортованих масивів. Використовується для 
    автоматичної перевірки завдання 4. У випадку, якщо масиви не відсортовані,
    виводить повідомлення про помилку та вказує індекс елементу в масиві,
    який є помилковим.
    Параметри:
        seq_a - перший масив
        seq_b - другий масив
    Повертає:
        True - якщо помилок не виявлено (масиви відсортовані), 
        False - якщо масиви не відсортовані коректно
    """
    for i in range(len(seq_a)-1):
        if seq_a[i]+1 != seq_a[i+1]:
            print "Error! Index:", i, "\n", seq_a
            return False
    for i in range(len(seq_b)-1):
        if seq_b[i]+1 != seq_b[i+1]:
            print "Error! Index:", i, "\n", seq_b
            return False
    return True
    
def run_task4():
    """
    Перевірка подвійного сортування двох масивів в рамках завдання 4.
    Процедура проводить серію експериментів з різними розмірностями масивів n:
    від n_begin до n_end з кроком n_step, для кожного n виконуючи repeats 
    викликів. По закінченню експериментів будується графік, який відображає 
    кількість операцій порівняння під час роботи процедури сортування, а також
    графіки k*nlogn, де k = {1, 2, 3, 4}. Останні дозволяють дати оцінку 
    швидкодії розробленого алгоритму сортування.
    """
    global counter
    # параметри для проведення експерименту
    repeats = 10       # кількість запусків для однієї розмірності
    n_begin = 10       # початкова розмірність задачі
    n_end   = 1000      # кінцева розмірність задачі
    n_step  = 10       # крок розмірності
    
    data_plot = {'random': {'quick':{}, 'nlogn':{}, '2nlogn':{}, '3nlogn':{}, '4nlogn':{}}}
    for n in range(n_begin,n_end+1,n_step):
        counter = 0
        for i in range(repeats):
            a, b = generate_double_data(n)
            double_quick_sort(a, b, 0, len(a))
            if not check_double_result(a, b):
                return
        counter = counter/repeats
        data_plot['random']['quick'][n] = counter
        data_plot['random']['nlogn'][n] = n*np.log2(n)
        data_plot['random']['2nlogn'][n] = 2*n*np.log2(n)
        data_plot['random']['3nlogn'][n] = 3*n*np.log2(n)
        data_plot['random']['4nlogn'][n] = 4*n*np.log2(n)
        print n, ":", counter
        
    plot_data(data_plot, logarithmic=False, oneplot=True, 
              label_sort_type=False, label_data2_label=False,
              data_label='Number of operations',
              legend_pos=2, show_markers=False)
    
"""
Завдання 1
Робота алгоритму швидкого сортування
"""
#a = generate_data(10, gen_type="random")
#print "Quick sort test\n", "Before:", a
#quick_sort(a, 0, len(a))
#print "After: ", a

"""
Завдання 2
Робота алгоритму рандомізованого швидкого сортування
"""
#a = generate_data(10, gen_type="random")
#print "Randomized quick sort test\n", "Before:", a
#randomized_quick_sort(a, 0, len(a))
#print "After: ", a

"""    
Завдання 3
Порівняння алгоритмів сортування
"""
#compare_merge_hybrid_quick()

"""    
Завдання 4
Подвійне сортування (сортування двох масивів одночасно)
"""
run_task4()