Imprima una array de strings en orden ordenado sin copiar una string en otra

Dada una array de n strings. La tarea es imprimir las strings en orden ordenado. El enfoque debe ser tal que ninguna string se copie a otra string durante el proceso de clasificación.

Ejemplos:

Input : {"geeks", "for", "geeks", "quiz")
Output : for geeks geeks quiz

Input : {"ball", "pen", "apple", "kite"}
Output : apple ball kite pen

Planteamiento: Tiene los siguientes pasos: 

1. Mantenga otra array indexed_arr que almacena/mantiene el índice de cada string.
2. Podemos aplicar cualquier técnica de clasificación a este indexed_arr .

Una ilustración:  

--> str[] = {"world", "hello"}
--> corresponding index array will be
    indexed_arr = {0, 1}
--> Now, how the strings are compared and 
    accordingly values in indexed_arr are changed.
--> Comparison process:
    if (str[index[0]].compare(str[index[1]] > 0
        temp = index[0]
        index[0] = index[1]
        index[1] = temp

// after sorting values of
// indexed_arr = {1, 0}
--> for i=0 to 1
        print str[index[i]]

This is how the strings are compared and their 
corresponding indexes in the indexed_arr
are being manipulated/swapped so that after the sorting process
is completed, the order of indexes in the indexed_arr
gives us the sorted order of the strings.

Implementación:

// C++ implementation to print array of strings in sorted
// order without copying one string into another
#include <bits/stdc++.h>
 
using namespace std;
 
// function to print strings in sorted order
void printInSortedOrder(string arr[], int n)
{
    int index[n];
    int i, j, min;
     
    // Initially the index of the strings
    // are assigned to the 'index[]'
    for (i=0; i<n; i++)
        index[i] = i;
     
    // selection sort technique is applied   
    for (i=0; i<n-1; i++)   
    {
        min = i;
        for (j=i+1; j<n; j++)
        {
            // with the help of 'index[]'
            // strings are being compared
            if (arr[index[min]].compare(arr[index[j]]) > 0)
                min = j;
        }
         
        // index of the smallest string is placed
        // at the ith index of 'index[]'
        if (min != i)
        {
            int temp = index[min];
            index[min] = index[i];
            index[i] = temp;
        }
    }
     
    // printing strings in sorted order
    for (i=0; i<n; i++)
        cout << arr[index[i]] << " ";
}
 
// Driver program to test above
int main()
{
    string arr[] = {"geeks", "quiz", "geeks", "for"};
    int n = 4;
    printInSortedOrder(arr, n);
    return 0;
}

//Java implementation to print array of strings in sorted
// order without copying one string into another
 
class GFG {
 
    // function to print strings in sorted order
    static void printInSortedOrder(String arr[], int n) {
        int index[] = new int[n];
        int i, j, min;
 
        // Initially the index of the strings
        // are assigned to the 'index[]'
        for (i = 0; i < n; i++) {
            index[i] = i;
        }
 
        // selection sort technique is applied   
        for (i = 0; i < n - 1; i++) {
            min = i;
            for (j = i + 1; j < n; j++) {
                // with the help of 'index[]'
                // strings are being compared
                if (arr[index[min]].compareTo(arr[index[j]]) > 0) {
                    min = j;
                }
            }
 
            // index of the smallest string is placed
            // at the ith index of 'index[]'
            if (min != i) {
                int temp = index[min];
                index[min] = index[i];
                index[i] = temp;
            }
        }
 
        // printing strings in sorted order
        for (i = 0; i < n; i++) {
            System.out.print(arr[index[i]] + " ");
        }
    }
 
    // Driver program to test above
    static public void main(String[] args) {
        String arr[] = {"geeks", "quiz", "geeks", "for"};
        int n = 4;
        printInSortedOrder(arr, n);
    }
}
 
// This code is contributed by 29AjayKumar

# Python 3 implementation to print array
# of strings in sorted order without
# copying one string into another
 
# function to print strings in sorted order
def printInSortedOrder(arr, n):
    index = [0] * n
     
    # Initially the index of the strings
    # are assigned to the 'index[]'
    for i in range(n):
        index[i] = i
     
    # selection sort technique is applied
    for i in range(n - 1):
        min = i
        for j in range(i + 1, n):
             
            # with the help of 'index[]'
            # strings are being compared
            if (arr[index[min]] > arr[index[j]]):
                min = j
         
        # index of the smallest string is placed
        # at the ith index of 'index[]'
        if (min != i):
            index[min], index[i] = index[i], index[min]
     
    # printing strings in sorted order
    for i in range(n):
        print(arr[index[i]], end = " ")
 
# Driver Code
if __name__ == "__main__":
     
    arr = ["geeks", "quiz", "geeks", "for"]
    n = 4
    printInSortedOrder(arr, n)
 
# This code is contributed by ita_c

     
//C# implementation to print an array of strings in sorted
// order without copying one string into another
 using System;
public class GFG {
  
    // function to print strings in sorted order
    static void printInSortedOrder(String []arr, int n) {
        int []index = new int[n];
        int i, j, min;
  
        // Initially the index of the strings
        // are assigned to the 'index[]'
        for (i = 0; i < n; i++) {
            index[i] = i;
        }
  
        // selection sort technique is applied   
        for (i = 0; i < n - 1; i++) {
            min = i;
            for (j = i + 1; j < n; j++) {
                // with the help of 'index[]'
                // strings are being compared
                if (arr[index[min]].CompareTo(arr[index[j]]) > 0) {
                    min = j;
                }
            }
  
            // index of the smallest string is placed
            // at the ith index of 'index[]'
            if (min != i) {
                int temp = index[min];
                index[min] = index[i];
                index[i] = temp;
            }
        }
  
        // printing strings in sorted order
        for (i = 0; i < n; i++) {
            Console.Write(arr[index[i]] + " ");
        }
    }
  
    // Driver program to test above
    static public void Main() {
        String []arr = {"geeks", "quiz", "geeks", "for"};
        int n = 4;
        printInSortedOrder(arr, n);
    }
}
  
// This code is contributed by 29AjayKumar

<script>
//Javascript implementation to print array of strings in sorted
// order without copying one string into another
     
    // function to print strings in sorted order
    function printInSortedOrder(arr,n)
    {
        let index = new Array(n);
        let i, j, min;
   
        // Initially the index of the strings
        // are assigned to the 'index[]'
        for (i = 0; i < n; i++) {
            index[i] = i;
        }
   
        // selection sort technique is applied   
        for (i = 0; i < n - 1; i++) {
            min = i;
            for (j = i + 1; j < n; j++) {
                // with the help of 'index[]'
                // strings are being compared
                if (arr[index[min]]>(arr[index[j]]) ) {
                    min = j;
                }
            }
   
            // index of the smallest string is placed
            // at the ith index of 'index[]'
            if (min != i) {
                let temp = index[min];
                index[min] = index[i];
                index[i] = temp;
            }
        }
   
        // printing strings in sorted order
        for (i = 0; i < n; i++) {
            document.write(arr[index[i]] + " ");
        }
    }
     
    // Driver program to test above
    let arr=["geeks", "quiz", "geeks", "for"];
    let n = 4;
    printInSortedOrder(arr, n);
     
    // This code is contributed by avanitrachhadiya2155
</script>

for geeks geeks quiz 

Complejidad Temporal: O(n ² ).
Espacio Auxiliar: O(n).

El enfoque puede tener su uso cuando tenemos que minimizar el número de escrituras de disco como en el caso de una array de estructuras. Los valores de la estructura se comparan, pero sus valores no se intercambian, sino que su índice se mantiene en otra array, que se manipula para mantener los índices en un orden que representa la array ordenada de estructuras.