Sortowanie przez selekcje. Implementacja

Dla specjalistów Programowanie
#1

Chodzi mi o wersję tego algorytmu z dwiema tablicami.

I mam problem.

Staram się go napisać nie patrząc na przykłady innych kodów, wszystko ok z jednym wyjątkiem.

2 tablice, zmienna i , zmienna j i zmienna min.

Pętla for (używa i) leci tyle razy ile jest elementow w tablicy.

W każdym przebiegu pętla szuka (dzięki j) minimalnej wartości, (na początku tab[0] jest min, potem jeśli któryś element jest mniejszy to on jest min, przy czym musi być jeszcze spełniony warunek że min nie może być mniejszy bądź równy sort_tab[i)

Na koniec, sort_tab = min.

No i niestety jest to niedoskonały algorytm dla tablicy w której jest kilka razy taka sama wartość…

#2

Jeśli dobrze sądzę w czym problem, użyj <= zamiast < (lub >= zamiast >, zależnie od tego w którą stronę sortujesz).

#3

Ale wtedy cały czas będzie to ten sam element…

#4

O jeden mniej niż elementów w tablice

na początku tab jest minimum a pętle po j zaczynasz od i+1

Jeżeli tak zrobisz to zgubisz i-tą wartość tablicy, masz wymienić z minimalnym elementem.

double tb[]={9,8,7,6,5,4,3,2,1};const unsigned cnt=sizeof(tb)/sizeof(*tb);
#5 
Na koniec, sort_tab[i] = min.

Chodziło mi że tej pierwszej pętli, nie w pętli z j.

Zaraz sobie przeanalizuje Twoj kod. Dzięki.

#6

Bez różnicy w którym miejscu to chciałeś wstawić, jeżeli znalazłeś minimum z jakiegoś zakresu to wpisując go (ten minimum) w konkretną komórkę tablicy gubisz zawartość tej konkretnej komórki.

#7

sort_tab to całkiem inna tablica - do której chciałem zapisywać już posortowane dane

Ty podałeś przykład http://www.home.umk.pl/~abak/wdimat/s/SelectSort.html czegoś takiego.

Ja chciałem to trochę inaczej , no nic, pokombinuję jeszcze.

#8

Musiałbyś zaznaczać które wartości z tablicy tb[] już weszli do posortowanej tablicy.

To oznacza że potrzebujesz, jedno z:

  • [*:3nt415ol]Trzecią tablice typu bool[*:3nt415ol]Najpierw znaleźć maksimum i zamieniać “zużytą” wartość[*:3nt415ol]Podmieniać “zużyte” wartości na np +INF (wynik dzielenia przez 0)

Każde z tych rozwiązań prowadzi do tego że algorytm przestanie być algorytmem sortowania przez selekcje.

#9

Myślałem nad takim rozwiązaniem i pomijając to że “prawdziwe sortowanie przez selekcję” nie jest bardzo wydajne, to to byłoby jeszcze mniej wydajne…

W starej książce znalazłem taki opis algorytmu.

#10

Czyli wciaż chcesz zrobić coś gorszego od sortowania przez selekcję: nie tylko sortować w n^2 ale i zjadać 2x więcej pamięci niż selection sort?

#11

No chciałem to po prostu zaimlementować (;

#12

Zaimplementować co?

Algorytm sortowania przez selekcje zakłada że usuwamy znaleziony element minimalny z tablicy pozostałych do sortowania.

Można to zrobić pracując na tej samej tablicę i wymieniając znaleziony element z elementem we właściwej pozycji.

Lub zaś chcesz posortowane wkładać do innej tablicy to tak jak napisałem wyżej.

#13

Już wiem (;

Po prostu złą nazwę podałem.