Una función de tipo de conteo en C -- algorithm campo con c campo con sorting camp codereview Relacionados El problema

A counting sort function in C


5
vote

problema

Español

He intentado implementar el algoritmo de clasificación de conteo en C.

¿Qué eficiencias puedes manchar? Pedirme cerca al final cuando se ejecuta nuevamente la matriz original para asignarla la matriz ordenada. Tal vez hay una mejor manera?

  /** * Sorts array of n values. * Using counting sort O(n) */ void sort(int values[], int n) {   //set our known max length, initialize our placer array and then our sorted array   int maxLength = 65536;   int placer[maxLength];   int sorted[n];    //so we can know which indexes in our placer array are in values array   for ( int i = 0; i < n; i++ ) {     placer[ values[i] ] += 1;   }    //store the sum of previous elements in each element at each index because this will give us the sorted position   for (int i = 0; i < maxLength; i++ ) {     placer[ i + 1 ] += placer[i];   }    //fill the sorted array with the values elements using the corresponding placer index   for ( int i = 0; i < n; i++ ) {     sorted[ placer[ values[i] ] - 1 ] = values[i];     placer [ values[i] ] -= 1;    }    //set the unsorted values array to the sorted array   for (int i = 0; i < n; i++) {     values[i] = sorted[i];   } }   
Original en ingles

I've tried to implement the counting sort algorithm in C.

What efficiencies can you spot? I squint at the end when running through the original array again to assign it the sorted array. Maybe there is a better way?

/** * Sorts array of n values. * Using counting sort O(n) */ void sort(int values[], int n) {   //set our known max length, initialize our placer array and then our sorted array   int maxLength = 65536;   int placer[maxLength];   int sorted[n];    //so we can know which indexes in our placer array are in values array   for ( int i = 0; i < n; i++ ) {     placer[ values[i] ] += 1;   }    //store the sum of previous elements in each element at each index because this will give us the sorted position   for (int i = 0; i < maxLength; i++ ) {     placer[ i + 1 ] += placer[i];   }    //fill the sorted array with the values elements using the corresponding placer index   for ( int i = 0; i < n; i++ ) {     sorted[ placer[ values[i] ] - 1 ] = values[i];     placer [ values[i] ] -= 1;    }    //set the unsorted values array to the sorted array   for (int i = 0; i < n; i++) {     values[i] = sorted[i];   } } 
        

Lista de respuestas

2
 
vote
vote
La mejor respuesta
 

OFF por un error

Este bucle pasa por 1 y escribe el último elemento de matriz:

    for (int i = 0; i < maxLength; i++ ) {     placer[ i + 1 ] += placer[i];   }   

Podría detener el bucle en maxLength - 1 , o reescribe el bucle para comenzar a comenzar 1 así:

    for (int i = 1; i < maxLength; i++ ) {     placer[i] += placer[i-1];   }   

Causas variables no inicializadas Crash

Cuando ejecuí su programa, se estrelló debido a una variable no inicializada, aquí:

  int placer[maxLength];   

Más adelante, usted hace 9988776655544334 Sin haber eliminado el placer Array a ceros, para que pueda obtener valores de basura en la matriz. Puede arreglar esto borrando la matriz así:

  memset(placer, 0, sizeof(placer));   

Sin embargo, recomiendo no usar matrices de longitud variable. Una de las razones es que solo están compatibles opcionalmente en el último estándar C. La otra razón es que a veces puede desbordar su pila si asigna una gran matriz de longitud de variable. Yo usaría calloc() aquí para asignar la matriz de conteo.

Simplifique la función

Parece que está utilizando una versión del tipo de conteo que se usa para Radix Sort, que necesita mover elementos en la matriz. Para un simple tipo de conteo, no necesita hacerlo. Después de la aprobación del conteo, puede completar la matriz original con valores de los conteos, como este:

  // Uses counting sort to sort an array which contains values in the // range [0..65535].  The counting array is allocated using calloc() in // order to avoid putting a large array on the stack. void sort(int values[], int n) {     const int maxLength = 65536;     int      *counts    = calloc(maxLength, sizeof(*counts));      if (counts == NULL) {         return;     }      for (int i = 0; i < n; i++) {         counts[values[i]]++;     }      int outIndex = 0;     for (int i = 0; i < maxLength; i++) {         for (int j = 0; j < counts[i]; j++) {             values[outIndex++] = i;         }     }      free(counts); }   
 

Off by one error

This loop goes over by 1 and writes past the last array element:

  for (int i = 0; i < maxLength; i++ ) {     placer[ i + 1 ] += placer[i];   } 

You could either stop the loop at maxLength - 1, or rewrite the loop to start at 1 like this:

  for (int i = 1; i < maxLength; i++ ) {     placer[i] += placer[i-1];   } 

Uninitialized variable causes crash

When I ran your program, it crashed due to an uninitialized variable, here:

int placer[maxLength]; 

Later on, you do placer[values[i]] += 1 without ever having cleared the placer array to zeros, so you can get garbage values in the array. You can fix this by clearing the array like this:

memset(placer, 0, sizeof(placer)); 

However, I recommend not using variable length arrays. One reason is that they are only optionally supported in the latest C standard. The other reason is that sometimes you can overflow your stack if you allocate a large variable length array. I would use calloc() here to allocate the counting array.

Simplify the function

It looks like you are using a version of counting sort that is used for radix sort, which needs to move elements around in the array. For a simple counting sort, you don't need to do that. After the counting pass, you can just fill in the original array with values from the counts, like this:

// Uses counting sort to sort an array which contains values in the // range [0..65535].  The counting array is allocated using calloc() in // order to avoid putting a large array on the stack. void sort(int values[], int n) {     const int maxLength = 65536;     int      *counts    = calloc(maxLength, sizeof(*counts));      if (counts == NULL) {         return;     }      for (int i = 0; i < n; i++) {         counts[values[i]]++;     }      int outIndex = 0;     for (int i = 0; i < maxLength; i++) {         for (int j = 0; j < counts[i]; j++) {             values[outIndex++] = i;         }     }      free(counts); } 
 
 
       
       

Relacionados problema

12  Intento de un algoritmo de clasificación  ( Attempt at a sorting algorithm ) 
He estado jugando y leyendo algunos algoritmos de clasificación, y he decidido intentar escribir mi propia. Resultó ser bastante rápido (en comparación con lo...

7  Insertar ordenar en una lista vinculada  ( Insert sort on a linked list ) 
Quiero hacer un orden de inserción en una lista vinculada sin usar los nodos ficticios. Este es mi código. ¿Cómo se puede mejorar esto? Se aprecia cualquier...

0  Función de clasificación personalizada implementada como un plugin jquery  ( Custom sorting function implemented as a jquery plugin ) 
Me pidieron que creara un complemento de jQuery que ordenara los elementos DOM homogéneos en un elemento de contenedor DOM dado. Se me ocurrió la idea de ad...

7  Merge Sort en JavaScript  ( Merge sort in javascript ) 
Implementé este tipo de fusión en JS y noté que para los números de enteros aleatorios es mucho más rápido que la construcción en funciones de tipo de todos l...

6  Fusionar la implementación de ordenación en Java  ( Merge sort implementation in java ) 
¿Puedes revisar mi implementación de tipo de fusión? De todas mis pruebas, parece que funciona, pero solo quería asegurarme de que lo estoy haciendo lo mejor ...

3  Diseño de MVC para recuperar, almacenar y presentar datos de una fuente externa  ( Mvc design to fetch store and present data from an external source ) 
Hace un par de semanas Una compañía me envió este desafío de codificación: Por favor escriba una aplicación web PHP y envíela a mí como archivo zip: que...

6  Clasificación de números no repetidos aleatorios  ( Sorting random non repeating numbers ) 
Estoy trabajando en un programa en el que 10000 números no repetidos aleatorios se clasifican de forma selectiva en orden ascendente " Team | Another Team ...

9  Clasificación de visualizaciones - WinForms  ( Sorting visualizations winforms ) 
Descripción Creo que muchas personas han visto este video de Youtube "15 algoritmos de clasificación en 6 minutos" Cuando lo vi, decidí: "Puedo hacerlo m...

6  Clasificación de palabras por frecuencia  ( Sorting words by frequency ) 
Estoy haciendo una tarea simple en óxido después de leer el Libro de óxido : Lea un archivo de texto dividirlo en Whitespace desinfectar palabras elim...

1  Python Bubble Sort  ( Python bubble sort ) 
a = [5, 2, 4, 6, 1, 3] def insert(arr): if len(arr) == 1: return arr # outer loop for i in range(1, len(arr)): # inner loop ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos