Sortowanie przez wstawianie połówkowe

Odpowiedz Nowy wątek
2016-06-08 23:19

Rejestracja: 4 lata temu

Ostatnio: 5 dni temu

0

Ktoś jest mi w stanie wytłumaczyć sortowanie połówkowe? Dlaczego akurat sortowanie połówkowe? Co to sortowanie ma związane z połówkami, co tam się dzieli na połówki?

Pozostało 580 znaków

2016-06-08 23:31
Moderator

Rejestracja: 16 lat temu

Ostatnio: 34 minuty temu

0

Nie ma takiego sortowania. Jest sortowanie przez scalanie (merge sort). Dzielisz zbiór na pół, sortujesz obie połowy (znów przez scalanie) a następnie je scalasz.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

Bialy Lew
2016-06-09 00:01
Bialy Lew
0

Chodzi ci moze o Quicksort (Sortowanie szybkie)?

Pozostało 580 znaków

2016-06-09 01:19

Rejestracja: 4 lata temu

Ostatnio: 5 dni temu

0

https://pl.wikisource.org/wiki/Sortowanie_przez_wstawianie/kod
i mamy kod zwykłej wersji sortowania przez wstawianie i wersje sortowania przez wstawianie z wyszukiwaniem połówkowym.

Pozostało 580 znaków

2016-06-09 01:46

Rejestracja: 5 lat temu

Ostatnio: 4 miesiące temu

1

Sortowanie przez wstawianie polega na dodaniu kolejnego elementu do posortowanego zbioru. Robimy to poprzez przesuwanie wszystkich elementów większych od nowego elementu w prawo:

[1 2 4 7]  <-- 3
przesuwamy 4 i 7
[1 2 _ 4 7]
wstawiamy 3 do wolnego miejsca
[1 2 3 4 7]

Wersja z wyszukiwaniem połówkowym (binarnym) wygląda jak jakaś bezużyteczna modyfikacja. Najpierw się wyszukuje miejsce, w które należy nowy element wstawić za pomocą wyszukiwania binarnego, a potem się przesuwa wszystkie elementy większe w prawo, żeby to miejsce zwolnić i się wstawia nowy element w zwolnione miejsce. Czyli na moje oko złożoność nadal taka sama, czas wykonywania się wydłuża, a program jest wiele razy dłuższy i brzydszy.
Chyba że czegoś tutaj nie widzę to niech ktoś mnie poprawi.

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0