Реализация пирамидальной сортировки

[icqprophet]

Доброго времени суток.
Javascript изучаю сравнительно недавно, поэтому не шарю, может кто подсказать:
- почему нижеследующий код виснет как только доходит до *Основного блока программы*
- мб кто поможет реализовать отрисовку пирамид на каждом 2-3 шаге сортировки?

Да и по всей видимости проблемы с выводом.

/*------Задаем длину массива------*/
var arrayLength = prompt('Введите длину массива', 10);
var arr = [];
	//alert(arr.length);
/*------*****************------*/
/*------Заполняем массив------*/
for (var i=0; i<arrayLength; i++) {
	var newElemArray = prompt('Введите '+(i+1)+' число массива', 0);
	arr.push(newElemArray);
}
alert(arr);
/*------****************------*/
/*------Функция сортировки------*/
function swap (n1, n2) {
	var temp, num1, num2;
	temp = num1;
	num1 = num2;
	num2 = temp;
}
/*------****************------*/
/*------Основное тело программы------*/
var shift = 0; 
var b = false;

for (;;) {
	b = false;
	for (var i=0; i<arrayLength; i++) {
		if (i*2+2+shift<arrayLength) {
			if ((arr[i + shift] > arr[i*2+1+shift]) || (arr[i+shift] > arr[i*2+2+shift])) {
				if (arr[i*2+1+shift] < arr[i*2+2+shift]) {
					swap(arr[i*2+1+shift],arr[i*2+2+shift]);
					b = true;
				}	else if (arr[i*2+2+shift] < arr[i+2+1+shift]) {

				}
			}
		}
	}
		if( arr[i*2 + 2 + shift] < arr[i*2 + 1 + shift] ) {
      	    swap( arr[i*2+1+shift], arr[i * 2 +2+ shift] );
                        b = true;
        }   else if( i * 2 + 1 + shift < arrayLength ) {
                if( arr[i + shift] > arr[ i * 2 + 1 + shift] ) {
                    swap( arr[i + shift], arr[i * 2 + 1 + shift] );
                    b = true;
                }
                }
        }
        if (!b) shift++; //смещение увеличивается, когда на текущем этапе сортировать больше нечего
        if (shift+2==arrayLength) return 0;  alert('Конец осртировки');     
 
alert(arr);

Почему JS? потому что интересно).. на с++ альтернативный код пашет. Как реализовать нечто подобное на JS ума не приложу.

Заранее спасибо!.

[Deff]

icqprophet,
Лениво вникать в код - объясните задачу на пальцах ?

[icqprophet]

Ну если на пальцах, то сама задача заключается в :

1. Запросить от пользователя массив (длину/числа)
2. Отсортировать массив методом "Пирамидальной сортировки" (еще называют "Турнирная сортировка"). Довольно подробное описание алгоритма есть тут. Каждый шаг сортировки отрисовать в виде пирамиды.

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

[Deff]

Можно свести к алгоритму для питона,

def heapsort(s):                               
    sl = len(s)                                    
 
    def swap(pi, ci):                              
        if s[pi] < s[ci]:                          
            s[pi], s[ci] = s[ci], s[pi]            
 
    def sift(pi, unsorted):                        
        i_gt = lambda a, b: a if s[a] > s[b] else b
        while pi*2+2 < unsorted:                   
            gtci = i_gt(pi*2+1, pi*2+2)            
            swap(pi, gtci)                         
            pi = gtci                              
    # heapify                                      
    for i in range((sl/2)-1, -1, -1):              
        sift(i, sl)                                
    # sort                                         
    for i in range(sl-1, 0, -1):                   
        swap(i, 0)                                 
        sift(0, i)

Но лень - просмотрите все методы массивос и объектов http://javascript.ru/basic/array

[monolithed]

Можно свести к алгоритму для питона,

Причем тут Python?

на с++ альтернативный код пашет

Я бы так писал:

#include <algorithm>
#include <vector>

template <typename ...T>
	void heapsort (T... range) {
		std::make_heap(range...);
		std::sort_heap(range...);
	}
;

std::vector<int> vector = {1, 4, 3, 0, 2};
heapsort(vector.begin(), vector.end()); // 0, 1, 2, 3, 4

PS: C++11

[icqprophet]

def heapsort(s):                               
    sl = len(s)                                    
 
    def swap(pi, ci):                              
        if s[pi] < s[ci]:                          
            s[pi], s[ci] = s[ci], s[pi]            
 
    def sift(pi, unsorted):                        
        i_gt = lambda a, b: a if s[a] > s[b] else b
        while pi*2+2 < unsorted:                   
            gtci = i_gt(pi*2+1, pi*2+2)            
            swap(pi, gtci)                         
            pi = gtci                              
    # heapify                                      
    for i in range((sl/2)-1, -1, -1):              
        sift(i, sl)                                
    # sort                                         
    for i in range(sl-1, 0, -1):                   
        swap(i, 0)                                 
        sift(0, i)

Как этот метод реализовать на питоне где то уже видел, но вся соль в том что бы сделать это на JS.
В любом случае спасибо!

[icqprophet]

for (;;) {

...

        }
        if (!b) shift++; //смещение увеличивается, когда на текущем этапе сортировать больше нечего
        if (shift+2==arrayLength) return 0;  alert('Конец осртировки');     
 
alert(arr);

Я знаю, был вариант с "break", но отладчик ругался на него.. сейчас ошибку уже не вспомню.
-------------------------

Как обычно весь скрипт загинался от подобной мелочи как скобка и пары других недочетов.
Скрипт заработал, не правильно, но заработал, уже результат. Буду разбираться уже в алгоритме.
Всем спасибо за помощь!

Кстати чуть не забыл, как можно реализовать отрисовку пирамиды?.. интересна сама идея.

[рони]

как-то так ...

var arr = [4,7,6,5,8,2,0,3,1,12,4,7,6,5,8,2,0,3,12,4,7,6,5,8,2,0,3,1,12,4,7,6,5,8,2,3];
function sort(b) {
    function d(a, c) {
        var d = b[a];
        b[a] = b[c];
        b[c] = d
    }
    for (var c = b.length; c--;) {
        for (;;) {
            for (var e = !0, a = 0; a < (c - 1) / 2; a++)
            b[a] < b[2 * a + 1] && (d(a, 2 * a + 1), e = !1),
            b[a] < b[2 * a + 2] && (d(a, 2 * a + 2), e = !1);
            if (e) break
        }
        b[0] > b[c] && d(0, c)
    }
    return b
};
alert(arr + "\n" +sort(arr)+"\n"+arr)

[icqprophet]

Мелочь? Ха, какое забавное мнение...
И можно подумать, что в C++ не загнулся бы.

Вы меня не правильно поняли .. я не имел ввиду, то что JS на столько плохой язык, что загнулся изза отсутствия скобки)).. я скорее написал о своей не внимательности))

[icqprophet]

var arr = [4,7,6,5,8,2,0,3,1,12,4,7,6,5,8,2,0,3,12,4,7,6,5,8,2,0,3,1,12,4,7,6,5,8,2,3];
function sort(c) {
    for (var e = c.length; e--;) {
        for (var a = c;;) {
            for (var d = !0, b = 0; b < (e - 1) / 2; b++)
            a[b] < a[2 * b + 1] && (d = a[b], a[b] = a[2 * b + 1], a[2 * b + 1] = d, d = !1),
            a[b] < a[2 * b + 2] && (d = a[b], a[b] = a[2 * b + 2], a[2 * b + 2] = d, d = !1);
            if (d) break
        }
        a = c[0];
        c[0] = c[e];
        c[e] = a
    }
    return c
};
alert(arr + "\n" +sort(arr)+"\n"+arr)

Спасибо за вариант!.. краткость сестра таланта))..
Кто подскажет как пошагово отрисовать пирамиды?..