Как сортират докторите

Изроди, виждам, че сте много отворени всички тука, но ме съмнява някой да може да каже каква е сложността на следния алгоритъм:

template<class T>
void drNakovSort( T masiv[], size_t size )
{
____ T t;
____ size_t i,j;
____ bool isSorted = false;

____ while( ! isSorted ) {
________ i = rand() % size;
________ j = rand() % size;

________ if( (i > j) ^ (masiv[i] > masiv[j]) ) {
____________ t = masiv[i];
____________ masiv[i] = masiv[j];
____________ masiv[j] = t;
________ }else{
____________ isSorted = true;
____________ for( i = 1; i < size; ++i ){
________________ if( masiv[i-1] > masiv[i] ){
____________________ isSorted = false;
____________________ break;
________________ }
____________ }
________ }
____ }
}

Ти, след като можеш, защо не те взеха в Google и Microsoft? Страдаш от много тежък комплекс за малоценност. Вземи мерки ...

три

Няма гаранция за приключване. Или да ти го обясня като на ,,доктор'' - можеш да изпаднеш в безкраен цикъл стига първоначалният масив да не е сортиран.

Отиди да направиш доцентатура по въпроса и после пак ела да ни покажеш колко си умен.

Точен е алгоритъмът, няма да изпадне в безкраен цикъл.

Светлин, браво за това, че създаде нещо ново, но срам че се заби да обучаваш начинаещи.

Аз не съм доктор и не съм Светлин.

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

Ето ти пример за безкрайно въртене на тоя алгоритъм:

масив от три елемента - { 3, 1, 2 }

i и j се падат само 1 и 2 (rand не дава гаранция за покриване на цялото множество).

Програмирането не е за индианци, вожде Митич.

предполагам алгоритъма е майтап, и ще е безумно бавен (поне N*exp(N)), но като сме заговорили за проблема със приключването ще спомена че това не е задължително да е проблем. например алгоритъм за измисляне на произволна точка в сфера - измисляме случайна в куб, и ако не е в сферата пробваме пак. не е финитен, но е по-бърз от финитните си конкуренти.




NE SUTOR ULTRA CREPIDAM

Такива алгоритми обикновено имат някакъв брояч и той като се прехвърли сигурно връща фиксирана точка от сферата. Ако няма озаптяващ критерий значи и той е безумен.

А алгоритъма на Наков мисля, че не е майтап - един мой човек преди време си беше купил великата книга на Наков, от него знам, че там имало някакъв алгоритъм за сортиране. Като говориме за глупави алгоритми ето един и от мене:

size_t i = 0;
size_t c = fact( n );

while( несортиран )
пермутирай(масив, пермутация_номер i++);

Тоя поне е гарантирано финитен, сложността е само О(n!).

Именно, недей се занимава с неща, които не разбираш.

Кой ти каза, че rand не гарантира покриване на цялото множество?

Да кажем, че това е код на С/С++. Защо сега не ни извадиш формулата по която работи rand, че да проверим дали ще се падат само 1 и 2?

Подсказка: Функцията rand е различна за различните компилатори.

Прав си, бавен е и то много:

#include <ctime>
#include <cstring>
#include <cstdlib>
#include <iostream>

using namespace std;

const size_t NUMBER_OF_SORTS = 10;

const size_t ARRAY_SIZE = 1000;

void initRandomArray(int array[ ], size_t size) {
for(size_t i=0; i<size; i++) {
array[ i ] = rand();
}
}

void drNakovSort(int array[ ], size_t size)
{
int t;
size_t i,j;
bool isSorted = false;

while( ! isSorted ) {
i = rand() % size;
j = rand() % size;

if( (i > j) ^ (array[ i] > array[ j]) ) {
t = array[ i];
array[ i] = array[ j];
array[ j] = t;
}else{
isSorted = true;
for( i = 1; i < size; ++i ){
if( array[ i-1] > array[ i] ){
isSorted = false;
break;
}
}
}
}
}

void bubbleSort(int array[ ], size_t size) {
int element;
bool swapped = false;

do {
swapped = false;

for(size_t i=1; i<size; i++) {
if(array[ i-1] > array[ i]) {
element = array[ i];
array[ i] = array[ i-1];
array[ i-1] = element;

swapped = true;
}
}

size--;
} while(swapped == true);
}

void selectionSort(int array[ ], size_t size) {
int j;
int element;

for (int i = 0; i < size; i++) {
j = i;
for (i = i+1; i < size; i++) {
if (array[ i] < array[ j]) {
j = i;
}
}

if ( j != i ) {
element = array[ i];
array[ i] = array[ j];
array[ j] = element;
}
}
}

int original[ ARRAY_SIZE ];
int array[ ARRAY_SIZE ];

int main() {
time_t seconds;
srand( time(NULL) );

initRandomArray(original, ARRAY_SIZE);

seconds = time( NULL );
for(size_t i=0; i<NUMBER_OF_SORTS; i++) {
memcpy(array, original, sizeof(int)*ARRAY_SIZE);
bubbleSort(array, ARRAY_SIZE);
}
cout << "Bubble Sort: " << (time(NULL)-seconds) << endl;

seconds = time( NULL );
for(size_t i=0; i<NUMBER_OF_SORTS; i++) {
memcpy(array, original, sizeof(int)*ARRAY_SIZE);
selectionSort(array, ARRAY_SIZE);
}
cout << "Selection Sort: " << (time(NULL)-seconds) << endl;

seconds = time( NULL );
for(size_t i=0; i<NUMBER_OF_SORTS; i++) {
memcpy(array, original, sizeof(int)*ARRAY_SIZE);
drNakovSort(array, ARRAY_SIZE);
}
cout << "Nakov Sort: " << (time(NULL)-seconds) << endl;

system( "PAUSE" );
return( EXIT_SUCCESS );
}

... я сега да видим кой харчи работното време на еврейския робовладелец за глупости. Камшика май не е играл от много време.

[линк]

Notice though that this modulo operation does not generate a truly uniformly distributed random number in the span (since in most cases lower numbers are slightly more likely), but it is generally a good approximation for short spans.

Ти си бил прост като Чертичко - само заяждане без обосновка. Плувай, екскрементче, няма да си губя повече времето с тебе.

Явно ни смяташ за големи балъци. Това едната възможност. Другата възможност е да си невероятен психопат, изпаднал в култ към Светлин Наков. Погледни си първия постинг! Знаеш ли колко много говори написаното между редовете? Погледни си форматирането! Мислиш ли, че мърлячите, които Светлин обучава могат да подредят така програма? Погледни си оцветяването! Мислиш ли, че същите онези мърлячи имат минимален шанс да успеят, да постигнат такова оцветяване? После си погледни зададеният въпрос, ти трябва да си пълен олигофрен щом смяташ, че сганта обучавана от Светлин някога ще проумее смисъла на асимптотичната сложност и върху какви алгоритми се пресмята тя.

Ти се оказа уникално тъпо същество. Хем ти написах подсказка, хем не се усещаш какви глупости говориш.

Барем да беше открил названието на алгоритъма заложен в rand функцията.

Ей, аман от мърлячи, които си мислят, че разбират нещо.

Раздвоение на личността ли те мъчи?

А ти, потърси малко повече в Google, преди да пускаш в действие шизофренията.

Ти си бил много сплескана путка, щом търсиш слабостта на този алгоритъм в библиотечна функция.

Я погледни какви шаблони се ширят из кода:

template<class T>

Един "хубав" оператор за сравнение (от тип по-голямо) и стой да гледай какви безкрайни цикли ще се въртят.

Добре, айде обратно при бай гугл и този път се опитай да проумееш какво означава uniformly distributed

Толкова труд само за да оцветиш кода. Надявам се кампанията на наков да се отплаща.

best = rand()
average = rand()
worst = rand()

;-))