Print array of strings in sorted order without copying one string into another
Given an array of n strings. The task is to print the strings in sorted order. The approach should be such that no string should be copied to another string during sorting process.
Examples:
Input : {"geeks", "for", "geeks", "quiz") Output : for geeks geeks quiz Input : {"ball", "pen", "apple", "kite"} Output : apple ball kite pen
Approach: It has the following steps:
 Maintain another array indexed_arr which stores/maintains the index of each string.
 We can apply any sorting technique to this indexed_arr.
An Illustration:
> 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.

// 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<n1; 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[] = {
"tech"
,
"code"
,
"tech"
,
"bit"
};
int
n = 4;
printInSortedOrder(arr, n);
return
0;
}
Output:
bit tech
tech
code
Time Complexity: O(n^{2})
The approach can have its usage when we have to minimize the number of disc writesas in the case of array of structures. The structure values are compared but their values are not being swapped, instead their index is maintained in another array, which is manipulated so as keep the indexes in an order which represents the sorted array of structures.
Exercise: Apply this approach with the help of other sorting techniques like merge sort, insertion sort, etc.
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/printarraystringssortedorderwithoutcopyingonestringanother/
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide