Wednesday, July 8, 2015

python: Sort (2)


Abstract: quick sort

The processing of sorting and results are
247 [93, 229, 247, 849, 292, 249, 447, 823, 344, 531]
93 [93, 229, 247, 849, 292, 249, 447, 823, 344, 531]
229 [93, 229, 247, 849, 292, 249, 447, 823, 344, 531]
849 [93, 229, 247, 531, 292, 249, 447, 823, 344, 849]
531 [93, 229, 247, 344, 292, 249, 447, 531, 823, 849]
344 [93, 229, 247, 249, 292, 344, 447, 531, 823, 849]
249 [93, 229, 247, 249, 292, 344, 447, 531, 823, 849]
292 [93, 229, 247, 249, 292, 344, 447, 531, 823, 849]
447 [93, 229, 247, 249, 292, 344, 447, 531, 823, 849]
823 [93, 229, 247, 249, 292, 344, 447, 531, 823, 849]
Unsorted data:  [247, 447, 249, 849, 292, 93, 229, 823, 344, 531]
Sorted data:  [93, 229, 247, 249, 292, 344, 447, 531, 823, 849]

The script:
# -*- coding: utf-8 -*-
"""
Created on Wed Jul  8 22:40:45 2015

@author: yuan
"""

import random

#sort
class sort_methods:
   
    def __init__(self, arr):
        self.pool=arr
        self.sorted=list(arr)
        self.num=len(arr)
       
    def quick_sort(self, left, right):
        if left>right:
            return
       
        tmp=self.sorted[left]
        l=left
        r=right
        while(l!=r):
            #
            while self.sorted[r] >=tmp and l<r:
                r -= 1
            while self.sorted[l] <=tmp and l<r:
                l += 1
            if l<r:
                self.sorted[l],self.sorted[r]=self.sorted[r],self.sorted[l]
        #l==r
        self.sorted[left], self.sorted[l]=self.sorted[l], self.sorted[left]
        #
        print tmp,self.sorted
        self.quick_sort(left, l-1)
        self.quick_sort(l+1, right)
        return
       
       
    def my_sort(self, decreasing=0):
        #sort
        self.quick_sort(0,self.num-1)
        #decreasing sort
        if decreasing==1:
            self.sorted.reverse()
        #export
        print "Unsorted data: ", self.pool
        print "Sorted data: ", self.sorted
        return self.sorted
#####################
#main programm
arr=random.sample(range(1000),10)
S=sort_methods(arr)           
           
#increasing
sorted=S.my_sort(decreasing=0)

No comments:

Post a Comment