Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

Sortowanie przez selekcję (przez wybór)

powrót

Następny algorytm sortujący, który omówimy, ma złożoność rzędu {tex}O(n^2){/tex} . Podobnie jak sortowanie bąbelkowe nie poradzi sobie przy porządkowaniu większych zbiorów.

Strategia sortowania przez wybór jest bardzo prosta. Szukamy najmniejszego elementu w zbiorze i zamieniamy go z elementem stojącym na pozycji pierwszej. Następnie szukamy znowu elementu najmniejszego w zbiorze pominiętym o pierwszy element i wstawiamy go na pozycję drugą. Czynności powtarzamy do momentu otrzymania jednoelementowego podzbioru. Rozpatrzmy przykład liczb:

{tex}3,\ 2,\ 4,\ 3,\ 1,\ 2,\ 0{/tex}

Przeanalizujmy porządkowanie tych liczb metodą przez selekcję:

{tex}\overbrace{3}^{zamiana\ z\ 0},\ 2,\ 4,\ 3,\ 1,\ 2,\ 0{/tex}

{tex}0,\ \overbrace{2}^{zamiana\ z\ 1},\ 4,\ 3,\ 1,\ 2,\ 3{/tex}

{tex}0,\ 1,\ \overbrace{4}^{zamiana\ z\ 2},\ 3,\ 2,\ 2,\ 3{/tex}

{tex}0,\ 1,\ 2,\ \overbrace{3}^{zamiana\ z\ 2},\ 4,\ 2,\ 3{/tex}

{tex}0,\ 1,\ 2,\ 2,\ \overbrace{4}^{zamiana\ z\ 3},\ 3,\ 3{/tex}

{tex}0,\ 1,\ 2,\ 2,\ 3,\ \overbrace{4}^{zamiana\ z\ 3},\ 3{/tex}

{tex}0,\ 1,\ 2,\ 2,\ 3,\ 3,\ 4{/tex}

Rozwiązanie w C++:

#include<iostream>
#include<cstdlib>
using namespace std;
 
void selection_sort(int tab[],int n) //n - ilość elementów do posortowania
{
int mn_index; //zmienna pomocnicza przechowująca indeks komórki 
        //z minimalną wartością
  for(int i=0;i<n-1;i++)
  {
    mn_index = i;
    for(int j=i+1;j<n;j++) //pętla wyszukuje najmniejszy element w podzbiorze nieposortowanym
    if(tab[j]<tab[mn_index])
      mn_index = j;
 
    //zamiana elementu najmniejszego w podzbiorze z pierwszą pozycją nieposortowaną
  swap(tab[i], tab[mn_index]);
  }
}
 
int main()
{
  int *tab, n;
 
  cout<<"Ile liczb chcesz posortować? ";
  cin>>n;
 
  tab = new int [n];
 
  for(int i=0;i<n;i++)
    cin>>tab[i]; //wczytanie liczb do posortowania
 
  selection_sort(tab,n); //sortowanie przez selekcję
 
  for(int i=0;i<n;i++)
    cout<<tab[i]<<" "; //wypisanie posortowanych elementów
 
  cout<<endl;
  system("pause");  
  return 0;
}