A sorting algorithm is considered stable when it manages to preserve the order of record of equal keys, in other words if the records appear in the ordered sequence in the same order they are in the initial sequence.
An example of a stable algorithm, ordering the sequence of numbers (keys) with letters (records)
3[a], 2[b], 2[c], 1[d]
Obligatorily the result will be:
1[d], 2[b], 2[c], 3[a]
Non-stable algorithms subject the elements associated with the objects to be ordered:
1[d], 2[c], 2[b], 3[a]
An algorithm is stable when numbers with the same value appear in the output array in the same order they are in the input array.
This property is important when the satellite data accompanying the elements being ordered must be transported along with the element.
The counting sorting algorithm is stable as it reads the intermediate array backwards when creating the resulting vector. But it is the maintenance of this stability that requires the algorithm to use an auxiliary array. If the stability property did not need to be maintained, the algorithm could already work on the initial array itself, using less memory.
examples:
Ordering Bubble Sort (stable)
for(i=n-1;i>0;i--)
for(j=0;j
if( v[j] > v[j+1])
swap(v[j], v[j+1]);
Sorting by inserction Sort (stable)
for(j=1; j
chave = v[j];
i = j-1;
while(i >= 0 && v[i] > chave){
v[i+1] = v[i];
i--;
}
v[i+1] = chave;
}
Quicksort ordering (Not stable)
#include
using namespace std;
int partition(int vec[], int left, int right) {
int i, j;
i = left;
for (j = left + 1; j <= right; ++j) {
if (vec[j] < vec[left]) {
++i;
swap(vec[i], vec[j]);
}
}
swap(vec[left], vec[i]);
return i;
}
void quickSort(int vec[], int left, int right) {
int r;
if (right > left) {
r = partition(vec, left, right);
quickSort(vec, left, r - 1);
quickSort(vec, r + 1, right);
}
}
Quicksort da stdlib. h
#include
int compara(const void *pa , const void *pb){
int a = *(int *)pa;
int b = *(int *)pb;
return a-b;
}
qsort(v,n,sizeof(n) , compara);
I have a Java implementation of Bubble Sort, inserction Sort and Selection Sort.
public class Main {
public static void main(String[] args) {
int[] vetor = { 3, 2, 2, 1 };
System.out.println(Arrays.toString(bubbleSort(vetor)));
System.out.println(Arrays.toString(insertionSort(vetor)));
System.out.println(Arrays.toString(selectionSort(vetor)));
}
public static int[] bubbleSort(int vetor[]) {
for (int i = vetor.length; i >= 1; i--) {
for (int j = 1; j < i; j++) {
if (vetor[j - 1] > vetor[j]) {
int aux = vetor[j];
vetor[j] = vetor[j - 1];
vetor[j - 1] = aux;
}
}
}
return vetor;
}
public static int[] insertionSort(int[] vetor) {
for (int i = 0; i < vetor.length; i++) {
int valor = vetor[i];
int j = i - 1;
while (j >= 0 && vetor[j] >= valor) {
vetor[j + 1] = vetor[j];
j--;
}
vetor[j + 1] = valor;
}
return vetor;
}
public static int[] selectionSort(int[] vetor) {
for (int i = 0; i < vetor.length; i++) {
int indiceMinimo = i;
for (int j = i + 1; j < vetor.length; j++) {
if (vetor[j] < vetor[indiceMinimo]) {
indiceMinimo = j;
}
}
int valor = vetor[indiceMinimo];
vetor[indiceMinimo] = vetor[i];
vetor[i] = valor;
}
return vetor;
}
}
in this link there are more examples
Now there is a very complicated theme, data ordering.
– Jorge B.