Сортировка пузырьком

Идея сортировки пузырьком заключается в последовательных проходах массива. За каждый проход выполняется обмен соседних элементов в том случае, если они стоят в неправильном порядке. Проходы выполняются до тех пор, пока обмены не прекратятся.

<span style="color: #0000ff;"><span style="color: #ff0000;">int BubbleSort(double *Array, int ArraySize)
 {
 int bIsChanged=1, i;
 double dTmp;
 while(bIsChanged)
 {
 bIsChanged=0;
 for(i=0; i&lt;ArraySize-1; i++)
 {
 if(Array[i]&gt;Array[i+1])
 {
 dTmp=Array[i];
 Array[i]=Array[i+1];
 Array[i+1]=dTmp;
 bIsChanged=1;
 }
 }
 }
 return 0;
 }</span>

</span>

Ниже приведен код, который использовать предпочтительнее, чем “наивный” предыдущий вариант.

<span style="color: #0000ff;">int BubbleSortPlus(double *Array, int ArraySize)
 {
 int bIsChanged=1, i;
 double dTmp;
 while(bIsChanged)
 {
 bIsChanged=0;
 for(i=1; i&lt;ArraySize-1; i++)
 {
 if(Array[i]&gt;Array[i+1])
 {
 dTmp=Array[i];
 Array[i]=Array[i+1];
 Array[i+1]=dTmp;
 bIsChanged=1;
 }
 if(Array[ArraySize-1-i]&lt;Array[ArraySize-1-i-1])
 {
 dTmp=Array[ArraySize-1-i];
 Array[ArraySize-1-i]=Array[ArraySize-1-i-1];
 Array[ArraySize-1-i-1]=dTmp;
 bIsChanged=1;
 
 }
 }
 }
 return 0;
 }</span>

Сложность алгоритма для худшего случая составляет О(n*n).

Оставить комментарий

Вы должны быть зарегистрированы чтобы комментировать.