Sorting in C using recursion

Question

Sorting in C using recursion

I need to make a vector ordering code using recursion. I searched about sorting methods and found two that would be interesting: selection sort and quicksort. However, I tried to use Selection sort and was unsuccessful. Follow my code:

#include <stdio.h>
#include <stdlib.h>


int numeros[5]; 
int i;

void Ordenar(int numeros[], int i, int j){
  int aux;
  int menor;

  if(i==3){
  for(i=0; i<5; i++){
    printf("%d", numeros[i]);
  }
  return 0;
  }

  if(j==4){
    return Ordenar(numeros, i+1, i+2);
  }
  if(numeros[i]>numeros[j]){
    menor = j;
    aux = numeros[j];
    numeros[menor] = numeros[i];
    numeros[i] = aux;
  }

  else{
    return Ordenar(numeros, i, j+1);
  }

}


int main(){
  for(i=0; i<5; i++){
    scanf("%d", &numeros[i]);
  }

  Ordenar(numeros, 0, 1);
  return 0;
}

The idea was to leave the first number standing and compare them with all the others, until you find the smallest. Then do the same with the second, third, etc.

Another question: What is better to use for sort a vector with recursion: selection sort or quicksort?

0

c classificação recursão

Author: heavydsoul, 2017-06-20

Source

1 answers

score 1 · Accepted Answer

SELECTION SORT

It is a simple algorithm that takes up little memory and is quite efficient if you sort small volumes of data.

Is extremely slow to sort large volumes of data, its complexity will always be O(n^2).

Example Code (Tested):

#include <stdio.h>
#include <string.h>

#define swap( _a, _b ) do{ int _tmp = _a; _a = _b; _b = _tmp; } while(0)

void selectionsort( int array[], int tam )
{
    int i = 0;
    int j = 0;
    int min = 0;

    for( i = 0; i < ( tam - 1 ); i++)
    {
        min = i;

        for( j = (i+1); j < tam; j++ )
            if( array[j] < array[min] )
                min = j;

        if( i != min )
            swap( array[i], array[min] );
    }
}

void exibir( int array[], int tam )
{
    int i = 0;

    for( i = 0; i < tam; i++ )
        printf( "%s%d", (i>0)?", ":"", array[i] );

    printf("\n");
}


int main( int argc, char * argv[] )
{
    int numeros[16] = { 6, -9, 7, 5, 3, -1, 8, -6, 4, 2, 1, -3, -5, 9, -8, 0 };

    printf("Array Original: ");
    exibir( numeros, 16 );

    selectionsort( numeros, 16 );

    printf("Array Ordenada: ");
    exibir( numeros, 16 );

    return 0;
}

/* fim-de-arquivo */

QUICK SORT

This is a very efficient algorithm, and on average quicksort takes O(n log n) comparisons to sort n items.

#include <stdio.h>
#include <string.h>

#define swap( _a, _b ) do{ int _tmp = _a; _a = _b; _b = _tmp; } while(0)

void quicksort( int array[], int start, int end )
{
    if( start < end )
    {
        int l = start + 1;
        int r = end;
        int p = array[start];

        while( l < r )
        {
            if( array[l] <= p )
            {
                l++;
            }
            else if( array[r] >= p )
            {
                r--;
            }
            else
            {
                swap( array[l], array[r] );
            }
        }

        if( array[l] < p )
        {
            swap( array[l], array[start] );
            l--;
        }
        else
        {
            l--;
            swap( array[l], array[start] );
        }

        quicksort( array, start, l );
        quicksort( array, r, end );
    }
}

void exibir( int array[], int tam )
{
    int i = 0;

    for( i = 0; i < tam; i++ )
        printf( "%s%d", (i>0)?", ":"", array[i] );

    printf("\n");
}


int main( int argc, char * argv[] )
{
    int numeros[16] = { 6, -9, 7, 5, 3, -1, 8, -6, 4, 2, 1, -3, -5, 9, -8, 0 };

    printf("Array Original: ");
    exibir( numeros, 16 );

    quicksort( numeros, 0, 16 );

    printf("Array Ordenada: ");
    exibir( numeros, 16 );

    return 0;
}

/* fim-de-arquivo */