Сортировка пузырьков раз в несколько раз?

Я пытаюсь создать функцию, которая сортирует 100 случайных чисел, используя сортировку пузырьков. Я думаю, что я мог бы сделать что-то неправильно, но .. Позвольте мне показать вам мой код первой:Сортировка пузырьков раз в несколько раз?

#define MAXVALUE 100 

void sortera_nummer(int slumptal[]){ 
int i,j,temp,k=0; 


for(i=0;i<MAXVALUE;i++){ 
    for(j=MAXVALUE-1;j>i;j--){ 
     if(slumptal[j-1]>slumptal[j]){ 
      temp=slumptal[j-1]; 
      slumptal[j-1]=slumptal[j]; 
      slumptal[j]=temp; 
      k++; 
     } 
    } 
} 
printf("K = %d",k); 
}

Числа все упорядочиваются от самого низкого до самого высокого, так сортировки работ. Но я получаю K = неожиданно большое число. (Это было где-то между 2300 и 2700.)

Итак, теперь я задаюсь вопросом: каково максимальное количество раз, когда подходящий рабочий пузырь может работать со 100 элементами? Каково уравнение для его расчета?

(Это мое первое сообщение здесь, извините, если я допустил какие-либо ошибки.) Заранее спасибо.

источник

2015-11-24 Anonymous

В этом худшем случае для сортировки пузырьков нужно ввести 'n' итераций' n/2' для ввода типа 'n'. –

Я не очень хорошо разбираюсь в математике, не могли бы вы объяснить, что немного легче, пожалуйста? EDIT: Я предполагаю, что n, в данном случае = 100? –

В худшем случае, когда ваш входной массив находится в полном убывающем порядке. В этом случае последний элемент запустит n-1 итерации. В этой итерации следующий самый маленький элемент переместился бы в последнюю позицию в первом свопе предыдущего цикла. И это повторится. –

В худшем случае, если входной массив отсортирован в порядке убывания. Первый цикл исполняется 99 раз, следующий 98, следующий 97 ......, который равен «sum (n) от n = 99 до n = 1», что означает, что худшим случаем является n (n + 1)/2, в вашем случае n = 99, то есть 4950.

источник

2015-11-25 08:47:56

Сортировка пузырьков раз в несколько раз?

ответ

Смежные вопросы