Алгоритъм за разбъркване на масив, Много шум за 10 реда код... Опции

[TALANTO]

Това е един алгоритъм за разбъркване на масив, който измислих една вечер и реализирах на скоро. Идеята е следната:
1 - инициализирам масива с числата от 0 до n;
2 - избирам произволен елемент на масива;
3 - слагам го на пъво място, а този който е бил на първо взима неговото.
Елементът който е с индекс 0 вече го считам за "разбъркан", затова при следващо избиране на произволен елемент него ще го прескачам.
2 - избирам произволен елемент от масива;
3 - този път той и втория елемен си разменят местата.
Цикълът се повтаря докато не стигна n-1 избиране на елемент.

Ето го и самият код:

Код

n=10
for(i=0; i<n; i+=1)
    array[i]=i

for(i=0; i<n-1; i+=1){
    rand=floor(random(n-i)+i)
    temp=array[i]
    array[i]=array[rand]
    array[rand]=temp
}

Ето и една снимка с малко разяснения:
Хоризонтално са различни масиви;
Вертикално са елементите на всеки масив.


Какво е предимството:
-При тестване на три алгоритъма за разбъркване на 1 000 и дори 10 000 елемента този се оказа най-бърз.
-Този цикъл не прави излишни избирания на елементи и излишни проверки. Като пример мога да покажа един стар алгоритъм, който измислих преди доста време:

Код

n=1000
for(i=0; i<n; i+=1)
    array[i]=0

for(i=0; i<n; i+=1){
    array[i]=floor(random(n))
    
    for(j=0; j<i; j+=1)
        if array[i]=array[j]{
            i-=1
            break
        }
}

Представете си като стигне до момента в който с random(1000) трябва да се падне точно едно число. Да не говорим за по-голям масив. Другия алгоритъм с който го сравнявах (негов автор е krisis, измислен специално за играта "Сварка"), също имаше проверки, но беше доста по-бърз от този два реда по-нагоре. Остана да го тествам с алгоритъм на RaGiNGWhiSpeR, направен за играта "Сделка или не".

Приложение:
-Ако правите игра с карти естествено те трябва да се разбъкват, но да не се повтарят. Това е перфектно решение на проблема.

Като заключение ще кажа че този алгоритъм е изцяло мой, но не изключвам възможността някой преди мен да го е измислил. Просто не съм потърсил в интернет.

Качвам и програмката за тестване:
 array_randomize.gmk ( 9.17k ) Брой сваляния: 3

[яверт]

Добре измислен алгоритъм, само това не мога да разбера:

Елементът който е с индекс 0 вече го считам за "разбъркан", за това при следващо избиране на произволен елемент него ще го прескачам.

Какво пречи на въпросния елемент да бъде разбъркан отново?

[TALANTO]

Какво пречи на въпросния елемент да бъде разбъркан отново?

Какъв смисъл има вече разбъркан елемент да се бърка отново. Точно това е уникалното на алгоритъма да разбърка масива за n-1 повторения. Или по друг начин казано:
при
rand=floor(random(n-i)+i)
първия път имам:
random(10)
след това:
random(9)
random(8)
...
random(2)

Разбираш ли - след всяко изпълнение възможните елементи се намаляват.

Само за сравнение ще покажа какво се случи при изпълнение на по-стария ми алгоритъм отново с 10 елемента:
-Цикълът по i се изпълни 23 пъти;
-Цикълът по j 77 пъти. Като се има предвид, че някога минава 250.
Това е така защото там е възможно неколкократно падане на едно и също число.