Algorytmy. Trivial: Czy jest na forum ktoś dobry z algorytmiki? Mam problemy z takim oto zadaniem: Rozważmy sortowanie n liczb z tablicy A następującą metodą. Znajdujemy najmniejszy element tablicy A i wstawiamy na pierwsze miejsce w pewnej tablicy B. Następnie znajdujemy drugi najmniejszy element z A i wstawiamy na drugie miejsce w B. W ten sposób postępujemy dla wszystkich n elementów tablicy A. Napisz dla tego algorytmu − który jest znany jako sortowanie przez selekcję − program. Podaj pesymistyczny i optymistyczny czas działania tego algorytmu, używając notacji Θ. Głównie chodzi mi o to, jak wyszukać drugi najmniejszy element w tablicy A. Wszelka pomoc mile widziana.

...: po wyszukaniu pierwszej liczby komórkę, gdzie ona się znajdowała zamieniasz na NULL i wyszukujesz kolejny raz

Trivial: Ze zmianą to wiem. A bez zmiany wartości?

b.: jesli liczby sa rozne, to mozna po prostu szukac najmniejszego elementu w A, ktory bedzie wiekszy od ostatniego elementu w B a w ogolnym przypadku trzeba troche na okolo, eleganckiego wariantu powyzszej metody nie mam. Mozna np. szukac najpierw w A elementow rownych ostatniemu elementowi w B (i je dopisywac do B). Mozna tez juz przy okazji szukania najmniejszego elementu w A, ktory bedzie wiekszy od B zliczac powtorzenia, ale to pewnie na jedno wyjdzie. W kazdym razie, czas dzialania pogarsza sie co najwyzej 2 krotnie...

Trivial: Ciekawy pomysł. A czy w ogólnym przypadku nie wystarczy dać warunku słabej nierówności?

b.: i tak bedziesz mial klopot z liczbami pojawiajacymi sie wielokrotnie (mozna oczywiscie dac slaba nierownosc i zliczac, ile bylo rownosci −− sposob 2)

Trivial: SELECTION−SORT(A)  1. utwórz tablicę B[n]  2. iMin ← 1  3. for i ← 1 to n  4.  do if A[i] ≤ A[iMin]  5. then iMin ← i  6. B[1] ← A[iMin]  7. for j ← 1 to n−1  8.    do for i ← 1 to n  9. do if A[i] ≤ A[iMin] and A[i] ≥ B[j] 10. then B[j+1] ← A[iMin] Co myślisz o takim algorytmie?

Trivial: SELECTION−SORT(A)  1. utwórz tablicę B[n]  2. iMin ← 1  3. for i ← 1 to n  4.  do if A[i] ≤ A[iMin]  5. then iMin ← i  6. B[1] ← A[iMin]  7. for j ← 1 to n−1  8.    do for i ← 1 to n  9. do if A[i] ≤ A[iMin] and A[i] ≥ B[j] 10. then iMin ← i 11. B[j+1] ← A[iMin] Sorry tak miało być.

b.: musisz uaktualniac iMin w petli. Napisz, jak to zamierzasz zrobic, wtedy sie wypowiem

b.: aha, juz patrze

Trivial: SELECTION−SORT(A)  1. utwórz tablicę B[n]  2. iMin ← 1  3. for i ← 1 to n  4.  do if A[i] ≤ A[iMin]  5. then iMin ← i  6. B[1] ← A[iMin]  7. for j ← 1 to n−1  8.    do iMin ← j+1  9. for i ← 1 to n 10. do if A[i] ≤ A[iMin] and A[i] ≥ B[j] 11. then iMin ← i 12. B[j+1] ← A[iMin] Kolejne błędy...

b.: dla A=[1,2,3] dostaniemy B=[1,1,1]

Trivial: Chyba linijka ósma jest zupełnie niepotrzebna, no i trzeba zmienić w linijce dziesiątej: A[i] > B[j]... No nie wiem. W takim razie załóżmy, że są to tablice różnowartościowe.

Trivial: w linijce 8 powinno być iMin ← 1.

Trivial: Złożoność oczywiście Θ(n²)?

b.: tak, zlozonosc rzedu n² w linijce 8 powinno być iMin ← 1, zgadza sie, no i jak zamiesz druga nierownosc w 10. na ostra, to bedzie dzialalo dla roznowartosciowych

Trivial: OK. W takim razie dziękuję za pomoc.

b.: wersje dla dowolnych mozna dostac np. dodajac takie wiersze: 6.5. lastiMin ←iMin 11.5. lastiMin ←iMin oraz modyfikujac 10: 10. do if A[i] ≤ A[iMin] and (A[i] > B[j] or (A[i]=B[j] and i>lastiMin))

b.: (ten wiersz 11.5 powinien byc na tym samym poziomie wciecia co wiersz 12.)

Trivial: w takim razie chyba trzeba zmienić na silną nierówność. 10. do if A[i] < A[iMin] and ...

Trivial: Mimo wszystko ten algorytm nie będzie zbyt wydajny.

b.: nie, tej pierwszej nierownosci nie zmieniamy, bo szukamy najmniejszego elementu w slabym sensie (moze byc kilka najmniejszych elementow), ale ograniczamy poszukiwania do elementow wiekszych od B[j], albo rownych B[j], ale o indeksie i wiekszym od ostatniego iMin

Trivial: tak samo w linijce 4.: if A[i] < A[iMin] Mam rację, czy nie ma to znaczenia?

Trivial: Ale mając tablicę A = (2, 2, 1) najpierw wyszukamy iMin = 3, czyli B = (1, .., ..) potem wyszukamy iMin = 2, czyli B = (1, 2, ..) a potem wyszukamy iMin = 2 no i mamy kłopot.

b.: nie bedzie zbyt wydajny jesli chodzi o liczbe porownan w jednym okrazeniu petli, to prawda ale to tylko kwestia stalego czynnika, gorsza sprawa jest zlozonosc rzedu n² (na co nic sie tu nie poradzi) za to jest dobry jesli chodzi o liczbe podstawien elementow tablicy (tylko n) − wiec mialby zastosowanie, gdyby elementami tablicy byly duze struktury (drogie kopiowanie), ale sortowalibysmy tylko po jednym elemencie tej struktury (tanie porownywanie)

b.: masz racje! powinna byc ostra nierownosc, tak jak pisales o 15:25

b.: (na co nic sie tu nie poradzi) −> w sensie, w tym algorytmie typu 'selection sort', bo sa inne o mniejszej asymptotycznej zlozonosci

Trivial: Jeszcze mam takie pytanie. Czy znajomość tego typu rzeczy przydaje się "w praktyce" w programowaniu?

b.: znajomosc konkretnych algorytmow sortowania nie jakos bardzo, bo w wielu nowych jezykach jest efektywna metoda sortowania dostarczana przez biblioteke i nie trzeba sie o to martwic (no chyba ze sortowanie jest naprawde kluczowe dla programu, to wtedy moze byc potrzeba napisania samemu/znalezienia bardziej odpowiedniego algorytmu do danej sytuacji; nie zawsze ten z lepsza zlozonoscia asymptotyczna bedzie lepszy w praktyce). Szczegolnie w jezykach wysokiego poziomu, typu js, python, nie warto pisac samemu czegos, co jest dostarczane standardowo. Ale mysle, ze napisanie sobie samemu takiej funkcji raz w zyciu jest rozwijajace − zobacz ile bledow tu zrobilismy

Trivial: OK. Jeszcze raz dzięki za pomoc... Sam pewnie bym tego tak szybko nie wymyślił. Zaraz jeszcze zaimplementuję i sprawdzę, czy algorytm rzeczywiście działa.

Trivial: Działa. /* sort.c */ #include <stdio.h> #define ROZMIAR 10 void sSort(const int*, int*); void show(const int*); int main(void) { int tab[ROZMIAR] = {1, 2, 3, 3, 2, 1, −1}; int tab2[ROZMIAR]; sSort(tab, tab2); puts("Tablica przed sortowaniem to:"); show(tab); puts("A po sortowaniu to:"); show(tab2); getchar(); return 0; } void sSort(const int A[], int B[]) { int lastiMin, i, j; int iMin = 0; for (i=0; i<ROZMIAR; i++) if (A[i] < A[iMin]) iMin = i; B[0] = A[iMin]; lastiMin = iMin; for (j=0; j<ROZMIAR−1; j++) { iMin = 1; for (i=0; i<ROZMIAR; i++) if ( A[i] < A[iMin] && (A[i]>B[j] || (A[i] == B[j] && i > lastiMin)) ) iMin = i; B[j+1] = A[iMin]; lastiMin = iMin; } } void show(const int A[]) { int i; for (i=0; i<ROZMIAR; i++) printf("%d ", A[i]); putchar('\n'); }

Trivial: A jednak nie działa.

Trivial: W tablicy wynikowej trójek brak.

Trivial: Już wiem co było źle... Poprawiona wersja dla zainteresowanych: http://pastebin.com/AzZJuq9N