Selection sort

Ang selection sort ay maituturing na pinakasimple sa lahat ng mga sorting algorithms. Isinasagawa ito sa pamamagitan ng paghahati sa mga numerong isasaayos sa dalawang bahagi. Ang isang bahagi ay binubuo ng mga numerong naayos na samantalang ang natirang bahagi ay binubuo naman ng mga numerong wala pa sa ayos.

Nagsisimula ang prosesong ito na walang lamang ang unang bahagi (naayos) habang ang ikalawang bahagi naman (hindi pa naayos) ay kinabibilangan ng lahat ng numerong nasa listahan.

Isinasagawa ang selection sort sa pamamagitan ng paulit-ulit na paghanap ng pinakamaliit (o pinakamalaking) numero sa hindi pa naayos na bahagi ng listahan at paglagay ng nasabing numero sa dulo ng naayos ng bahagi. Matatapos ang proseso kapag ang lahat ng laman ng hindi pa naayos na bahagi ay nailipat na sa naayos ng bahagi.

Ang selection sort ay pinakamabuting gamitin sa mga maliliit na listahan. Pinakamalala naman itong gamiting kapag ang listahan ay nakaayos sa baligtad na paraan.

Ang complexity ng algorithm na ito ay O(n²). Gayunpaman, sa halos lahat ng pagkakataon ay mas mabilis ito sa bubble sort at gnome sort na may parehong complexity. May mga pagkakataon din kung saan mas mabuti itong kagimitin kaysa sa mga mas kumplikadong mga algorithm.

Halimbawa:

5 4 2 3 1
1 4 2 3 5
1 2 4 3 5
1 2 3 4 5
1 2 3 4 5

Code snippets:

Java

public void selectionSort(int[] arr) {

     int i, j, minIndex, tmp;
     int n = arr.length;
     for (i = 0; i < n - 1; i++) {
           minIndex = i;
           for (j = i + 1; j < n; j++)
                 if (arr[j] < arr[minIndex])
                       minIndex = j;
           if (minIndex != i) {
                 tmp = arr[i];
                 arr[i] = arr[minIndex];
                 arr[minIndex] = tmp;
           }
     }

}

C++

void selectionSort(int arr[], int n) {

     int i, j, minIndex, tmp;    
     for (i = 0; i < n - 1; i++) {
           minIndex = i;
           for (j = i + 1; j < n; j++)
                 if (arr[j] < arr[minIndex])
                       minIndex = j;
           if (minIndex != i) {
                 tmp = arr[i];
                 arr[i] = arr[minIndex];
                 arr[minIndex] = tmp;
           }
     }

}

Mga Sanggunian

http://www.algolist.net/Algorithms/Sorting/Selection_sort
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/selectionSort.htm
http://www.cprogramming.com/tutorial/computersciencetheory/sorting2.html