Sortowanie przez selekcję i wstawianie

Sortowanie przez selekcję

Inaczej nazywane "Selection Sort" lub "Sortowanie przez wybór".

Kolejne z sortowań o złożoności O(n²).

Całe sortowanie wykonuje się w dwóch pętlach.
Jego istota polega na wyszukiwaniu w zbiorze elementu najmniejszego i zamienianiu go z pierwszym. Wraz z kolejnym okrążeniem głównej pętli zakres poszukiwań się zawęża.
Przy pierwszym okrążeniu przeszukujemy całą tablicę. Najmniejszy element zamieniamy z pierwszym elementem tablicy.
Przy drugim okrążeniu przeszukujemy już tablicę bez pierwszego elementu, a najmniejszy element zamieniamy z drugim elementem sortowanej tablicy (pierwszym w wypadku tablicy, na której właśnie działamy).

Najlepiej zobaczyć to na przykładzie kodu w C++. Został on napisany na wzór zadania pomocniczego "Z2 - Sortowanie". Z całego tego bałaganu najważniejsza jest podwójna pętla for.

Kod z pełnym komentarzem:

//Implementacja C++ by slic3
 
#include <iostream>
using namespace std;
 
void SelectionSort()
{
//Wczytujemy zmienną "ile", która mówi, ile liczb będzie w tablicy
// oraz informuje jak dużą tablicę zadeklarować.
//Tu zgodnie z treścią zadania pomocniczego miało być "n",
// ale czego się nie robi dla czytelności...
int ile; cin>>ile;
int A[ile];
 
//Pętla wczytuje "ile" liczb do tablicy "A[ile]" 
for (int b=0; b!=ile; b++)
cin>>A[b];
 
//Wczytujemy zmienne pomocnicze "i", "j", oraz "min" 
int i=0;
int j=0;
int min;
 
//Podwójna pętla for, która wykonuje właściwe sortowanie
for (i=0; i!=ile-1; i++)
 {
 min=i;
 for (j=i+1; j!=ile; j++)
  {
  if (A[j]<A[min]) min=j;
  }
 swap (A[i], A[min]);
 }
 
//Pętla zajmująca się wypisaniem liczb z posortowanej tablicy
for (int c=0; c!=ile; c++)
 cout<<A[c]<<" ";
 
//Zakończenie linii, dla estetyki
cout<<endl; 
}
 
int main()
{
//Wczytujemy zmienną "z", która mówi, ile razy wykonać sortowanie
int z; cin>>z;
 
//Pętla wykonuje sortowanie "z" razy
for(int a=0; a!=z; a++)
 SelectionSort();
 
//No comment :)
return 0;
}

Kod bez komentarza, być może bardziej czytelny (zależy dla kogo):

//Implementacja C++ by slic3
 
#include <iostream>
using namespace std;
 
void SelectionSort()
{
int ile; cin>>ile;
int A[ile];
 
for (int b=0; b!=ile; b++)
cin>>A[b];
 
int i=0;
int j=0;
int min;
 
for (i=0; i!=ile-1; i++)
 {
 min=i;
 for (j=i+1; j!=ile; j++)
  {
  if (A[j]<A[min]) min=j;
  }
 swap (A[i], A[min]);
 }
 
for (int c=0; c!=ile; c++)
 cout<<A[c]<<" ";
 
cout<<endl; 
}
 
int main()
{
int z; cin>>z;
 
for(int a=0; a!=z; a++)
 SelectionSort();
 
return 0;
}

Sortowanie przez wstawianie

Inna poprawna nazwa to "Insertion Sort".

Jego złożoność wynosi oczywiście O(n²).

Jego działanie jest następujace:
Na początku (pierwsze przekręcenie pętli for) tworzymy listę uporządkowaną, która zawiera tylko jeden element (ostatni element tablicy). Wybieramy element przed listą i zapamiętujemy. Wybrany element porównujemy z kolejnymi elementami listy uporządkowanej i "znajdujemy dla niego miejsce" (odpowiada za to pętla while). Robimy to dopóty, dopóki lista uporządkowana nie zajmie całego zbioru (tablicy).

Kod w C++ na wzór zadania pomocniczego "Z2 - Sortowanie".

Full comment:

//Implementacja C++ by slic3
 
#include <iostream>
using namespace std;
 
void SelectionSort()
{
//Wczytujemy zmienną "ile", która mówi, ile liczb będzie w tablicy
// oraz informuje jak dużą tablicę zadeklarować.
//Tu zgodnie z treścią zadania pomocniczego miało być "n",
// ale czego się nie robi dla czytelności...
int ile; cin>>ile;
int A[ile];
 
//Pętla wczytuje "ile" liczb do tablicy "A[ile]" 
for (int b=0; b!=ile; b++)
cin>>A[b];
 
//Wczytujemy zmienne pomocnicze "i", "j", oraz "pom" 
int i=0;
int j=0;
int pom;
 
//Połączenie pętli for i while, które wykonuje sortowanie właściwe
for (i=ile-2; i>=0; i--)
 {
 pom=A[i];
 j=i+1;
 while ((pom>A[j]) && (j<ile))
  {
  A[j-1]=A[j];
  j++;
  }
 A[j-1]=pom;
 }
 
//Pętla zajmująca się wypisaniem liczb z posortowanej tablicy
for (int c=0; c!=ile; c++)
 cout<<A[c]<<" ";
 
//Zakończenie linii, dla estetyki
cout<<endl; 
}
 
int main()
{
//Wczytujemy zmienną "z", która mówi, ile razy wykonać sortowanie
int z; cin>>z;
 
//Pętla wykonuje sortowanie "z" razy
for(int a=0; a!=z; a++)
 SelectionSort();
 
//No comment :)
return 0;
}

Wersja czytelna, ale mniej edukacyjna:

#include <iostream>
using namespace std;
 
void SelectionSort()
{
int ile; cin>>ile;
int A[ile];
 
for (int b=0; b!=ile; b++)
cin>>A[b];
 
int i=0;
int j=0;
int pom;
 
for (i=ile-2; i>=0; i--)
 {
 pom=A[i];
 j=i+1;
 while ((pom>A[j]) && (j<ile))
  {
  A[j-1]=A[j];
  j++;
  }
 A[j-1]=pom;
 }
 
for (int c=0; c!=ile; c++)
 cout<<A[c]<<" ";
 
cout<<endl; 
}
 
int main()
{
int z; cin>>z;
 
for(int a=0; a!=z; a++)
 SelectionSort();
 
return 0;
}

Mam nadzieję, że moje wypociny wam się na coś przydadzą,
pozdrawiam,
slic3