sortowanie najmniejszym kosztem

na zajeciach dostalem zadanie odnosnie wymyslenia algorytmu w C ktory sortuje wartosci w tablicy "najmniejszym kosztem" a jasniej:
mamy wypelniona tablice 5 elementowa (nie wazne czy wypelniamy ja sami podajac wartosci czy sa losowe) a program sortuje ja i wyswietla krok po kroku co robi np:
mamy tablice: 3 1 7 10 5
program wyswietla:

1. zamieniam 3 z 1 suma 4
2. zamieniam 10 z 5 suma 19
3. zamieniam 7 z 5 suma 31
   posortowana tablica: 1 3 5 7 10 koszt 31
   (sortowanie 3 z 1; 5 z 7 i 7 z 10 nie wyswietla bo koszt bylby wiekszy o 2)
   prosilbym o napisanie takiego algorytmu gdyz kompletnie nie mam pojecia jak to zrobic

QuickSort przytoczony przez Marka ma pesymistyczną złozoność O(n²). Ciebie interesuje, żeby ilość operacji była jak najmniejsza, więc obczaj inne algorytmy, które zawsze mają O(nlogn) lub niższą, np. kubełkowe, przez scalanie, przez kopcowanie. A najfajniej by było - i tu pewnie szansa na jakiś bonus od ćwiczeniowca - zaimplementować kilka algorytmów sortowania, potem puścić kilkadziesiąt testów porównawczych na losowych danych i wypluć informację o najbardziej wydajnym algorytmie (lub algorytmach, jeśli najlepsze wyniki będą do siebie bardzo zbliżone).

1. Z algorytmami to jest tak, że czasami można wymyślić coś trochę szybszego od quicksorta jeśli tylko się wie coś z góry o zbiorze liczb. Ewentualnie dobrać optymalne parametry dla znanych już algorytmów.

2. Drugim problemem jest to, że w Twoich danych brakuje zdefiniowanego "najmniejszego kosztu".

Tak czy inaczej - skoro to jest na zajęcia, to przegooglaj hasło "sorting algorithms".

ŁF napisał(a):

. Ciebie interesuje, żeby ilość operacji była jak najmniejsza

no wlasnie nie do konca chocby z przykladu: 3 z 1, 10 z 5, 7 z 5 -> ilosc operacji 3 suma (koszt) 31, a 3 z 1, 5 z 7 i 7 z 10 to tez 3 operacje zas ich koszt to 33

wartek01 napisał(a):

brakuje zdefiniowanego "najmniejszego kosztu".

chyba nie rozumiem (chodzi o czysta definicje?: "posortowac najmniejszym kosztem tzn posortowac tak by suma przestawianych elementow byla jak najmniejsza")

wartek01 napisał(a):

Tak czy inaczej - skoro to jest na zajęcia, to przegooglaj hasło "sorting algorithms".

googlalem pare dni i niczego nie znalazlem wiec napisalem tutaj na forum :)

Możesz mieć "najmniejszy koszt" zdefiniowany w liczbie wykonanych operacji porównania, przypisania, tych obu.

Jeśli googlałeś kilka dni na temat algorytmów sortowania - najbardziej opisanego tematu w internecie, z masą artykułów, źródeł i materiałów... to coś z tobą nie tak.

P.S. Quick-sort nie jest najlepsża opcją dla małych zbiorów danych.

wydaje mi sie ze powinien pracowac wg nastepujacych 2 krokow:

1. dopoki jest mozliwe wyszukuje i zamienia pozycje tak by po zamianie obie wartosci byly na swoich (odpowiednich) miejscach
2. po zakonczeniu 1). wyszukuje najwiekszej i zamienia ja z mozliwie najmniejsza by najwieksza po zamianie byla na swoim miejscu

ale nie potrafie tego napisac i nie wiem czy to na pewno poprawny "schemat" dzialania

http://rextester.com/GBAOD54889

wersja rekurencyjna zlożoność O(n ^ 2), można lepiej O(n * log n) przy użyciu dwóch priority queues

znajdujesz najmniejszą wartość w tablicy, sprawdzasz czy jest potrzebny swap, jeśli tak to go wykonujesz
zmniejszasz rozmiar tablicy, aby nie zawierała posortowanych (we właściwych miejscach) elementów
znajdujesz największą wartość w tablicy, sprawdzasz czy jest potrzebny swap, jeśli tak to go wykonujesz
zmniejszasz rozmiar tablicy, aby nie zawierała posortowanych (we właściwych miejscach) elementów

reptile333 napisał(a):

znajdujesz najmniejszą wartość w tablicy, sprawdzasz czy jest potrzebny swap, jeśli tak to go wykonujesz
zmniejszasz rozmiar tablicy, aby nie zawierała posortowanych (we właściwych miejscach) elementów
znajdujesz największą wartość w tablicy, sprawdzasz czy jest potrzebny swap, jeśli tak to go wykonujesz
zmniejszasz rozmiar tablicy, aby nie zawierała posortowanych (we właściwych miejscach) elementów

to chyba nie jest dobre: z przykladu 3 1 7 10 5
szukam najmniejszej 1 i swap z 3
zmniejszam tablice do 7 10 5
i zgodnie z tym co napisales powinienem zamienic 5 z 7 co jest zle jak pisalem juz wyzej ;/

Wszystko wygląda dobrze, zawsze tablicę zmniejszasz o 1 element z lewej lub prawej strony.
Dodałem więcej logowania, pokazuję jak obecnie wygląda tablica i jakie elementy są zamieniane

case 1) starting with a smallest value
3,1,7,10,5,
1 swapping 1 with 3
3,7,10,5,
-1 swapping 10 with 5
3,7,5,
no swapping 3 has a correct position
7,5,
-1 swapping 7 with 5
31
1,3,5,7,10,
case 2) starting with a largest value
3,1,7,10,5,
-1 swapping 10 with 5
3,1,7,5,
1 swapping 1 with 3
3,7,5,
-1 swapping 7 with 5
3,5,
no swapping 3 has a correct position
31
1,3,5,7,10,

ok dzieki wielkie teraz juz rozumiem :)
z przerobieniem tego na C nie powienienem miec problemow, a daloby rade bez vectorow?

powinno dać radę, trzeba użyć tablicy zamiast vectora

reptile333 napisał(a):

powinno dać radę, trzeba użyć tablicy zamiast vectora

dzikei juz przerobilem dziala chyba idealnie tzn nie wiedzialem co to robi i jak to zastapic " for(auto x: v) cout << x << "," " wiec calkowicie wywalilem i dziala :)
a przy okazji moglbys powiedziec co to robi i jak to zamienic na c?
i dzieki wszystkim ktorzy pomogli :)

http://stackoverflow.com/questions/1534748/design-an-efficient-algorithm-to-sort-5-distinct-keys-in-fewer-than-8-comparison