24 Nisan 2013 Çarşamba

Sıralama Algoritmaları

Sıralama algoritmaları, sayı kümelerini küçükten büyüğeyahut büyükten küçüğe sıralamak için geliştirilmiş matematiksel yaklaşımlardır. Bu yaklaşımlardan en popüler olanlarının python dili ile implemente edilmiş halini sizlerle paylaşacağız.







Bubble Sort
numbers = []
def bubble_sort():
     "Sorts numbers in place it."
     for passesLeft in range(len(numbers)-1, 0, -1):
         for index in range(passesLeft):
             if numbers[index] > numbers[index + 1]:
                numbers[index], numbers[index + 1] = numbers[index + 1], numbers[index]   


Heap Sort
def heap_sort(lst):
  for start in range((len(lst)-2)/2, -1, -1):
    siftdown(lst, start, len(lst)-1)
 
  for end in range(len(lst)-1, 0, -1):
    lst[end], lst[0] = lst[0], lst[end]
    siftdown(lst, 0, end - 1)
 
def siftdown(lst, start, end):
  root = start
  while True:
    child = root * 2 + 1
    if child > end: break
    if child + 1 <= end and lst[child] < lst[child + 1]:
      child += 1
    if lst[root] < lst[child]:
      lst[root], lst[child] = lst[child], lst[root]
      root = child
    else:
      break

Quick Sort
def partition(list, start, end):
    pivot = list[end]                          
    bottom = start-1                          
    top = end                                 

    done = 0
    while not done:                            

        while not done:                        
            bottom = bottom+1                  

            if bottom == top:                  
                done = 1                       
                break

            if list[bottom] > pivot:          
                list[top] = list[bottom]       
                break                          

        while not done:                       
            top = top-1                        
            
            if top == bottom:                  
                done = 1                      
                break

            if list[top] < pivot:             
                list[bottom] = list[top]       
                break                          

    list[top] = pivot                         
    return top                                

def quicksort(list, start, end):
    if start < end:                           
        split = partition(list, start, end)    
        quicksort(list, start, split-1)        
        quicksort(list, split+1, end)
    else:
        return

Insertion Sort
def insertion_sort(list):
    i = 0
    j = 0
    for index in range(len(list)):
        j = index
        while (j > 0) and (list[j-1] > list[j]):
            list[j-1] , list[j] = list [j] , list[j-1]
            j -= 1

Selection Sort
def selection_sort():
    n = len(numbers)
    for i in range (0, n-1):
        minI = min(range(i,n), key = partial(getitem, numbers))
        numbers[i], numbers[minI] = numbers[minI], numbers[i] 

0 yorum :

Yorum Gönderme