Czy to sortowanie zadziała (?)

Question

Zamierzam napisać własny algorytm (?) sortujący i mam już pomysł jak go zrobić, ale nie wiem, czy taki sposób byłby efektywny. Oto zarys:

1. Przekazuje się tablicę plików do funkcji, która sprawdza dla każdego elementu czy jest większy od elementu o jeden index "niżej". Jeśli jest zwraca true + wartość + index, jeśli nie false + wartość + index (będzie specjalna struktura do tego)

2. Teraz dla każdej wartości oznakowanej "false" ustala się wartość najwyższą z tablicy (np. Dla 5 4 2 3 będzie to 4).

3. Oblicza się różnicę tych liczb oznaczonych jako "false" z tą najwyższą. (Np. 5-3 i 5-2) liczba z której różnica będzie mniejsza powędruje na górę, przed tą najwyższą liczbę. (w tym wypadku 3)

4. Tworzy się nową tablicę i wypełnia się wynikami; wypisuje się ją na ekran.  

 

 

Jeszcze tego nie okodowałem, naewet nie tknąłem środowiska, więc nwm jak to zadziała.

 

Czy to ma jakieś luki? Lub będzie działać bardzo nie efektywnie? Co można w tym zmienić?

 

 

PS język C++

Answer 1

Szczerze? Nie widzę tego.

Pisząc wartość najwyższa (w punkcie 2) masz na myśli wartość max z false czy ogólną?

Jeżeli byś to chciał tak posortować, to twój algorytm jest bardzo podobny do https://pl.wikipedia.org/wiki/Sortowanie_przez_wybieranie z niepotrzebnymi operacjami (wyznaczanie różnicy z maksymalną wartością, nadawanie wszystkim komórkom w tablicy dodatkowych wartości [true i false] itp). Do tego złożoność obliczeniowa takiego algorytmu (szybko licząc) jest minimum rzędu kwadratowego.

Aglorytm Quicksort ma złożoność nlogn (w przybliżeniu). Sortowanie przez scalanie 2nlogn.

Comments

No to yak. Racja, machnąłem się. Oblicza się różnice (w tym przypadku) dla 4-3 i 4-2 a nie 5-3 i 5-2. I nie wiem co to jest ten nlogn oraz 2nlogn, ponieważ algorytmiki nie ogarniam, a jakiś taki algorytm, byłby wstępem do niej..