ordinamento alternata - qsort

Question

Ho un programma che utilizza (e devono continuare a utilizzare) un vecchio funzione di ordinamento attuazione qsort. Devo anche fornire la funzione di ordinamento con i dati corretti per ordinare i dati sia ascendenti (se stringa contiene numero pari) o discendente (se stringa contiene numeri dispari).

I dati deve essere modificato per ottenere questo, la funzione di ordinamento non può essere modificato.

Il codice è scritto in C , ma non ho alcun frammento di codice rilevante per questo particolare problema.

La vera domanda è:

Come faccio a trasformare i dati in modo che il risultato corrisponda l'uscita desiderata qui sotto?

Non ho i seguenti dati (o simili)

String 1
String 2
String 3
String 4
String 5
String 6

EDIT:. I dati sono un certo numero di stringhe tipo char **, il numero all'interno di ogni stringa è un int

L'uscita desiderata è

String 5
String 3
String 1
String 2
String 4
String 6

Assortimento di solito è fatto in modo discendente corrispondenza dell'ingresso 1: 1. Sono riuscito a produrre una trasformazione rendendo il seguente output facendo precedere 1 o 0 per i numeri dopo la stringa.

Quindi, i dati interni da ordinare aspetto come questo

String 01
String 12
String 03
String 14
String 05
String 16

Questo produce il seguente output (trasformazione viene utilizzato solo in smistamento, ed è temporanea).

String 1
String 3
String 5
String 2
String 4
String 6

Answer 1

Si dovrebbe avere una struttura che contiene i dati, e il valore:

Struct DataValue
{
   string data;
   int value;
} 

{"01", 1} come Quindi ordinare per dati di valore e di uscita, ordinamento non è difficile se si vuole fare solite: Ordina per valore per rendere lista come quello che si mostrato. (Per valori) ora creare una matrice vuota di valori di dati (con dimensioni della matrice di base), inizia da ultimo elemento e riempirlo come qui sotto:

    int j = 0;
    for (int i = a.Count - 1; i >= 0; i -= 2) // fill bottom of list
    {
        b[a.Count - 1 - j] = a[i];
        j++;
    }

    j = 0;
    for (int i = a.Count - 2; i >= 0; i -= 2)  // fill root of list
    {
        b[j] = a[i];
        j++;
    }

Finalmente in uscita i valori.

L'ho scritto in C # non è molto diversa in c. si otterrà:

  List<int> a = new List<int>{1,2,3,4,5,6,7};

   b==> 6,4,2,1,3,5,7

and for:
  List<int> a = new List<int>{1,2,3,4,5,6};
  b==> 5,3,1,2,4,6

Answer 2

Questo può essere fatto sul posto (che è, con un singolo array di valori e di non richiedere una lista separata), utilizzando una routine di confronto personalizzato. La funzione che segue presuppone che stai smistamento direttamente le corde. E 'probabilmente meglio pre-elaborare i dati in modo da estrarre il numero dalla stringa e il luogo sia in una struttura. Ma questo vi darà l'idea.

Si potrebbe passare un puntatore a questa funzione di confronto per qsort.

int Comparer(void * v1, void * v2)
{
    char *s1 = (char *)v1;
    char *s2 = (char *)v2;

    // Here, extract the numbers from the ends of the strings.
    int n1 = // extract number
    int n2 = // extract number

    // First comparison sorts odd numbers above even numbers
    if ((n1 % 2) == 1)
    {
        // first number is odd
        if ((n2 % 2) == 1)
        {
            // second number is odd, so sort the numbers ascending
            return (n1 - n2);
        }
        else
        {
            // second number is even, which is "greater than" any odd number
            return -1;
        }
    }
    else
    {
        // first number is even
        if ((n2 % 2) == 0)
        {
            // second number is even, so sort the numbers descending
            return (n2 - n1);
        }
        else
        {
            // second number is odd, which is "less than" any even number
            return 1;
        }
    }
}

Answer 3

Prepend 9-i se i è dispari. Prepend 9 altrimenti.

Answer 4

1. Preprocessa: mettere le stringhe anche in un elenco (chiamiamolo questa lista _evens_) e mettere le stringhe dispari in un elenco separato (chiamato _odds _)
2. Ordina entrambe le liste
3. Crea un elenco di destinazione
4. Trattare la lista _odds_ come uno stack:. Pop cima _odds_ e posizionare l'elemento schioccato sulla parte anteriore * * della lista di destinazione
5. Trattare la _evens_ come una coda: pop cima alla _evens_ e posizionare l'elemento spuntato alla fine * * della lista di destinazione.