JavaScript BubbleSort, как повысить его эффективность?

Question

Есть процедура сортировки пузырьков, подобная этой. Мне нужно сделать его более эффективным, остановив цикл, когда массив отсортирован или если массив уже отсортирован.

function sortNumbers(listbox) {
  var x, y, holder;
  // The Bubble Sort method.
  for(x = 0; x < ranarray.length; x++) {
    for(y = 0; y < (ranarray.length-1); y++) {
      if(ranarray[y] > ranarray[y+1]) {
        holder = ranarray[y+1];
        ranarray[y+1] = ranarray[y];
        ranarray[y] = holder;
      }
    }
  }

Answer 1

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

function sortNumbers(listbox) { 
  var x, y, holder; 
  // The Bubble Sort method. 
  for(x = 0; x < ranarray.length; x++) { 
    var swapOccured = false;
    for(y = 0; y < (ranarray.length-1); y++) { 
      if(ranarray[y] > ranarray[y+1]) { 
        holder = ranarray[y+1]; 
        ranarray[y+1] = ranarray[y]; 
        ranarray[y] = holder; 
        swapOccured = true;
      } 
    }
    if (!swapOccured) break; 
  } 

Answer 2

var a = [1, 203, 3, 746, 200];

function bubbleSort(a)
{
    var swapped;
    do {
        swapped = false;
        for (var i=0; i < a.length-1; i++) {
            if (a[i] > a[i+1]) {
                var temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
            }
        }
    } while (swapped);

    for(i=0;i<a.length;i++)
    {
        document.write(a[i]+"\t");
    }
}

bubbleSort(a);

Answer 3

Улучшенная сортировка по пузырькам, которая более эффективна, более быстрая, с одним циклом for.

 /*Advanced BUBBLE SORT with ONE PASS*/
/*Authored by :: Brooks Tare  AAU*/

public class Bubble {

    public int[] bubble(int b[]){ 
    int temp,temp1; 

    for(int i=0;i<b.length-1;i++){

            if(b[i]>b[i+1] ){
                ///swap(b[i],b[i+1]);

                temp=b[i];
                b[i]=b[i+1];
                b[i+1]=temp;

    /*Checking if there is any number(s) greater than 
      the current number. If there is swap them.*/
                while(i>0){

                    if(b[i]<b[i-1]){
                    ///swap(b[i]<b[i-1])

                        temp1=b[i];
                        b[i]=b[i-1];
                        b[i-1]=temp1;
                        i--;
                    }
                    else if(b[i]>b[i-1]){i--;}
                }
            }
            else{continue;}

        }



        return b;
    }
///the following is a function to display the Array 
        public void see(int []a){
            for(int j=0;j<a.length;j++){
                System.out.print(a[j]+",");
            }
        }



    public static void main(String []args){
        ///You can change the Array to your preference.. u can even make it dynamic 

        int b[]={5,1,4,2,0,3}; 
        int v[]=new int[100]; 
        Bubble br=new Bubble();
        v=br.bubble(b);
        br.see(v);

    }
}

Answer 4

Вы можете использовать XOR для сдвига битовых позиций в массиве;

var arr, len, len2;
    arr = [0, 5, 7, 8, 9, 1, 2, 3, 6, 4];

len = arr.length;

// for loops
for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - 1; j++) {
        if (arr[i] <= arr[j]) {
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[j] ^ arr[i];
            arr[i] = arr[i] ^ arr[j];
        }
    }
}

// negative while
while (--len) {
    len2 = len;
    while (len2--) {
        if (arr[len] < arr[len2]) {
            arr[len] = arr[len] ^ arr[len2];
            arr[len2] = arr[len2] ^ arr[len];
            arr[len] = arr[len] ^ arr[len2];
        }
    }
}

jsperf: http://jsperf.com/sort-tive/4

Answer 5

Проверьте, произошел ли обмен во внутреннем цикле. Если во время одного прогона нет свопа, список сортируется.

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

function sortNumbers(listbox) {
  var done = false;
  for (var x = 1; !done; x++) {
    done = true;
    for (var y = 0; y < ranarray.length - x; y++) {
      if (ranarray[y] > ranarray[y + 1]) {
        var holder = ranarray[y + 1];
        ranarray[y + 1] = ranarray[y];
        ranarray[y] = holder;
        done = false;
      }
    }
  }
}