[JS] Arrays - 5 зад.


6

Условието на задачата е следното:

Sorting an array means to arrange its elements in increasing order. Write a script to sort an array. Use the "selection sort" algorithm: Find the smallest element, move it at the first position, find the smallest from the rest, move it at the second position, etc.
Hint: Use a second array

Любопитно ми е да видя как сте решили тази задачка. Аз използвам два вложени for-цикъла и в тях if-конструкция. Използвам и подсказката, като имам помощен масив. Решението е мое и не съм търсил в гугъл. Мисля си, обаче, че може да има и по-добър вариант.

Version 1.0: http://jsfiddle.net/georgi_yankov/V4L8s/
Version 1.1: http://jsfiddle.net/georgi_yankov/MuarM/

EDIT 1:
Както вече стана дума по-надолу в коментарите, аз не използвам "selection sort" алгоритъма.

EDIT 2:
Добавих и втори вариант на решението си (Version 1.1). Тук вече използвам "selection sort" алгоритъма. Между другото в първия си вариант (Version 1.0) открих бъг :).




Отговори



1
Едно масивче. Реших, че може да се мине и без две. :) Какво точно се случва, има описателен коментар.
http://jsbin.com/uyaket/10/edit

от Velidar (1099 точки)


0
Благодаря за споделеното решение, утре ще разгледам в детайли, че вече е време за лягане ;).

от georgi.s.yankov (6219 точки)

0
Браво, много добро решение. Виждам, че си използвал "selection sort" алгоритъма.
Поздрави!
EDIT 1: И друг път съм те виждал да увеличаваш брояча във for-цикъл, използвайки "i += 1". Защо просто не използваш "i++", по-кратко е и достатъчно ясно?
Гледам по-надолу в кода си го използваш: startIndex++;
EDIT 2: Доста добре подаваш като параметър резултат от една функция към друга. Аз все още нямам този навик, но е хубаво да се изгражда.

от georgi.s.yankov (6219 точки)



1

Грешно си го направил. Това не е selection sort, въпреки, че го наподобява.

Ето това е: http://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif

Накратко, резултатът трябва да е в същия масив, а не нов.


от evgenidb (606 точки)


0
Прав си, колега, тук не съм използвал "selection sort". Този път целта ми беше да подкарам задачата по свой начин. Както вече казах, не съм и търсил решения в гугъл.
Поздрави!

от georgi.s.yankov (6219 точки)


1
ето и моето решение (това се случва след създаването на масива "arr" и проверка на елементите му) while (move) { move = false for (i=0; i

от mvgmvg (296 точки)


0
Интересно решение ;).

от georgi.s.yankov (6219 точки)

0
Това, ако се не лъжа, си е метода на мехурчето. Разменяне местата на всеки два поредни елемента, докато нямаме подреден масив.

от Velidar (1099 точки)



1

А ето и едно конструктивно решение :

 

            function sort(){
                var data = document.getElementById("data").value;
                var arr = data.split(",");
                Array.prototype.sortNum = function () {
                    return this.sort( function (a,b) { return a-b; } );                
                }                
                alert(arr.sortNum());
            }
Тук създаваме собствена функция на масива, наречена sortNum(), посредством конструктора Array.prototype. Изобщо този похват е много мощен, тъй като така можем да задаваме custom фунционалност на всеки масив. Извинявам се, че не съм спазил инструкциите, но съм на мнение, че при писане на големи проекти, дебъгването на по-малко код е от голяма полза.



2
Предлагам ви една проста оптимизацийка на алгоритъма. Първо, ето го моето решение:
var j, k; var temp; var minIndex; for (j = 0; j < inputArray.length - 1; j++) { minIndex = j; for (k = j + 1; k < inputArray.length; k++) { if (inputArray[k] < inputArray[minIndex]) { minIndex = k; } } if (j !== minIndex) { temp = inputArray[j]; inputArray[j] = inputArray[minIndex]; inputArray[minIndex] = temp; } }
Оптимизацийката е if-a на 11-ти ред. Тоест да се извършва размяна на елемента не с всеки намерен по-малък в оставащата редица, а само с най-малкия намерен.

от bakalov85 (604 точки)


0
Не бях се замислял за If-a. Добре е да се спестява ресурс, ако елемента си е на мястото да не го бута.

от VGeorgiev (2890 точки)

0
mnogo hitro reshenie :)

от polina_n (0 точки)


0

Аз искам да попитам дали и array.sort(compareFunc) не се води за вид selection sort?

От лекцията е за arrays и си работи чудесно. Принципа е да връща отрицателно число или нула, за да остави елемента на мястото си. А ако връща  положително число разменя двата елемента.

function orderBy(a,b)  { return (a == b) ? 0 : (a>b) ? 1 : -1 }


от rossichka (444 точки)


0

Не мога да разбера нещо. Защо на 5-та задача, а също и на 7-ма, като въведа някакви стойности по-големи от трицифрени числа и те се лепват за съответното им едноцифрено. Т. е. Ако имам в масива 5, 6, 2, 4, 7, 65974, 2546465, то при подредбата ми ги изкарва по следния начин: 2, 2546465, 4, 5, 6, 65974, 7. Къде е грешката, какво пропускам?


от pe6eto (222 точки)


0
сякаш ги подрежда лексикографски, а не като числа, което за 5 зад. май е ОК. Дай част от кода да видим какво точно правиш

от pdrenovska (2196 точки)

0
Това е само първата част, която се явява и 5-та задача. Нещо ми се върти из главата, че имаше една врътка с едни парсвания, ама не се сещам къде точно... Ето го и кода: Ще се радвам ако ме сдобиеш с някоя и друга идея, за което много ти благодаря. var arr = prompt("Give me some numbers separated by ONE space").split(' '); var l = arr.length; var s = arr.slice(0); var n; var m; for (var i = 0; i < l; i++) { n = i; for (var j = i + 1; j < l; j++) { if (s[j] < s[n]) { n = j; } } m = s[n]; s[n] = s[i]; s[i] = m; } jsConsole.write("The array " + arr.join(", ") + " now is " + s.join(", "));

от pe6eto (222 точки)



0

Решение.
Демо.
Вкарвам елементите в масив, въртя два цикъла по елементите в масива. Приемам, че и-тия елемент е най-малкия и сравнявам всички с него,и така намирам най-малкия, като го разменям с първия, и така до края на масива.


от AsenVal (3487 точки)


0

И аз да добавя. За добро или лошо спазих условието с втори масив:

http://jsbin.com/osufuf/1/edit

 


от maniuni (117 точки)


0

Ето и моето решение:

http://jsbin.com/eYiBOMO/1/edit?html,console

<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <title>HW 5</title>
</head>
<body>
    <script>

        var arr = [0, 3, 7, 5, 2, 10, 6, 9, 4, 2, 6, 9, -1, -4, 4, 7, ];
        var arrTEMP = new Array(1);
        for (var i = 0; i < arr.length -1; i++) {
            for (var k = 0; k < arr.length - 1 - i; k++) {
                if (arr[k] > arr[k + 1]) {
                    arrTEMP = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = arrTEMP;
                }
            }
        }
        console.log("arr = " + arr.join(" | "));
    </script>
</body>
</html>
 


от bstaykov (528 точки)