Сортиране с метод на мехурчето в Java
В категория Програмиране
2 кометара
За метода на мехурчето
Алгоритъмът сравнява последователно всички двойки съседни елементи ai-1 и аi, и ако ai-1>ai местата им биват разменени.
Ако масивът е вече сортиран, методът на мехурчето ще премине през масива веднъж и ще установи, че не трябва да разменя никакви елементи.
Цитат от Wikpedia
Реализация в Java
При описване на решението на задачата прескачам някой части на програмата защото са тривиални. Например не съм описал декларирането на масива arr, който ще сортираме. След завършване на цикъла, масива arr е сортиран.
public static void bubbleSort() { boolean changed = false; //показва дали има разместване на елементи do{ temp = 0; //служи за размяна на стойностите for(int i = 0; i < arr.length-1; i++){ if(arr[i] > arr[i+1]){ //размяна на стойностите temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; changed = true; // показваме че е настъпила промяна } } }while(changed); }
Споделете тази публикация
Подобни статии
2 Кометара
Коментари
Автор 
мар 19, 2011
14:42
мар 19, 201114:42
#2 koleto :
Супер добра идея. Благодаря ви!
Коментирайте
Предишна публикация
« Проверка дали две числа са взаймно прости Следваща публикация
Сортиране чрез вмъкване в Java »
« Проверка дали две числа са взаймно прости Следваща публикация
Сортиране чрез вмъкване в Java »
16:21
Предложеното решение може да се прецезира след като се анализира ситуацията.
Ако се погледне кода, се вижда, че когато имаме „изплували“ елементи (т.е. например последните 5 елемента са наредени, то ако е имало разместване отново се прави сравнения и на тях, което е безмислено при много големи редици, за които пък този метод по принцип е сравнително по-бавен отколкото „Бърозо сортиране на Хор“). Малко по-ефективно решение е с два цикъла, при който горната граница след всяко изпуване на елемент да се нами с 1-ца.
Разбира се и тук може да се подобри идеята, защото ако последните 100 елемента на редицата са наредени и последното преместване на елемент е станало преди тях (101-я елемент преди края на редицата), то може да се запомни индекса на последния преместен елемент (от който на татък всички са по местата си), така че при по-нататъчните итерации да се пропускат сравненията на всички елементи от него до края на редицата.
Пример
arr[] = { 42, 18, 6, 23, 5, 15, 38, 49, 53, 68, 79, 88, 101, 215 }
в този случай очевидно е че след 1-то въртене на цикуъла (за сравняване на съседни елементи), елемента 42 ще се нареди преди елемента 49 и от него нататък всички са сортирани. Затова идеята е да се пропускат сравненията на вече сортираните елементи, като се знае на коя позиция (индекс) се е преместил елемента от последната итерация!
Дано да не звучи много не разбираемо!