Insertion Sorting and Recursive Insertion

Question

I would like to change the function to a recursive function, I’m error tried so

1 se  n > 1  então    
2   Inserção-Rec (A, n−1)
3   x ← A[n]
4   i ← n−1
5   enquanto  i > 0  e  A[i] > x  faça
6   A[i+1] ← A[i]
7   i ← i−1
8   A[i+1] ← x

aqui só esta o pseudo código do que tenho que fazer pois o meu esta bem errado.

#include <stdlib.h>
#include <string.h>
#include <string.h>
#define N 1000

/*Ordenar crescente por inserção*/



int ordenacao_por_insercao(int v[], int n);

int main(){
  int v[N];
  int i, n;

   printf("Digite o tamanho do vetor :");
   scanf("%d", &n);

   for(i=0; i<n; i++){
    printf("digite o valor do v[%i] : ",i);
    scanf("%d", &v[i]);
   }
   for(i=0;i<n;i++){

   printf("\nVetor   V[%d] : %d",i,v[i]);
   }

   ordenacao_por_insercao(v,n);

  for(i=0;i<n;i++){

   printf("\n\nVetor ordenado  V[%d] : %d",i,v[i]);
   }
}

int ordenacao_por_insercao(int v[], int n){
    int j, i, chave;
    for(j = 0; j < n; j++){
        chave = v[j];
        i = j - 1;
        while(i >= 0 && v[i] > chave){
            v[i + 1] = v[i]; /*encontrar o ponto onde chave é
            inserido no subvetor ordenado*/
            i = i - 1;
        }
        v[i + 1] = chave; /*chave é inserido no subvetor
        ordenado*/
    }
    return v;
}

Note put the code here for other people who have problem with that first part see and try to understand! Thank you.

Answer 1

Below is an example of sorting by direct insertion. (It is a little more efficient when compared to the direct selection method and the Bubble Sort)

#include<stdio.h>
int main()
{
   int i, j, tamanho, chave, trocas;
   int vetor[10];
   srand(time(0));
   tamanho=10;
   printf("Vetor desordenado...\n");
   for(i=0;i<tamanho;i++)
      {
      vetor[i]=rand()%100;
      printf("Vetor [%2d]: %3d\n",i+1,vetor[i]);
      }
   for (j=1;j<tamanho;j++)
      {
      chave = vetor[j];
      i = j - 1;
      while((i>=0) && (vetor[i]>chave))
         {
         vetor[i+1] = vetor[i];
         i = i - 1;
         trocas++;
         }
      vetor[i+1] = chave;
      }

   printf("Vetor ordenado...\n");
   for(i=0;i<tamanho;i++)
      printf("Vetor[%2d]: %3d\n",i+1,vetor[i]);
   printf("Trocas efetuadas: %3d\n\n",trocas);
   return 0;
}

source: https://www.vivaolinux.com.br/script/Ordenacao-por-insercao-direta

Don’t Panic! ^_^

Answer 2

void ordenacao_por_insercao(int v[], int n){
    int  i, chave;
    if(n>1)
        ordenacao_por_insercao(v, n-1);

        chave = v[n];
        i = n - 1;
        while(i > 0 && v[i] > chave){
            v[i + 1] = v[i]; /*encontrar o ponto onde chave é
            inserido no subvetor ordenado*/
            i = i - 1;
             v[i + 1] = chave; /*chave é inserido no subvetor
        ordenado*/
        }

    }

I think that’s it now I’d like to know if this is the most efficient?