Jak zaimplementować sortowanie przez wybieranie w C?

Wybór Sortuj to kolejny algorytm, który działa poprzez zlokalizowanie najmniejszej liczby całkowitej w tablicy, a następnie przypisanie jej do najwyższej pozycji. Indeks obok pozycji najmniejszej liczby całkowitej zostanie użyty do rozpoczęcia następnej tablicy, która ma zostać przeskanowana.

Przykład sortowania przez wybór w C

Jeśli weźmiemy tablicę z liczbami [10,2,8,4,6], w której najmniejszą liczbą jest 2. W ten sposób najmniejszą liczbę, czyli 2, umieścimy na pierwszej pozycji, po której tablica będzie wyglądać jak [2,10,8,4,6]. Następnie weźmiemy następną najmniejszą liczbę, ponieważ 2 jest już teraz na właściwej pozycji. Kolejną najmniejszą liczbą jest 4, która zostanie umieszczona na drugiej pozycji, po czym tablica będzie przeszukiwana podobnie, aż do ostatecznego posortowania.

Sortowanie przez wybór w C sortuje liczby w porządku rosnącym. Poprzez modyfikację algorytmu, liczby mogą być ułożone w malejącym Sortowaniu przez Selekcję, może być również wykonywane w innych językach oprócz C, takich jak Selection Sort C++ lub Selection Sort Python.

Ucz się kursów programistycznych online z najlepszych światowych uniwersytetów. Zdobądź programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.

Algorytm sortowania przez wybór

• Najpierw ustawiamy element początkowy w sortowaniu przez wybieranie jako minimum i szukamy najmniejszego elementu w tablicy, aby uzyskać poprawną procedurę algorytmu sortowania przez wybór .
• Minimalny element jest teraz porównywany z drugim komponentem. Jeśli drugi element spadnie poniżej minimum, zamienimy je, a następnie przypiszemy trzeciemu elementowi wartość minimalną.
• W przeciwnym razie przejdziemy do trzeciego elementu i porównamy go do minimum. Jeśli drugi element przekroczy nasz pierwszy element, zamienimy go. Powtórz ten proces do ostatniego składnika.
• Po każdej iteracji zobaczymy, że nasze minimum dotarło na początek nieposortowanej listy.
• Zaczniemy indeksowanie od pierwszego wpisu nieposortowanej listy dla każdej iteracji. Dopóki lista nie zostanie posortowana lub wszystkie komponenty nie zostaną odpowiednio ustawione, będziemy powtarzać kroki od 1 do 4 kilka razy.

Popularne kursy i artykuły na temat inżynierii oprogramowania

Poniższy przykład z każdą iteracją pomoże w szczegółowym zrozumieniu procesu sortowania przez wybór w C –

Iteracja nr 1

ja [ ] = 8,5,2,6,4

Ustaw minimum – 8

Porównaj i 0 i i 1

Ponieważ i 0 > i 1 , ustaw minimum = 5.

• Porównaj i 1 i i 2

Ponieważ i 1 > i 2 , ustaw minimum = 2.

• Porównaj i 2 i i 3

Ponieważ i 2 < i 3 , ustaw minimum = 2.

• Porównaj i 2 i i 4

Ponieważ i 2 < i 4 , ustaw minimum = 2.

2 to najmniejsza liczba ze wszystkich elementów, musimy zamienić miejscami i 0 i i 2

­ Iteracja nr 2

ja [ ]= 2,5,8,6,4

Ustaw minimum 5

• Porównaj i 1 i i 2

Ponieważ i 1 < i 2 , ustaw minimum = 5.

• Porównaj i 1 i i 3

Ponieważ i 1 < i 3, ustaw minimum = 5

• Porównaj i 1 i i 4

Ponownie, i 1 < i 4 , ustaw minimum = 4.

4 jest najmniejszym elementem w tablicy, dlatego musimy zamienić miejscami i 1 i i 4 .

Iteracja nr 3

ja [ ]= 2,4,8,6,5

Ustaw minimum 8

• Porównaj i 2 i i 3

Ponieważ i 2 > i 3 , ustaw minimum = 6.

• Porównaj i 3 i i 4

Ponieważ i 3 > i 4 , ustaw minimum = 5.

5 jest najmniejszym elementem w tablicy, musisz zamienić i 2 i i 4 .

Iteracja nr 4

ja [ ] = 2,4,5,6,8

Ustaw minimum 6

• Porównaj i 3 i i 4

Ponieważ i 3 < i 4 , ustaw minimum = 6.

Minimum jest umieszczone we właściwym miejscu; w związku z tym żadna zamiana nie nastąpi.

Przykład sortowania przez wybieranie w C

// Sortowanie przez wybór w C

#include <stdio.h>

// funkcja do zamiany pozycji dwóch elementów

void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = temperatura;

}

void selectionSort(int array[], int size) {

for (int krok = 0; krok < rozmiar – 1; krok++) {

int min_idx = krok;

for (int i = krok + 1; i < rozmiar; i++) {

// Aby posortować w kolejności malejącej, zmień > na < w tym wierszu.

// Wybierz minimalny element w każdej pętli.

if (tablica[i] < tablica[min_idx])

min_idx = i;

}

// umieść min we właściwej pozycji

swap(&tablica[min_idx], &tablica[krok]);

}

}

// funkcja do wydrukowania tablicy

void printArray(int tablica[], rozmiar int) {

for (int i = 0; i < rozmiar; ++i) {

printf("%d", tablica[i]);

}

printf("\n");

}

// kod sterownika

int main() {

int dane [] = {20, 12, 10, 15, 2};

int rozmiar = rozmiar(dane) / rozmiar(dane[0]);

selectionSort(dane, rozmiar);

printf("Posortowana tablica w kolejności wysyłania:\n");

printArray(dane, rozmiar);

}

Analiza złożoności sortowania przez wybór

Dane wejściowe – podano n elementów wejściowych.

Dane wyjściowe — liczba kroków wymaganych do posortowania listy.

Logika – jeśli otrzymamy n pozycji, wykonamy n-1 porównań w pierwszym przebiegu, n-2 porównań w drugim przebiegu, n-3 porównań w trzecim przebiegu i tak dalej. W związku z tym całkowitą liczbę porównań można obliczyć za pomocą;

Wyjście -

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

Suma = n(n-1)/2 tj. O(n²)

Ponieważ metoda sortowania przez wybieranie wymaga dodatkowego miejsca w pamięci na tymczasowe zmienne do zamiany, ma złożoność czasową O(n2) i złożoność przestrzenną O(1).

Analiza złożoności czasu sortowania wyboru

Najlepszy przypadek: dla tablicy, która została wcześniej posortowana, metoda sortowania przez wybieranie ma złożoność czasową najlepszego przypadku równą O(n²).

Średni przypadek: Algorytm sortowania przez wybieranie ma średnią złożoność czasową O(n²), gdy elementy są ułożone pomieszane, to znaczy ani w porządku rosnącym, ani malejącym.

Najgorszy przypadek: Kiedy odwracamy malejący porządek tablicy do porządku rosnącego, najgorszy przypadek złożoności czasowej wynosi O(n²).

Czasowa złożoność metody sortowania przez wybór wynosi O(n²) w każdym z trzech scenariuszy. Wynika to z faktu, że musimy zidentyfikować absolutne minimum elementów dla każdego etapu, aby odpowiednio je ułożyć. Po prześledzeniu całej tablicy znajdziemy nasz minimalny element.

Wniosek

To kończy wpis na blogu „Sortowanie przez wybór w C”. Musisz zrozumieć, że można to wykonać również w innych językach, takich jak Selection Sort C++ i Selection Sort Python. Mamy nadzieję, że ten artykuł pomoże Ci zrozumieć, jak sortować elementy w C.

Sortowanie przez wybór nie jest jedynym etapem na drodze do zostania programistą. Jeśli masz nadzieję na znaczący wzrost w karierze programisty dzięki dyplomowi zawodowemu, upGrad jest tutaj! rozwoju frontendu upGrad (JavaScript, HTML, CSS), backendu (NoSQL-MongoDB) i mikrousług, możesz kontynuować kurs Master of Science in Computer Science UpGrad. Ten kurs, prowadzony przez IIIT Bangalore i LJMU Alumni Status, pomoże Ci rozpocząć karierę jako inżynier oprogramowania / programista full-stack z gigantami technologicznymi na całym świecie.

Ten kurs obejmuje podstawową wiedzę na temat narzędzi, takich jak Java, Spring i Hibernate, wzmacniając nasze umiejętności programistyczne z pełnym stosem, aby odkrywać rynek pracy z niezwykłymi możliwościami.

Zarejestruj się, aby dowiedzieć się więcej!