Strona główna » Algorytmy » Sortowanie » Sortowanie Przez Wybór

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ć:

Lista nieposortowanaMin. elementLista posortowana
{5, 3, 4, 1, 2}1{1}
{3, 4, 5, 2}2{1, 2}
{4, 5, 3}3{1, 2, 3}
{5, 4}4{1, 2, 3, 4}
{5}5{1, 2, 3, 4, 5}

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ń.

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

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