ScratchData LogoScratchData
Back to MegaApuTurkUltra's profile

Quicksort [super fast list sorting]

MEMegaApuTurkUltra•Created December 30, 2014
Quicksort [super fast list sorting]
66
56
2156 views
View on Scratch

Description

If you've seen my 3D Wind Turbine you'll notice that it lags a lot. That's because it uses bubblesort to sort the triangles to render, which is pretty slow. I was too lazy to implement faster sorting. Well, now I've implemented faster sorting! This is a version of the quicksort algorithm in Scratch. It can sort both numbers and text alphabetically! Feel free to backpack my scripts but make sure to give credit! How it works: Quicksort works by first choosing a value from the list to sort, called the pivot. This can be any value, but I chose the middle value. Then it creates two pointers, one at the beginning of the list, and one at the end. It keeps incrementing the beginning pointer until it finds a value greater than the pivot, and it keeps decrementing the end pointer until it finds a value smaller than the pivot. At this point, if the beginning pointer is still smaller than the end pointer, there are 2 values that need to be swapped, because one is less than the other. So, they are swapped. Then, incrementing and decrementing the pointers and swapping continues until the pointers hit each other. Then, the list is split into 2 parts on the point where the pointers hit, and both parts are quicksorted. (A divide-and-conquer strategy, basically). Once there are no more areas to divide up, sorting is done and the list should be sorted!

Project Details

Project ID41440388
CreatedDecember 30, 2014
Last ModifiedJanuary 2, 2015
SharedDecember 31, 2014
Visibilityvisible
CommentsAllowed