Złożoność czasu sortowania selekcji

55 65 35 15 85 75 25 45

Gdyby ta lista jest sortowana w kolejności rosnącej, byłoby to:

15 25 35 45 55 65 75 85

Jeśli lista jest posortowana w kolejności malejącej, byłoby to:

85 75 65 55 45 35 25 15

W tym artykule rozważane jest tylko sortowanie w kolejności rosnącej. Wybór sortuje, szukając małych elementów i zamieniając je na elementy początkowe, zaczynając od najmniejszego elementu, podczas gdy wymienione elementy początkowe stają się rosnące. Lista powinna być sortowana w kolejności rosnącej na końcu tego procesu.

Artykuł ma na celu określenie złożoności czasowej typu selekcji. Poniższe programowanie odbywa się w języku C.

Algorytm sortowania selekcji

Kroki wyboru są następujące:

• Załóżmy, że pierwszy element jest najmniejszym elementem.
• Porównaj ten element z innymi elementami, aby poznać prawdziwy najmniejszy element.
• Zamień najmniejszy element znaleziony za pomocą pierwszego elementu.
• Powtórz poprzednie trzy kroki w kolejności, z wyłączeniem pierwszego wymienionego elementu.
• Kontynuuj powtarzanie poprzednich trzech kroków, z wyłączeniem elementów w kierunku lewego (dolnego), które zostały zastąpione.
• Sortowanie kończy się po osiągnięciu ostatniego elementu.

Istnieją tutaj dwa główne typy operacji, które są porównawcze i zamiany. Przejście z jednego elementu do drugiego jest również operacją, ale zajmuje to stosunkowo niewiele czasu w porównaniu z operacją porównawczą lub operacją zamiany w sortowaniu selekcji.

NA²) Złożoność czasu

Rozważ następujący kod:

int wynik = 0;
dla (int i = 0; i<8; i++)
for (int j = 0; j<8; j++)
wynik = wynik + 1;


printf („%i \ n”, wynik);

Istnieje zewnętrzna i wewnętrzna pętla. Każda pętla iteruje osiem razy. Jedna operacja dodatku dla obu pętli jest główna operacja i działa 64 razy. 64 = 8 x 8 = 82. Wyjście to 64.

Uważa się, że ten kod ma 82 główne operacje. Jeśli 8 zostanie zastąpione przez N, złożoność czasu zostanie podana jako:

O (N2)

To wykorzystuje notację Big-O. Notacja zaczyna się od O w wielkim poziomie, a następnie nawiasów. Wewnątrz nawiasów znajduje się liczba głównych operacji kodu.

Rozważ następujący kod:

int wynik = 0;
dla (int i = 0; i<8; i++)
for (int j = i; j<8; j++)
wynik = wynik + 1;


printf („%i \ n”, wynik);

Zewnętrzna pętla iteruje osiem razy. Wewnętrzna pętla itera do ósmego raz, ale zaczyna się od i, czyli liczba iteracji pętli zewnętrznej. Wyjście to 36. Operacja jednego dodatku działa 36 razy, a nie 64 razy. Cóż, jest to nadal uważane za złożoność czasu O (N2). Działanie wyboru jest podobne do tego kodu. Innymi słowy, uważa się, że sortowanie wyboru ma złożoność czasu O (N2).

Kodowanie w c

Sort selekcji zawsze daje złożoność czasu (N2). Nie ma znaczenia, w jaki sposób ułożone są elementy tablicy. Wynika to z faktu, że wszystkie elementy są najpierw skanowane; Wtedy reszta elementów bez pierwszych jest skanowana następna; skanowanie reszty elementów bez pierwszych dwóch. Skanowanie musi zostać zakończone przed zamianą.

Lista do sortowania to:

P o i u y t r e w q

Program C jest w sumie zamówienia rosnącego. Zasadniczo program zaczyna się od:

#włączać
void SelectiOSort (char a [], int n)
dla (int i = 0; iint minindx = i;
dla (int j = i+1; jif ([j] < A[minIndx])
minindx = j;

char temp = a [i]; A [i] = a [minindx]; A [minindx] = temp; // zamiana

Biblioteka odpowiedzialna za dane wejściowe z klawiatury i wyjścia do monitora jest uwzględnione. Następnie istnieje definicja funkcji sortowania wyboru. Ta funkcja jako parametry ma tablicę (odniesienie) z listą i liczbą elementów w tablicy.

Istnieją dwa na pętle; jeden jest zagnieżdżony w drugim. Zewnętrzna for-pętla itera wszystkich elementów zaczynających się od pierwszego. Podczas gdy zewnętrzna for pętka znajduje się w indeksie, wewnętrzna iteracyjna itera. Główną operacją jest operacja porównawcza w zagnieżdżonej formie pętli.

Zmienanie odbywa się dla każdej iteracji pętli zewnętrznej tuż po zakończeniu wewnętrznej pętli.

Odpowiednią główną funkcją C programu jest:

int main (int argc, char ** argv)

int n = 10;
char a [] = 'p', „o ',„ i ”,„ u ”,„ y ”,„ t ”,„ r ”,„ e ”,„ w ”,„ q ”;
SelectiOSort (a, n);
dla (int i = 0; iprintf („%c”, a [i]);
printf („\ n”);
powrót 0;

Wyjście to:

E i o p q r t u y

posortowany.

Zaczyna się od deklaracji liczby elementów w tablicy. Następnie jest deklaracja tablicy. W tablicy jest dziesięć elementów. Te elementy są postaciami. Tak więc deklaracja tablicy zaczyna się od „char”. Następnie wywoływana jest funkcja sortowania wstawiania. Pierwszym argumentem wywołania funkcji jest nazwa tablicy. Drugim argumentem jest liczba elementów w tablicy.

Następuje po pętli. To za pętla drukuje posortowane znaki. Używa funkcji printf () stdio.Biblioteka H. Pierwszym argumentem tej funkcji jest ciąg. Ten ciąg jest specjalnym ciągiem, ale nadal ma znaki, które zostałyby wydrukowane. Ma również parametry argumentów. W tym przypadku istnieje tylko jeden parametr, %c. Jest też tylko jeden argument, [i]. Po wydrukowaniu wszystkich znaków na jednej linii, następna funkcja printf () przenosi wyjście do następnego wiersza.

Wniosek

W tym artykule omówiono kroki w zakresie sortowania selekcji, które obejmują przyjęcie pierwszego elementu, jest najmniejszym elementem, porównując ten element z resztą elementów i znajomość prawdziwego najmniejszego elementu. Ponadto użytkownik musi zamienić najmniejszy element znaleziony w pierwszym elemencie i powtórzyć poprzednie trzy kroki w kolejności, z wyłączeniem pierwszego wymienionego elementu. Ostatnie kroki obejmują ciągłe powtarzanie trzech kroków powyżej, z wyłączeniem elementów w kierunku lewego (dolnego), które zostały zastąpione; Sortowanie kończy się po osiągnięciu ostatniego elementu. Złożoność czasu dla selekcji jest O (N2).