Algoryt(h)my

Page Title Shape 1
Page Title Shape 2
Page Title Shape 3

Na początku był chaos algorytm. Zastanawiałeś się jak wielką rolę odgrywają algorytmy w codziennym życiu programisty? Czy musisz być mózgiem matematycznym, żeby używać algorytmów? Kiedy i gdzie znajdują one zastosowanie? O tym w dzisiejszym wpisie. Jednocześnie jest to wpis otwierający dział “Algorytmy”, gdzie będę starał się w prosty sposób opisywać zasady działania omawianych algorytmów.

Czym jest algorytm?

Mówiąc krótko to zestaw instrukcji, które opisują sposób w jaki działa nasz kod, w celu osiągnięcia konkretnego wyniku. Algorytmy możemy zapisywać w różny sposób, niekoniecznie musi być to kod. Jednym ze sposobów opisywania algorytmów są schematy blokowe lub pseudokod.

No dobrze … ruszajmy zatem z naszym pierwszym algorytmem.

Na naszej stronie internetowej, chcemy posortować listę komentarzy na podstawie daty ich utworzenia. Komentarze powinny wyświetlać się od najnowszych do najstarszych.

Do rozwiązania tego problemu będzie potrzebowali dwóch rzeczy:
– listy komentarzy, w naszym przypadku będzie to tablica
– algorytmu, który wykona się wewnątrz funkcji sortowania

Pamiętaj, że algorytmy są niezależne od języka programowania. Dowolny algorytm możesz zaimplementować w wybranym przez siebie języku. W związku z tym, że na codzień piszę w JavaScript wszystkie przykłady przygotuję właśnie w tym języku.

Jaki algorytm?

W jaki sposób wyobrażasz sobie możliwość sortowania listy? Może dobrym pomysłem będzie przejście przez każdy komentarz i wyszukanie tego najnowszego, a następnie kolejnego po nim etc.?

Jest to jakieś rozwiązanie natomiast czy jest ono najbardziej wydajne? Metod na rozwiązanie tego zadania jest sporo, ale dziś chciałbym skupić się na omówieniu moim zdaniem najprostrzego algorytmu – sortowania bąbelkowego (eng. bubble sorting).

Sortowanie bąbelkowe

Jak działa ten algorytm? Porównuje on dwa sąsiadujące ze sobą elementy w zadanym zestawie danych. Następnie podejmuje decyzje, czy należy je zamienić miejscami.

(źródło WIKIPEDIA)

Tak wyglądałaby przykładowa implementacja w języku JavaScript (ES6).

function bubbleSorting(arrayToSort){
	const dataToSort = [...arrayToSort];
	let sortMaxIteration = dataToSort.length - 1;
	do{
		for(let i=0; i < dataToSort.length; i++){
			if(dataToSort[i] > dataToSort[i+1]){
				[dataToSort[i], dataToSort[i+1]] = [dataToSort[i+1], dataToSort[i]];
			}
		}
		sortMaxIteration--;
	}while(sortMaxIteration > 0)
	return dataToSort;
}

const exampleData = [9, 7, 1, 2, 3, 8];
const sortedData = bubbleSorting(exampleData);
console.log(sortedData);

Wydajność algorytmu

Powyższy przykład implementacji nie jest najlepszy 🙂 Mimo iż spełnia swoje zadanie, to potrzebuje na to 36 operacji. Ta wartość oczywiście wynika z ilości elementów jakie musimy posortować, czyli długości naszej tablicy. Ilość elementów w tablicy = 6, a ilość operacji potrzebnych na ich posortowanie = 36. Widzisz zależność między tymi liczbami?

Jeśli chcesz wiedzieć jaka jest wydajność algorytmu, to powinieneś szukać informacji o notacji wielkiego O. Pewnie zastanawiasz się o co chodzi. Dzięki notacji wielkiego O jesteśmy w stanie dowiedzieć się ile operacji potrzebuje algorytm na wykonanie danego zadania. W tym wypadku notacja wielkiego O wyglądałaby następująco O(n^2). Dlaczego tak? Ponieważ dla 6 elementów powyższa implementacja potrzebuje 36 operacji, a 6*6 = 36. Notacja wielkiego O nie opisuje konkretnych przypadków, dlatego 6 zastąpiono literą n.

PAMIĘTAJ! Notacja dużego O opisuje ile operacji musi wykonać algorytm w najgorszym wypadku.
Jeśli powyższy algorytm otrzymałby na wejściu tablicę posortowaną odpowiednio, to jego wydajność moglibyśmy opisać jako O(1), ponieważ algorytm wykonałby tylko jedną operację.

Jak zatem możemy zwiększyć wydajność tego algorytmu? Przerywając dalsze porównania w momencie, gdy wiemy, że druga liczba jest już w odpowiednim miejscu. Oto poprawiona implementacja:

function bubbleSorting(arrayToSort){
  const dataToSort = [...arrayToSort];
  let wasSwapped = false;
  let loopRange = 0;
  for(let i = 0; i < dataToSort.length; i++){
    wasSwapped = false;
    loopRange = dataToSort.length - i - 1;
    for(let j=0; j < loopRange; j++){
      if(dataToSort[j] > dataToSort[j+1]){
        [dataToSort[j], dataToSort[j+1]] = [dataToSort[j+1], dataToSort[j]];
        wasSwapped = true;
      }
    }
    if(!wasSwapped){
      break;
    }
  }
  return dataToSort;
}

const exampleData = [9, 7, 1, 2, 3, 8];

const sortedData = bubbleSorting(exampleData);
console.log(sortedData);

To tyle na dziś. Daj znać w komentarzu jak podoba Ci się ten wpis oraz czy sposób wyjaśnienia jest dla Ciebie przyjazny 🙂

Newer Post

Brak produktów w koszyku.

X