Cycle Sort

Visualization and "audibilization" of "Cycle Sort" algorithm.
Sorts a random shuffle of the integers [1,100] using Cycle Sort - en.wikipedia.or...
The algorithm is an in-place transposition-based sorting algorithm, which always requires only the minimal number of writes to the array.
It achieves this by calculating the rank of each element, and swapping it into the correct position.
The animation is slowed down during the video to give you time to see how the algorithm works.
More information on the "Sound of Sorting" at panthema.net/20...

[@razerage1]

1:20 MUST... COMPARE... EVERYTHING!

[@jsceo]

XDDDDDD

[@brahamaggarwal1800]

No it actually this sorting algorithm actually doesn't compare like that, it has time complexity of O(n) and space complexity of O(1), why don't you look this up, I'm sure you won't regret studying this.

[@garlicxi]

@@brahamaggarwal1800 this comment was 4 years ago

[@chickenbobbobba]

@@brahamaggarwal1800 ik this comment is 2 year old now but its n^2 according to wikipedia

[@BendenDrijver]

From 1:25 - end: [sorting intensifies]

[@irgendwerausbayern1999]

Ben den Drijver XD

[@GeometryDashSwietymiki]

I only come for this comment

[@cnflx]

Ludicrous Speed!

[@infitium7246]

faster... gasp... faster... yes... [can't speak anymore]

[@Juurai]

What, no base drop? I really anticipated a base drop there in the end

[@mistymysticsailboat]

the end sweep was the drop

[@maurolionelmipianoyyo11]

@@mistymysticsailboat right

[@TheRaineWitch]

*bass

[@MoolsDogTwoOfficial]

The base dropped so hard, we went from hexadecimal to tenary.

[@ilex_occulta]

I never knew sorting algorithms oculd make really trippy music.

[@KevinSiebert]

Listen to bogo sort

[@isaiasolivares8254]

That was stressful near the end

[@thebottlewithoutalix2806]

1:24 self destruct activated

[@AvindraGoolcharan]

Seems super inefficient, but it sounds pretty!

[@steamcastle]

well it is not speed that is the point, of this sort, it is doing the minimum writing.

[@steamcastle]

***** that is up to you, but why wouldn't you ever want to use this?

[@sugarfrosted2005]

steamcastle Because he likes destroying hardware? Or perhaps he meant he wouldn't want to use it, but begrudgingly would in the right circumstance.

[@steamcastle]

***** I think you are missing a word or two.

[@markhesse4510]

@@steamcastle Anti-SSD-fail sort

[@csmcstrsshd]

This is what the Predator's self-destruct sequence should have looked like

[@HalcyonMeteor72]

This sort algorithm becomes heavy when the number is too large. (It took two and a half days to do it with the maximum number (2048)) * This is the number of days if you continue to work without changing the speed from 1.00 ms.

[@SomeDudeInBaltimore]

I literally just tried to implement this on en ESP32 with an SD card for sorting a flat file database of elements. After 10 or so elements it starts taking a long, long time. I'm gonna have to put SOME of the elements into memory and sort them there, this really isn't going to work for my project which requires a responsive UI on a OLED screen.

[@Baldlick]

Put an element where it belongs and swap it for the element that took its place Put that element where it belongs and swap it for the element that took its place And repeat until you find a element the lowest, go to the element that is next to it and do the same thing Like a cycle

[@smaybius]

There are no swaps. What's in blue is just the item being held in aux memory

[@Baldlick]

@@smaybius Oop- I was new to sorting algorithms at that time

[@lenselement9020]

Yeah I'm making a dubstep remix of this

[@bonedoggle]

how's that dubstep remix coming along

[@NoriMori1992]

Did you post it on SoundCloud?

[@selftaughtsurgeon]

Chill guys, it takes a while. Wait a few more years.

[@MajorMandyKitten]

I don't get why it needs to check the sorted elements.

[@anonymoususer9837]

Shemy Djent I'm guessing it's because it doesn't remember they were sorted. This algorithm minimizes writes, and remembering an item is in the right place would take a write to memory? I'm not sure.

[@nanchoparty]

1:35 Sounds like the sound of a charging laser from an old Sonic the Hedgehog game

[@theLuigiFan0007Productions]

This is one crazy algorithm. Never seen anything like it.

[@MASTERO400]

You could optimize a lot through adding an additional dynamic array which would be the 'workspace' instead of accessing the original one this whole time.

[@PeterAuto1]

That would be against the purpose of this Algorithm. This Algorithm has the minimal write Access. The Blue bar should be in the Register

[@jhanfc]

​@@PeterAuto1 ann n

[@oh_finks]

this sort is basically bubblesort, but without the efficiency

[@yusufsahinyzs]

that beat-drop-build-up tho

[@douggale5962]

What if aliens see this?

[@Xeverous]

bad things gonna happen; especially if they find bogo

[@Obstagoon862]

+Xeverous What if they're friendly?

[@Xeverous]

Derp Nerd Then I will be happy cuz I love maths

[@tylerian4648]

Xeverous They'll think that BOGO sort is a secret program for unlocking the secrets to the universe or something based on the fact we still have it despite all the other sorters we have and switch all their programs to run BOGO sort thus guaranteeing our survival of first contact.

[@want-diversecontent3887]

Doug Gale Well, if they saw this through our broadcasts or terrestrial contact, they would be advanced enough to understand arrays. They need to see any sorting algorithm which requires comparisons and isn't just a bogo or bozo sort. EVEN BUBBLE SORT WOULD KEEP US SAFE.

[@EdwardNavu]

It''s reverse selection sort but you're forbidden to rewrite the same element the second time.

[@markhesse4510]

Because a second rewrite of the same element would degrade the SSD unnecessarily.

[@joshzimmerman]

Whew. I feel like I need a cigarette after that ending.

[@drone_better7757]

No. Don't advocate drug use in a harmless video.

[@stardustreverie6880]

@@drone_better7757 so anyone talking about cigarettes in any context is advocating drug use now? I feel like I need a cigarette after reading that.

[@kyleinwis]

Never seen this before. But I wouldnt ever want to use it, I dont think.....

[@steamcastle]

why not?

[@IlersichProductions]

steamcastle It's extremely slow.

[@steamcastle]

it depends on your system. if you have a system where reading is fast but writing is slow, this sort has the lowest number of writes of any sort.

[@IlersichProductions]

steamcastle True, but that's not a very common situation. EEPROMs (what I think you're referring to) are almost never used as RAM. It would probably be faster to use radix or merge sort then write it to the EEPROM.

[@steamcastle]

Laersico well what about flash.? but really the place I see it being useful is if you need to sort objects in the real world. with a robot that is. it would be be done with the sort in the time it takes to move just one objects. for data on a "computer" a bubble sort or Cocktail sort often okay as it can be done just a couple of lines of code.

[@jonnynik7626]

HOUSTON WE HAVE A PROBLEM

[@PointyGorman]

What an amazing algorithm

[@raymontdabizach]

is this what it feels like to chew 5 gum?

[@gray6209]

this will sound strange but these help calm me down when im having a panic attack

[@Obstagoon862]

1:35 What are you doing? Everything's already sorted!

[@7GtwNYkHYs]

YOUR DOSE OF AUDIO VISUAL SUBLIMINAL PROGRAMMING IS COMPLETE, HUMAN. CARRY ON. 🤖

[@dr_banks]

The ending made me think that there was a jumpscare inbound. I nearly had a heart attack.

[@lmartinson6963]

Listening to this while sleep deprived is terrifying for some reason.

[@ItsDaKoolaidDude]

Oh dear God it's following the booklet instructions...

[@ferociousfeind8538]

Uhh, the ehole thing's already sorted? You only need to compare the non-green tiles tho?

[@raffimolero64]

NEEDS OPTIMIZATION

[@ENCHANTMEN_]

Yeah, it should keep a list of indexes that are already sorted. Although maybe it's I'm case there are elements with equivalent values? IDK

[@anthlagr.1816]

(1:25 and ahead) >Engine starting

[@kevnar]

My dogs started howling in dismay by the end of this.

[@RammusTheArmordillo]

This is DEFINITELY alien music.

[@AnonEMoose-mr8jm]

Best sounding sort

[@meh23p]

Sounds really eerie...

[@AAAAAAAAAA42]

daft punk

[@cinaedus8781]

You guys know which super Mario level this sounds like

[@judef]

you know what this reminds me of? The scrumptious taste of pomegranate.

[@Ambipie]

Is this for a tiny system that can't think so well?

[@dnaroseandthewolves]

It's when writes are expensive

[@maxispeeltspellen4892]

1:39 sounds like an alarm tho

[@chasenplayz]

sounds like metroid music

[@whiteeye2121movalik]

hypnotizing

[@markhesse4510]

"How to sort data on a SSD without destroying the storage cells"

[@Ztenam976]

1:43 DROP

[@LocalGoober10]

The end sounds like a self destruction sequence alarm.

[@Scrolte6174]

Sounds like an alarm.

[@DiptiranjanHarichandan]

How did make the sorting graphic ?? i mean using bars n sifting them ......

[@asifkamboh3188]

great example

[@builderdex]

Scotty! Get more power to the warp drive. And somebody turn off that DAMNED alarm!

[@shiningarmor2838]

You'll tear the bloody ship apart, Jim!

[@LudwigvanBeethoven2]

1:24 about to drop da base

[@Andrescarmona767]

FeelsGoodMan Clap

[@clobre_]

1:40 *firetruck noises*

[@whiteeye2121movalik]

i was sure m laptop was about to blow up towards the end

[@machineball]

me an anime fan, and i find myself watching this at 2:21 am

[@MM-ny7dv]

1:40 SELF DESTRUCT IN 3..2..1

[@joshyeins]

Please can someone explain how it works? Im not stupid, I just haven't studied maths in years and stumbled upon this.

[@tdelfino2509]

+MadHatter It works based on the idea that an item is in the right position if everything before it is smaller and everything after it is larger. (1) Start by examining the first item. (2) Count how many items to the right are smaller than the current item; this is the rank. (3) If the rank is greater than 0, take the item that number of spaces ahead and swap (the previous element is now in the correct position). (4) If the rank is 0 (no items are larger, current item is already in correct position), move to the next item. (5) Repeat from step (2) until the end of the list is reached. In this video, the blue highlight represents the swap point for the end of the iteration. As items to the right are examined (red), each one that is smaller moves the blue highlight forward. When the end is reached, the proper position for the current item is found.

[@wcodelyoko]

It sounds like an horror movie.

[@HollowDesert]

So what are these sorting algorithms for?

[@omzldn6472]

What do the different colours that aren't red or white mean?

[@PoltergeistHC4L]

Ligth blue finds the place for dark blue, wich then sitches place and "placing" it correctley = green. Becouse it swithced place the light blue must then find the new place for the new dark blue, and thus the cycle continues, I think this is a method of a mechanical spinning disc sorting.

[@wengel_eth]

Cycle Sort is the best sorting algorithm change my mind.

[@laramads5101]

Bogo sort is adorable and tries its best dammit. Slow sort and stooge sort have anxiety and paranoia, and cycle sort tries just a little too hard. best sorting algorithm family ever.

[@wengel_eth]

@@laramads5101 I think you made the other guy delete his comment haha.

[@starduststriker8792]

mother 4 final boss theme

[@princeofexcess]

I am really interested... Who watches these and why? (Is it to visualize sorting algorithms as a software engineer. Is it for mathematicians to get inspiration? I really dont understand who the main audience for this is)

[@iPiehax]

People who are learning sorting algorithms.

[@58VintageSunburst]

Its for relaxation.

[@HitLuca94]

I am actually doing a master degree in ai and i really only like to see this algorithms visualized, nothing more

[@ponocni1]

Random bored people with lots of curiosity, that just wanna know something more random.

[@lorenzorossi2000]

It's to watch how certain algorithms behave: In our school they teach us algorithms but we learn only code not visualizing much. Those videos help us visualize how they behave and it helps us to remember the code

[@judef]

this makes me hungry

[@stallion8499]

does anybody understand whats even happening?

[@aeonsoforigin]

Why did it continue after it sorted N-1 elements in place?...that means the remaining element must already be sorted.

[@Sneakydud2]

Its a teleportation device

[@alexeyborodulin1781]

alien invaders take control

[@magicschoolbus8417]

*bogosort intensifies*

[@egoisto656]

Why does this sounds like animal collective

[@izzrainy7410]

squak

[@PG-20]

Seems very inefficient

[@dustunmalone7816]

🟪🟩🟫⬛️⬜️🟥🔲🔳🟧🟥🟥🟥🟥🟥

[@FMcheeky]

これはスッキリしない

[@Ivan-qb7kc]

WTF?!

[@Froncusiek]

Oh, another useless sorting algorithm

[@ponocni1]

Read desc, Its made to minimalize how much write process it needs to sort and how fast that sort is is kinda unrelevant. This thing would be great for flash disks and ssds, since they got limited write cycles.