10
mam tej tablicy:sortowania int tablica z tylko 3 elementy
int [] myarray = {17, 6, 8};
Jaki jest optymalny sposób uporządkować tę tablicę, w Pseudokod?
Dzięki!
A
Odpowiedz
17
myślę, że to powinno być dość szybki (rosnąco):
if (el1 > el2) Swap(el1,el2)
if (el2 > el3) Swap(el2,el3)
if (el1 > el2) Swap(el1,el2)
+5
Twój klasyczny rozwijany bąbelkowy rodzaj :-) +1. – paxdiablo
13
Kod ten sprawia, 2 lub 3 porównań i 4 rekordy pamięci w najgorszym przypadku, w przeciwieństwie do innej odpowiedzi (zawsze 3 porównań i 9 zapasy pamięci w najgorszym przypadku).
if a[0] < a[1]:
if a[1] > a[2]:
if a[0] < a[2]:
temp = a[1]
a[1] = a[2]
a[2] = temp
else:
temp = a[0]
a[0] = a[2]
a[2] = a[1]
a[1] = temp
else:
# do nothing
else:
if a[1] < a[2]:
if a[0] < a[2]:
temp = a[0]
a[0] = a[1]
a[1] = temp
else:
temp = a[0]
a[0] = a[1]
a[1] = a[2]
a[2] = temp
else:
temp = a[0]
a[0] = a[2]
a[2] = temp
+1
Dam ci +1 za to, adamax. Chociaż czytanie jest brzydkie, pytanie _did_ pytaj o optymalne, a twoje wydaje się to satysfakcjonować :-) – paxdiablo
+0
Twój algorytm daje niepoprawny wynik z tablicą {2, 3, 1}. – nitrocaster
+0
@nitrocaster Jestem przekonany, że to działa. – ionree
8
Nieco bardziej wydajna wersja niż rozwiniętym bubble rodzaju, nie jest optymalny, ale wciąż dość prosty
if (el1 > el2) Swap(el1, el2)
if (el2 > el3) {
Swap(el2, el3)
if (el1 > el2) Swap(el1, el2)
}
+0
Nie mogę uwierzyć, że ktoś to pominął. To było na -1. Dopiero co przegłosowałem i teraz jest to 0. –
5
maja this graphic przedstawiający drzewo decyzyjne do sortowania trzech elementów pomaga: 
+0
Z której książki to pochodzi? – johncip
+0
To jest z "Algorithmen Grundlegende" (http://www14.in.tum.de/~ga/) Volkera Heuna - niestety tylko w języku niemieckim. Bardzo podobną postać można znaleźć w "Wstępie do algorytmów" Cormena i innych (http://mitpress.mit.edu/books/introduction-algorithms). –
+1
Wiedziałem, że gdzieś to widziałem ... może też jest w książce Sedgewicka? Ale dla każdego, kto zastanawia się, czy rzeczywiście jest w CLRS, w "Sortowanie w czasie liniowym". Dzięki! – johncip
'klasyfikowane (a) 'z moją pseudo' posortowaną' funkcją, która sortuje w miejscu :) –
Wiele duplikatów, np. http://stackoverflow.com/questions/3319993/sorting-the-three-integers-programowanie –
Łatwe: 'int [] myarray = {6, 8, 17};' :) –