У JavaScript є стандартний методи сортування масиву: Array.sort():
var mas=[10, 5, 8, 9, 1, 3, 2];
mas.sort();
alert( mas );
Розглянемо інші відомі методи сортування масиву.
Сортування бульбашкою
Метод сортування бульбашкою (сортування обміном) є простим алгоритмом сортування. Метод полягає у порівняні двох сусідніх елементів, якщо один з елементів, не відповідає критерію сортування (є більшим або меншим за свого сусіда), то ці два елементи міняються місцями. Використовується два проходи по масиву.
var mas=[10, 5, 8, 9, 1, 3, 2];
for(var i=0, tmp;i<mas.length-1;i++){
for(var j=0;j<mas.length-1;j++){
if(mas[j]>mas[j+1]){
tmp=mas[j];
mas[j]=mas[j+1];
mas[j+1]=tmp;
}
}
}
alert( mas );
Додавання методу в прототип Array що дозволяє в подальшому викликати його для усіх масивів.
Array.prototype.sortBubble=function(){
for(var i=0, tmp;i<this.length-1;i++){
for(var j=0;j<this.length-1;j++){
if(this[j]>this[j+1]){
tmp=this[j];
this[j]=this[j+1];
this[j+1]=tmp;
}
}
}
return this;
}
var mas=[10, 5, 8, 9, 1, 3, 2];
alert( mas.sortBubble() );
Сортування методом вибору
Масив переглядається перший раз, знаходиться мінімальний елемент цього масиву, який міняється місцями з першим елементом. Другий раз масив переглядається, починаючи з другого елементу. Знову знаходиться мінімальний елемент, який міняється місцями з другим елементом масиву і так до повного проходження масиву.
function selectionSort(mas){
var n = mas.length;
for(var i=0;i<n-1;i++){
var min = i;
for(var j=i+1;j<n;j++){
if(mas[j]<mas[min])min=j;
}
var t=mas[min];
mas[min]=mas[i];
mas[i]=t;
}
return mas;
}
var a=[10, 5, 8, 9, 1, 3, 2];
a=selectionSort(a);
alert(a);
Швидке сортування
Спочатку з елементів масиву обрається деяке значення (середина) як опорний елемент і переставляється елемент масиву так, щоб елементи зліва від опорного були не більші нього, а елементи справа від опорного — не менші. Далі процедура швидкого сортування застосовується до кожної з одержаних частин масиву.
function QuickSort(mas, L, R){
if(L==undefined)L=0;
if(R==undefined)R=mas.length-1;
var iter = L, jter = R, middle = parseInt((R+L)/2), x = mas[middle], tmp;
do{
while(mas[iter]<x){iter++;}
while(x<mas[jter]){jter--;}
if(iter<=jter){
tmp = mas[iter];
mas[iter] = mas[jter];
mas[jter] = tmp;
iter++;
jter--;
}
}while(iter<jter);
if(L<jter) QuickSort(mas, L, jter);
if(iter<R) QuickSort(mas, iter, R);
return mas;
}
var a=[10, 5, 8, 9, 1, 3, 2];
a=QuickSort(a);
alert( a );
Пірамідне сортування
Сортування пірамідою ("сортування купою") використовує бінарне сортувальне дерево.
Спочатку вибудовуються елементи масиву у вигляді сортувального дерева. Потім переміщуються елементи з корення по одному за раз і перебудовується дерево. Процес продовжується до тих пір, поки в сортувальному дереві не залишиться один елемент - тоді масив є відсортований.
function heapSort(mas){
function swap(a, b){
var temp = mas[a];
mas[a] = mas[b];
mas[b] = temp;
}
function heapify(count){
var start = count/2-1;
while (start >= 0){
siftDown(start, count-1);
start--;
}
}
function siftDown(start, end){
var root = start;
while(root*2+1<=end){
var child = root*2+1, w=root;
if(mas[w] < mas[child]) w=child;
if(child+1 <= end && mas[w] < mas[child+1]) w=child+1;
if(w!=root){
swap(root, w);
root = w;
}else return;
}
}
if(mas.length<2) return mas;
heapify(mas.length);
var end = mas.length-1;
while(end > 0){
swap(end, 0);
siftDown(0,--end);
}
return mas;
}
var a=[25,6,8,0,45,6,7,56];
a=heapSort(a);
alert(a);
function heapSort(mas){
if(mas.length<2) return mas;
var n = mas.length, i = Math.floor(n/2), j, k, t;
while(true){
if(i>0) t=mas[--i];
else{
n--;
if(n==0) return mas;
t = mas[n];
mas[n] = mas[0];
}
j=i;
k=j*2+1;
while(k<n){
if(k+1<n && mas[k+1]>mas[k])k++;
if (mas[k]>t){
mas[j]=mas[k];
j=k;
k=j*2+1;
}else break;
}
mas[j]=t;
}
}
var a=[98,7,25,1,3,32];
a=heapSort(a);
alert( a );
Сортування методом Шелла
Сортуванням методом Шелла полягає в обмінні елементів, розташованих не тільки поряд, але і далеко один від одного, що значно скорочує загальне число операцій переміщення елементів.
function sortShell(mas){
var k=0, gap=[parseInt(mas.length/2)];
while(gap[k]>1){
k++;
gap[k]=parseInt(gap[k-1]/2);
}
for(var i=0;i<=k;i++){
step=gap[i];
for(var j=step;j<mas.length;j++){
temp=mas[j];
p=j-step;
while(p >= 0 && temp <mas[p]){
mas[p+step]=mas[p];
p=p-step;
}
mas[p+step]=temp;
}
}
return mas;
}
var a=[51,1,8,23,100,10];
a=sortShell(a);
alert(a);
function sortShell(mas){
var i=Math.floor(mas.length/2);
while(i>0){
for(var j=0;j<mas.length;j++){
var k=j, t=mas[j];
while(k>=i && mas[k-i]>t){
mas[k]=mas[k-i];
k-=i;
}
mas[k]=t;
}
i=(i==2)?1:Math.floor(i*5/11);
}
return mas;
}
var a=[12,5,89,32,1,5];
a=sortShell(a);
alert(a);
Сортування злиттям
Сортування злиттям полягає у злитті двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Сортування триватиме доти, доки довжина відсортованої ділянки не стане рівною довжині самого масиву.
function sortMerge(mas){
function Merge(a,low,mid,high){
var b = new Array(high+1-low), h, i, j = mid+1, k, h = low, i = 0;
while(h<=mid && j<=high){
if(a[h]<=a[j]){
b[i]=a[h];
h++;
}else{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid){
for(k=j; k<=high; k++){
b[i]=a[k];
i++;
}
}else{
for(k=h; k<=mid; k++){
b[i]=a[k];
i++;
}
}
for(k=0; k<=high-low; k++) a[k+low]=b[k];
return a;
}
function merge_sort(a,low,high){
if(low<high){
var mid=Math.floor((low+high)/2);
merge_sort(a, low, mid);
merge_sort(a, mid+1, high);
Merge(a, low, mid, high);
}
}
merge_sort(mas, 0, mas.length-1);
return mas;
}
var a=[25,96,10,1,5,45,0];
a=sortMerge(a);
alert(a);
function sortMerge(mas){
function merge(left, right){
var result=[];
var il=0;
var ir=0;
while(il<left.length && ir<right.length){
if(left[il]<right[ir])
result.push(left[il++]);
else result.push(right[ir++]);
}
return result.concat(left.slice(il)).concat(right.slice(ir));
}
function merge_sort(items){
if(items.length<2)return items;
var middle = Math.floor(items.length/2);
var left = items.slice(0, middle);
var right = items.slice(middle);
return merge(merge_sort(left), merge_sort(right));
}
return merge_sort(mas);
}
var a=[1,25,9,75,62,0];
a=sortMerge(a);
alert( a );