Sortowanie Przez Wybór

O sortowaniu

Sortowanie przez wybór (ang. selection sort) polega na znajdowaniu najmniejszego elementu w liście, ustawieniu go na początku listy, a następnie powtórzenia dla listy bez elementu pierwszego. Na początku bierzemy listę L w której znajdujemy najmniejszy element w liście, a następnie zamieniamy go z pierwszym elementem rozpatrywanej listy. Kolejny krok polega na posortowaniu w ten sam sposób listę bez pierwszego elementu.

Weźmy przykładowo listę L={5, 3, 4, 1, 2}. Będziemy sortować elementy rosnąco. Kolejno będziemy wykonywać:

W przypadku, gdy lista jest jednoelementowa nie musimy już szukać elementu najmniejszego - możemy go normalnie przepisać.

Implementacja

Załóżmy, że chcemy posortować ciąg liczb rzeczywistych typu double. Do funkcji przekażemy wskaźnik na listę L oraz liczbę całkowitą n - długość listy L:

1. void sort(double* L, int n){
2.   for(int i = 0; i < n - 1; i++){
3.     int min = i;
4.     for(int j = i + 1; j < n; j++){
5.       if(L[j] < L[min]){
6.         min = j;
7.       }
8.     }
9.     double t = L[i];
10.     L[i] = L[min];
11.     L[min] = t;
12.   }
13. }

(2.) Wykonujemy pętle dla każdej podlisty listy L - od listy długości n od indeksu 0, po listę długości 2 od indeksu n-3. (3.) W i-tej iteracji pierwszy element ma indeks i. Zakładamy, że jest on elementem najmniejszym i zapisujemy jego indeks do zmiennej min. (4.) Następnie wśród pozostałych elementach podlisty szukamy (5.) elementu mniejszego. Jeśli taki znajdziemy to (6.) zapisujemy jego indeks j w zmiennej min. (9. - 11.) Zamieniamy miejscami pierwszy element podlisty z elementem mniejszym.

W ten sposób posortowaliśmy listę rosnąco. Policzmy złożoność czasową: czyli co oznacza, że nasz algorytm zawsze będzie wykonywać tyle samo porównań.

• Kod źródłowy Implementacja

Poprawa implementacji

Aktualny algorytm wykona dokładnie n-1 zamian co można poprawić, aby liczba zamian była mniejsza. Możemy spróbować zmniejszyć ilość zamian upewniając się, że indeksy elementów, które zamieniamy są różne. W ten sposób dla pewnych przypadków list sortowanie odbędzie się szybciej.

1. void sort(double* L, int n){
2.   for(int i = 0; i < n - 1; i++){
3.     int min = i;
4.     for(int j = i + 1; j < n; j++){
5.       if(L[j] < L[min]){
6.         min = j;
7.       }
8.     }
9.     if(i != min){
10.       double t = L[i];
11.       L[i] = L[min];
12.       L[min] = t;
13.     }
14.   }
15. }

Efektywność algorytmu poprawia warunek w (9.) sprawdzający czy indeks pierwszego elementu listy jest różny od indeksu elementu najmniejszego w podliście.

Testowanie funkcji

Po uruchomieniu programu należy wpisać liczbę n jak długa jest lista, a potem n elementów.

1. int main () {
2.   int n;
3.   cin >> n;
4.   double* L = new double[n];
5.   for(int i = 0; i < n; i++)
6.     cin >> L[i];
7.   sort(L, n);
8.   for(int i = 0; i < n; i++)
9.     cout << L[i] << " ";
10.   delete[] L;
11.   system("pause");
12.   return 0;
13. }

Przykładowo dla listy [5 3 4 1 2] otrzymamy:

1. 1 2 3 4 5

• Kod źródłowy Poprawa implementacji

Zadania

Zadanie 1

Zmodyfikuj kod źródłowy, aby funkcja sort() sortowała litery alfabetu łacińskiego alfabetycznie malejąco.

Przykładowo dla listy [d b a e c] program wypisze na ekran:

1. e d c b a

• Kod źródłowy Zadanie 1