Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Rodzaje sortowań

No description
by

Julia Kowalska

on 3 April 2017

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Rodzaje sortowań

Sortowanie – jeden z podstawowych problemów informatyki, polegający na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.
Rodzaje sortowań
Sortowanie bąbelkowe
(ang. bubble sort) – prosta metoda sortowania o złożoności czasowej O(n^2) i pamięciowej O(1).

A algorytm ?
Algorytm – skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Sposób postępowania prowadzący do rozwiązania problem.Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwienia stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.

Sortowanie kubełkowe
(ang. bucket sort) – jeden z algorytmów sortowania, najczęściej stosowany, gdy liczby w zadanym przedziale są rozłożone jednostajnie, ma on wówczas złożoność -Θ(n)[1]. W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n²).
Rodzaje sortowań
Julia Kowalska
Co to w ogóle sortowanie?
Dla lepszego zoobrazowania
Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.
Idea działania algorytmu sortowania kubełkowego:
1.Podziel zadany przedział liczb na k podprzedziałów (kubełków) o równej długości.
2.Przypisz liczby z sortowanej tablicy do odpowiednich kubełków.
3.Sortuj liczby w niepustych kubełkach.
4.Wypisz po kolei zawartość niepustych kubełków.
Sortowanie przez wstawianie
(ang. Insert Sort, Insertion Sort) – jeden z najprostszych algorytmów sortowania, którego zasada działania odzwierciedla sposób w jaki ludzie ustawiają karty – kolejne elementy wejściowe są ustawiane na odpowiednie miejsca docelowe. Jest efektywny dla niewielkiej liczby elementów, jego złożoność wynosi O(n2).
Sortowanie przez scalanie
(ang. merge sort) – rekurencyjny algorytm sortowania danych, stosujący metodę dziel i zwyciężaj[1]. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi.
Wyróżnić można trzy podstawowe kroki:
1.Podziel zestaw danych na dwie równe części
2.Zastosuj sortowanie przez scalanie dla każdej z nich oddzielnie, chyba że pozostał już tylko jeden element;
3.Połącz posortowane podciągi w jeden ciąg posortowany.
Sortowanie przez zliczanie
(ang. counting sort) – metoda sortowania danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy.
Algorytm zakłada, że klucze elementów należą do skończonego zbioru (np. są to liczby całkowite z przedziału 0..100), co ogranicza możliwości jego zastosowania.
Dziękuje Za uwagę :)
Full transcript