[request]Dwa algorytmy

[Knicz 0]

Zwracam się z uprzejmą proźbą do informatycznej braci o napisanie dwóch algorytmów - jeden przedstawiający sortowanie bąbelkowe, a drugi poprzez podstawianie. Sam bym sobie je napisał bo algorytmy w miare rozumiem ale to sortowanie to dla mnie jakaś czarna magia ;/ Z góry dzięki za pomoc

[darek_dade 2]

w Javie to tak by wyglądało:

 

public static void insertionSort (int[] list) {

 

// repeat list.length times

for(int i = 0; i < list.length - 1; i++) {

 

// element to be inserted

int j = i + 1;

 

// repeat as long as element to be inserted is

// less than the element before it in the sorted

// part of the list.

// Only until we reach the end of the list

while(j > 0 && list[j] < list[j-1]) {

 

// swap list[j] with list[j-1]

int temp = list[j];

list[j] = list[j-1];

list[j-1] = temp;

 

 

 

j--;

}

}

 

public static void bubbleSort(int[] list) {

 

// used to determine whether the list is sorted

boolean swapped = true;

 

for(int j = 0; j < list.length - 1 && swapped; j++) {

 

swapped = false;

 

// traverse the "unsorted" part of the list

// At this point j elements are sorted, so we

// do not need to compare with the last j elements.

for(int i = 0; i < list.length - 1 - j; i++) {

 

 

// compare element i with element i+1

if(list > list[i + 1]) {

 

// swap element i with element i+1

int temp = list;

list = list[i+1];

list[i+1] = temp;

 

swapped = true;

 

}

}

}

 

Preferowalem komentarze po angielsku, jak czegos nie rozumiesz to sie pytaj.

[Knicz 0]

Ale mi chodzi o algorytmy, takie z kwadracików, a nie kod w javie ;/

 

EDIT:

 

Znalazłem taki przykład ale z tego co widze to sam system sprawdzania (ale i tak wydaje mi się że nie ma znaczników o pobieraniu danych z tablicy). Mam nadzieję że teraz ktoś to poprawi bo napisać od nowa to więcej roboty niż tylko zedytować.

 

[Tommy 6]

 

Dany jest zbiór { a1 a2 a3 ...an-2 an-1 an }, który należy posortować zgodnie z funkcją porównującą fp(...). W algorytmie zastosowano następujące zmienne:

 

n liczba elementów w zbiorze

a[...] element zbioru o numerze od 1 do n, podanym w klamrach kwadratowych

i , j zmienne używane na liczniki pętli

p zmienna logiczna używana do sprawdzenia, czy cały zbiór jest już posortowany

t zmienna tymczasowa używana przy wymianie zawartości elementów tablicy

 

Algorytm rozpoczynamy nadając zmiennej i wartość 0. Zmienna ta pełni funkcję: licznika elementów, które zostały już uporządkowane na końcu zbioru - patrz przykład. Ponieważ jeszcze nie uporządkowano żadnych elementów, dlatego i przyjmuje wartość 0.

 

W pętli wewnętrznej porównujemy ze sobą kolejne elementy zbioru z elementem następnym. Zmienna p jest znacznikiem uporządkowania zbioru. Przed wejściem do pętli ustawiana jest na wartość logiczną true. Jeśli wewnątrz pętli elementy nie są uporządkowane, tzn. funkcja porównująca fp( a[j] , a[j+1] ) daje w wyniku wartość logiczną false, porównywane elementy są ze sobą zamieniane i znacznik p przyjmuje wartość false. Spowoduje to następny obieg pętli zewnętrznej, która wykonuje się do momentu, aż p będzie miało wartość logiczną true, czyli nie wystąpiła żadna zamiana elementów zbioru, co oznacza jego uporządkowanie.

 

Po porównaniu elementów i ewentualnej zamianie ich miejsc następuje zwiększenie indeksu j. Jeśli w zbiorze pozostały jeszcze jakieś elementy do porównania, to wykonywany jest następny obieg pętli wewnętrznej.

 

W przeciwnym razie pętla wewnętrzna jest kończona i następuje zwiększenie o 1 licznika pętli zewnętrznej. Powoduje to zmniejszenie o 1 liczby elementów do porównania w zbiorze - każdy obieg pętli zewnętrznej ustala pozycję ostatniego elementu zbioru - w następnym obiegu nie musimy go już sprawdzać, co przy dużej liczbie elementów znacznie zmniejsza ilość wykonywanych porównań.

 

Jeśli znacznik uporządkowania zbioru p ma wartość false, to następuje kolejny obieg pętli zewnętrznej. Jest to konieczne, ponieważ zbiór może być nieuporządkowany. Sortowanie kończymy dopiero wtedy, gdy wszystkie pary kolejnych elementów są we właściwym porządku i w trakcie przeglądania zbioru nie wystąpiło żadne przestawienie elementów.

[darek_dade 2]

Ale mi chodzi o algorytmy, takie z kwadracików, a nie kod w javie ;/

W komentarzach masz logike stojaca za sortowaniem.

[Crow 0]

O ile sie niemyle to te algorytmy byly opisane w drugiej czesci moich artykulow :]

[ogor_89 0]

Knicz, a z Boberem tego czasem nie było? Nie pomogę Ci, bo strasznie mnie denerwują schematy blokowe... Jak miałem takie zadanie to gościowi gotowe "programy" przyniosłem.