What defines a stable ordering algorithm?

Question:

It is known that there are several ways to sort the data in a collection, some examples are the famous bubble sort , insertion sort and selection sort .

I've heard that some algorithms are stable and some are not. What defines a stable ordering algorithm? Are any of the three in the example stable?

If possible I would like some example of some sorting algorithm that is stable and a code representation that is easy to read (pseudo-language, Python or C#).

Answer:

A sorting algorithm is considered stable when it manages to preserve the order of registration of equal keys, in other words, if the records appear in the ordered sequence in the same order as 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]

The result will be:

1[d], 2[b], 2[c], 3[a]

Unstable algorithms subject the elements associated with objects to be sorted: 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 as they do in the input array. This property is important when satellite data accompanying the elements being sorted must be transported along with the element. The ordering by count algorithm is stable as it reads the intermediate array backwards when creating the resulting vector. But it is the maintenance of this stability that forces 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:

Bubble sort ordering (stable)

for(i=n-1;i>0;i--)
      for(j=0;j
            if( v[j] > v[j+1])
                  swap(v[j], v[j+1]);    

Insertion sort order (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 sorting (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, insertion 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;
    }

}

on this link there are more examples

Scroll to Top