Selecting Sort and Quick Sort


1

Необходимо ли е в алгоритъма на selecting sort да се пази променлива на индекса. Навсякъде по този начин се пише.

Не може ли просто да се разменят стойностите във втория for цикъл като това: http://pastebin.com/TQeU7xae

Добавям и още един мой код на QuickSort. Понеже съм начинаещ се опитвам сам да си съставя алгоритъм с goto рекурсия. Но идва момента, в който не мога да изляза от цикъла и да върна резултата. До едно положение работи алгоритъма: http://pastebin.com/BTGiSiXm

Ще съм благодарен да получа някакви идеи.




Отговори



0

 Колега, линка ти не работи но мисля, че разбрах каква питаш.

  Идеята е, на всяко завъртане на външния цикъл да се намери най-малкия елемент ов всички останали. За това се използва променлива за индекса. Например вътрешния цикъл върти и намира за най-малък елемент 4. Не е добре обаче да правим размяна, защото преди края на вътрешния цикъл можед да се окаже, че има още по-малък елемент - например 3.


от ivan.mihov1 (4988 точки)


0

вътрешния цикъл обхожда n*n пъти масива. няма как да пропусне число. изпробвал съм го. Това е кода:

for (int i = 0; i < array.Length-1; i++)
          {
            for (int j = i+1; j < array.Length; j++)
            {
                if (array[j]<array[i])
                {
                    int variableNum = array[j];
                    array[j] = array[i];
                    array[i] = variableNum;
                }
             }




0

това е bubble sort - ако не греша

работи лошо нема - ама бая повече цикли от selection sort-a

та затова за selection sort ти трябва индекса.. май :)


от kiko81 (1655 точки)


1

Може, но така всеки път, когато намериш по-малко число, ще правиш размяна, т.е. ще извършиш повече операции.

Ако трябва да сортираш 3, 2, 1 първо i ще ти сочи 3 (имам предвид стойността 3 на нулевата позиция), а j - 2(на първа позиция). Разменяш ги - 2, 3, 1. После j ти сочи 1(на втора позиция). Разменяш 2 с 1 - 1, 3, 2.

После i ти сочи 3(на първа позиция), j - 2(на втора). Разменяш ги - 1, 2, 3 и си готов.

Какво се получава ако пазиш индекса на най-малкото намерено число?

Започваме пак от 3, 2, 1. i сочи 3, j - 2. следователно currentMinIndex = 1. После j сочи 1, следователно currentMinIndex = 2. Вътрешния for приключва и разменяш 3 с 1. Получаваш 1, 2, 3. Готов си, но все пак циклите си доизвъртат, няма как. Обаче повече операции за размяна от това не правиш.




0
благодаря за примера.  вече ми е ясно защо трябва индекс. 


0
За нищо. Радвам се, че помогнах :)