sorts.py

# -*- coding: utf-8 -*-
from __future__ import unicode_literals, print_function


from PIL import Image
import numpy as np
from os.path import join
from functools import partial

import sys
sys.setrecursionlimit(sys.getrecursionlimit() * 2)


def previous(maxx, maxy, currentx, currenty):
    x = currentx - 1
    y = currenty
    if x < 0:
        x = maxx -1  # 0 index
        y -= 1

    if y < 0:
        raise StopIteration

    return x,y

def coorditer(maxx, maxxy, currentx, currenty):
    yield currentx, currenty
    x = currentx+1
    y = currenty
    while True:
        if x >= maxx:
            x = 0
            y+=1
        if y >= maxx:
            raise StopIteration
        yield x,y
        x+=1

def nextcoord(maxx, maxxy, currentx, currenty):
    x = currentx+1
    y = currenty
    if x >= maxx:
        x = 0
        y+=1
    if y >= maxx:
        raise StopIteration
    return x,y

def selectionsort(surfarray, maxx, maxy, currentx, currenty):

    def minreduce(acc, coords):
        if sum(surfarray[coords]) < (surfarray[acc]):
            return coords
        return acc

    swapcoord = (currentx, currenty)
    minbright = sum(surfarray[currentx, currenty])
    _sum = sum
    for i in coorditer(maxx, maxy, currentx, currenty):
        currbright = _sum(surfarray[i])
        if currbright < minbright:
            minbright = currbright
            swapcoord = i
            
    surfarray[currentx, currenty], surfarray[swapcoord] = surfarray[swapcoord], surfarray[currentx, currenty]
    return nextcoord(maxx, maxy, currentx, currenty)

def coordbigger(coord1,coord2):
    x1, y1 = coord1
    x2, y2 = coord2
    if y1 > y2:
        return True
    if y1 == y2 and x1 > x2:
        return True
    return False

def count(n):
    i = 0
    while i < n:
        yield i
        i+=1
    raise StopIteration

def quicksort(array):
    # print(depth)
    # print("quick called with {} elements".format(len(array)))
    if len(array) < 2:
        yield array
        raise StopIteration

    pivot = array[0].reshape((1,3))
    pivotbright = pivot.sum()
    array = np.delete(array,0,0)

    sums = array.sum(axis=1)
    
    idx = sums > pivotbright
    greater = array[idx]
    less = array[~idx]

    #print(len(greater) + len(less))
    #raise StopIteration
    yield np.concatenate((less, pivot, greater))
    for left in quicksort(less):
        yield np.concatenate((left, pivot, greater))
    for right in quicksort(greater):
        yield np.concatenate((left, pivot, right))
    raise StopIteration

def mergesort(surfarray, maxx, maxy, step):
    "This works with np array instead of pixel access because it is much much faster"
    arrlen = maxx * maxy
    surfarray = surfarray.reshape((arrlen, 3))

    while True:
        print(step)
        for i in range(0,arrlen-step, step):
            end = i+step
            idx = surfarray[i:end].sum(axis=1).argsort()
            surfarray[i:end] = surfarray[i:end][idx]
            yield surfarray.reshape((maxx, maxy,3)), step
        # do remainder
        idx = surfarray[i:].sum(axis=1).argsort()
        surfarray[i:] = surfarray[i:][idx]
        yield surfarray.reshape((maxx, maxy,3)), step
        if step >= arrlen:
            raise StopIteration
        step = step * 2
    

def bubblesort(surfarray, maxx, maxy, step):
    prevx, prevy = 0,0
    _sum = sum
    for i in coorditer(maxx, maxy, 1,0):
        if i == step:
            break
        if _sum(surfarray[i]) < _sum(surfarray[prevx, prevy]):
            surfarray[i], surfarray[prevx, prevy] = surfarray[prevx, prevy], surfarray[i]
        prevx, prevy = i
    return previous(maxx, maxy, *step)

def insertionsort(surfarray, maxx, maxy, currentx, currenty):
    # print("insertion sort called for {}x{}".format(currentx, currenty))
    x = currentx
    y = currenty
    while True:
        prevx, prevy = previous(maxx, maxy, x,y)
        if prevy < 0:
            break
        # print("compare {}x{} to {}x{}".format(x,y,prevx,prevy))
        if sum(surfarray[x,y]) < sum(surfarray[prevx, prevy]):
            temp = surfarray[x,y]
            surfarray[x, y] = surfarray[prevx, prevy]
            surfarray[prevx, prevy] = temp
            # print("later {}".format(surfarray[15:17][0]))
        else:
            break
        x,y = prevx, prevy

    currentx += 1
    if currentx == maxx:
        currentx = 0
        currenty += 1

    if currenty == maxy:
        return -1,-1

    return currentx, currenty

img = Image.open("cat.jpg")
array = np.array(img)
sizex, sizey = img.size
counter = 0
frame = 1
img.save("output/quick/{}.png".format(frame))
frame += 1
counter = 0
array = array.reshape((sizex*sizey,3))

for arr in quicksort(array):
    # print(arr)
    # break
    if counter > 100:
        img = Image.fromarray(arr.reshape((sizex, sizey, 3)))
        img.save("output/quick/{}.png".format(frame))
        frame+=1
        counter = 0
    counter+=1
img = Image.fromarray(arr.reshape((sizex, sizey, 3)))
img.save("output/quick/{}.png".format(frame))
print("finished {}".format(counter))
"""
sizex,sizey = img.size
currentx = 1
currenty = 0
import profile
profile.run("mergesort(array, sizex,sizey, 2048)")
""""""
counter = 0
frame = 1
img.save("output/merge/{}.png".format(frame))
frame += 1
try:
    step = 2
    while True:
        step = mergesort(array, sizex,sizey, step)
        img.save("output/merge/{}.png".format(frame))
        frame+=1
        #if counter > 50:
        #    img.save("output/merge/{}.png".format(frame))
        #    frame+=1
        #    counter = 0
        #counter += 1
except StopIteration:
    pass
finally:
    img.save("output/merge/{}.png".format(frame))
    print("Finished...")
    
# print("{}x{}th color ordered".format(currentx, currenty))"""