firat's blog

quickmergesort (with in-place mergesort)

2012-02-02T11:55:00.000-05:00

The algorithm shown in the previous post doesn't use in-place mergesort. Here is the in-place version:
http://pastebin.com/cu8zphcA

quickmergesort (an example of mutual recursion)

2012-02-01T21:58:00.002-05:00

In this post, I'm showing a sorting algorithm called quickmergesort which makes use of both quicksort and mergesort in a mutually recursive way.

import random

#mutually recursive quick+merge sort
def quickmergesort(L):
 mergesort(L, 0, len(L)-1)
 
def mergesort(L, sindex, eindex):
 N = eindex - sindex + 1
 if N < 2:
  return 
 mindex = (sindex + eindex)/2 
 quicksort(L, sindex, mindex)
 quicksort(L, mindex+1, eindex)
 T = []
 i = sindex
 j = mindex+1
 while i <= mindex and j <= eindex:
  if L[i] > L[j]:
   T.append(L[j])   
   j = j + 1   
  else:
   T.append(L[i])   
   i = i + 1
 if i == mindex + 1:
  T = T + L[j:eindex+1]
 else:
  T = T + L[i:mindex+1] 
 L[sindex:eindex+1] = T 
 

def quicksort(L, sindex, eindex):
 N = eindex - sindex + 1
 if N < 2:
  return
 p1 = sindex+1
 p2 = eindex
 while p2 > p1:
  if L[p1] <= L[sindex]:
   p1 = p1 + 1
  else:
   swap(L, p1, p2)
   p2 = p2 - 1
 if L[sindex] < L[p1]:
  p1 = p1 - 1
 swap(L, sindex, p1)   
 mergesort(L, sindex, p1-1)
 mergesort(L, p1+1, eindex) 
 
def swap(L, i, j):
 t = L[i]
 L[i] = L[j]
 L[j] = t

items = range(15)
random.shuffle(items)
print items
quickmergesort(items)
print items

recursion olsun camurdan olsun

2012-01-18T00:03:00.001-05:00

asagidaki python kodunu kafadan yazdim, ama daha sonra bir benzerine rastladim: http://c2.com/cgi/wiki?SlowSort, ama garanti ediyorum benimki daha yavas...

import random

def slowsort(L):
    n = len(L)
    if n <= 1:
        return L
    r = random.randint(0,n-1) 
    L1 = slowsort(L[:r])
    L2 = slowsort(L[r:])
    if L1 == []:
       return L2
    elif L2 == []:
       return L1
    elif L1[-1] <= L2[0]:
       return L1+L2
    else:
       return slowsort(L2+L1)

items = range(20)
random.shuffle(items)
print items
S = slowsort(items)
print S

2012-01-17T20:46:00.001-05:00

hazir facebook, twitter ve google+'da boy gosteriyoruz, blog camiasina da el atalim. gerci ilk girisimim degil ama bu sefer umutluyum.