my carrot sort, kinda like merge, or bubble

I still have to test it, but I was so excited it worked, wanted to share.  So far no issues with a random list of 30,  going to shoot for bigger lists, and run the profiler on it, compare it to the other ones.  I was playing with merge and trying to figure out a way to do that without the list breakage and memory storage.

Pytest for is_sorted on a list of 800 random numbers passed.
It's slower then bubble.... but faster then quicksort on my computer.... Not sure If I accomplished anything.... But I feel pretty good about doing something I set out to do.
Bubble sort only has to go through the list max 799 times, but it goes completely through the list each time...

Still playing with it, still fixing it. Time to run significantly fixed by taking out the back end while loop. It wasn't necessary.  I have a feeling I'm just going to end up with a bubble sort.... I don't know if there is any way to make it faster without resorting to recursions and using memory to speed it up. 

Merge sort and quick sort split the lists up, sort the pieces separately in thousands of steps, but are faster per say, because the steps are done in memory. 

Can you do it?  Hold my beer.
Basically what python is doing.
It doesn't have to worry about the time it takes to do it while it's holding the beer.
Eh.  I still think it can be done. 
I'll figure it out.
This should be faster, it's not processing the whole list each step.  But it also isn't stopping if the list is done early. 
Maybe I can talk someone in class into testing it on a good computer.


This, is my carrot sort.  I didn't know what to name it.  :)



from ex19DLList import*
from random import randint



def random_list(count):
    numbers = DLList()
    for i in range(count, 0, -1):
        numbers.push(randint(0, 1000))
    return numbers



def split(numbers, place):
    print("split >>>>>>>>>>>>>>>>>>>")
    if numbers._length == 0 or numbers._length == 1:
        return numbers
    ## how do I make the lists without relying on memory??
    ## bubble sort doesn't move anything. It changes values at location
    ## what if I placed a marker in the list.....

    else:

        numbers.insert("merge_sort_mid_point_split", place)



def carrot_swap(numbers):
    front = numbers.begin
    while front.value != "merge_sort_mid_point_split":
        if front.next.value != "merge_sort_mid_point_split":
            if front.value > front.next.value:
                print("swap")
                front.value, front.next.value = front.next.value, front.value
        front = front.next

    #back = numbers.end
    #while back.value != "merge_sort_mid_point_split":
        #if back.prev.value != "merge_sort_mid_point_split":
           # if back.value < back.prev.value:
                #print("swap")
                #back.value, back.prev.value = back.prev.value, back.value
        #back = back.prev


    numbers.remove("merge_sort_mid_point_split")
    print("---merging---")
    return numbers


def carrot_sort(numbers):
    length = numbers._length
    front = False
    x = length
    while not front:

        if x < 1:
            front = True
        else:
             split(numbers, x)           
             numbers = carrot_swap(numbers)
        x -= 1


    return numbers

alist = random_list(20)
alist.graphical()
newlist = carrot_sort(alist)
newlist.graphical()

Comments

Popular posts from this blog

playing with color in powershell python

JavaScript Ascii animation with while loops and console.log

playing with trigonometry sin in pygame