Блог о програмировании и программистах

Чем больше всматривашься в код, тем больше код всматривается в тебя

Быстрая сортировка(golang)

Пример варианты быстрой сортировки на golang

The Go Playground - запустить код

package main

import "fmt"

func qwik_sort(lst []int,left int,right int) []int{

    //Создаем копии пришедших переменных, с которыми будем манипулировать в дальнейшем.
    l := left
    r := right

    //Вычисляем 'центр', на который будем опираться. Берем значение ~центральной ячейки массива.
    center := lst[(left + right) / 2]

    fmt.Println(l,r,(left + right) / 2)

    //Цикл, начинающий саму сортировку
    for l <= r{

        //Ищем значения больше 'центра'
        for lst[r] > center{
            r--
        }

        //Ищем значения меньше 'центра'
        for lst[l] < center{
            l++
        }

        //После прохода циклов проверяем счетчики циклов
        if(l <= r){
            //И если условие true, то меняем ячейки друг с другом.
            lst[r],lst[l] = lst[l],lst[r]
            l++
            r--
        }
    }

    if r > left{
        qwik_sort(lst,left,r)
    }

    if l>right{
        qwik_sort(lst,l,right)
    }

    return lst
}

func main(){
    lst := []int{5,4,1,2,0,123,1234,32,12,2345,99}
    lst = qwik_sort(lst,0,len(lst)-1)
    fmt.Println(lst)
}

Сортировка перемешиванием(golang)

Пример усовершенствованной сортировки пузырьком

The Go Playground - запустить код

package main

import "fmt"

func cocktailsort(lst []int) []int{

    n := len(lst)
    left:=0
    right:=n-1
    for {

        for i := left;i<right;i++{
            if lst[i] > lst[i+1]{
                lst[i],lst[i+1] = lst[i+1],lst[i]
            }
        }

        right -= 1

        fmt.Println(lst)

        for i := right; i > left; i-- {
            if lst[i] < lst[i - 1] {
                lst[i], lst[i - 1] = lst[i - 1], lst[i]
            }
        }

        left += 1

        fmt.Println(lst)
        fmt.Println(left,right)

        if left >= right{
            break
        }
    }

    return lst
}

func main(){
    lst := []int{5,4,1,2,0,123,1234,32,12,2345,99}
    lst = cocktailsort(lst)
}

Сортировка слиянием(golang)

The Go Playground - запустить код

package main

import "fmt"

func merge(left []int,right []int) []int{
    //Merge two lists in ascending order.
    lst:=make([]int,0)
    for len(left) > 0 && len(right) > 0{
        if left[0] < right[0]{
            lst = append(lst,left[0])
            left = left[1:]
        }else{
            lst = append(lst,right[0])
            right = right[1:]
        }
    }
    if len(left) > 0{
        lst = append(lst,left...)
    }
    if  len(right) > 0{
        lst = append(lst,right...)
    }

    return lst
}

func mergesort(lst []int) []int{
    //Sort the list by merging O(n * log n).
    length:=len(lst)
    if length >= 2{
        mid := length/2
        lst = merge(mergesort(lst[:mid]),mergesort(lst[mid:]))
    }
    return lst
}

func main(){

    lst := []int{2,123,443,223,3,5,6,432,1}
    lst = mergesort(lst)
    fmt.Println(lst)
}

Сортировка пузырьком

Оценка работы алгоритма сортировки пузырьком:


# -*- coding: UTF-8 -*-

#----------------------------------------
#сортировка пузырьком
#----------------------------------------

#инициализация
#----------------------------------------
import profile
import random
 
array = [x for x in xrange(1000)]
random.shuffle(array)
arr=[]

#----------------------------------------
#python эталон(встроенная функция[1000 - 0.001c])
profile.run('array.sort()')
#----------------------------------------

#1 вариант(неоптимизированный[1000 - 0.103c])
#----------------------------------------
# Реализация в виде функции
def bubble_sort(lst):
    for i in xrange(len(lst)-2):
        for j in xrange(len(lst) - i - 1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

#запускаем скрипт сортировки
#----------------------------------------
profile.run('arr=bubble_sort(array)')
#----------------------------------------