Insertion Sort on a String Array

Question

I am having trouble applying the insertion sort algorithm to the string because it. I have been getting various errors which I think are from issues regarding strings vs char types.

Ex:

candidate template ignored: could not match 'stack' against 'basic_string'
operator> (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)

The insertion sort algorithm was pulled from geeks for geeks but I just changed it to string array.

void insertionSort(string arr[], int n)
{
    int i, key, j, unsortedness;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;
        
        /* Move elements of arr[0..i-1], that are  
         greater than key, to one position ahead  
         of their current position */
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
    
        }
        
        arr[j + 1] = key;
    }
}

int main()
{
    
    //Read in from file stuff missing to save space
    
    int d, lengthStrings, numberStrings; // D will hold the number of data sets
    infile >> d;
    cout << d << endl;
    while (d != 0)
    {
        infile >> lengthStrings;
        infile >> numberStrings;
        int numCopy = numberStrings;
        
        int i = 0;
        string arrayDna[numberStrings]; //char arrayDna[numberStrings][lengthStrings] instead?;
        
        while (numberStrings != 0)
        {
            infile >> arrayDna[i];
            i++;
            numberStrings--;
        }
        
        insertionSort(arrayDna[], numCopy);

        for (int i = 0; i < numCopy; i++)
            cout << arrayDna[i] << "\n";
        
        d--;

So basically I need help fixing the error not allowing me to apply this insertion algorithm to my own string array.

What makes you think that insertion sort is well-suited to this task? — Beta, Jul 22 '20 at 16:24
Before you can *sort* a set of things, you must be able to *compare* two things. Since you want to sort things by "measure" or "unsortedness", you must write code that calculates the measure of a sequence. Once you have that, you can modify this insertion sort to compare the measures of two things, instead of comparing the things themselves. — Beta, Jul 22 '20 at 16:30
I was planning on adding the level of unsortedness element inside of the insertion function. Would that not work? — 101001, Jul 22 '20 at 16:33
@101001 -- You are going about this the wrong way. As Beta mentioned, if you can't logically figure out what makes one string less than another, then the sorting code can't exist, regardless of what type of sort you are trying to do. — PaulMcKenzie, Jul 22 '20 at 16:35
It could work, but it reduces the re-usability of the insertion algorithm and the comparison algorithm. If you keep the two separate you can easily reuse either piece of code. — user4581301, Jul 22 '20 at 16:36
[See this link, and look at Insertion Sort](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). Do you see the last parameter of the template and to the function itself? That is the sorting criteria. That's how you separate algorithm from the sort criteria. You insertion sort code shouldn't have a single `<` or `>` hard-coded. It should be a function that returns `true` or `false` depending on the two items being tested. — PaulMcKenzie, Jul 22 '20 at 16:38
Plus combining the two means you have to debug two algorithms at the same time. This sounds twice as hard, but it's not. Often it goes exponential. Keep things small and simple and separately testable, then assemble like Lego blocks. — user4581301, Jul 22 '20 at 16:39

Sai Sreenivas · Answer 1 · 2020-07-22T16:53:40.430

I didn't work on the logic, but cleared all the basic errors, hopefully:)

changes:

(1) arrayDna[] => arrayDna (in the parameters) while invoking insertionSort function.

(2) In the insertionSort function at line : key = arr[i],

key is an int type but needed string type, so changed type of key to string from int

void insertionSort(string arr[], int n)  
 {  
int i,j, unsortedness;  
string key;
for (i = 1; i < n; i++) 
{  
    key = arr[i];  
    j = i - 1;  

    /* Move elements of arr[0..i-1], that are  
    greater than key, to one position ahead  
    of their current position */
    while (j >= 0 && arr[j] > key) 
    {  
        arr[j + 1] = arr[j];  
        j = j - 1;
    // Since I just need to find unsortedness and not actually sort 
    //I should probably just replace the two lines with something such as  
    //unsortedness++ and compare that way
    }  

    arr[j + 1] = key;  
   }  
 }  



 int main(){

 //Read in from file stuff missing to save space

int d,lengthStrings, numberStrings;     // D will hold the number of data sets
infile >> d;
cout << d << endl;
while(d !=0){
    infile >> lengthStrings;
    infile >> numberStrings;
    int numCopy=numberStrings;

    int i=0;
    string arrayDna [numberStrings]; //char arrayDna[numberStrings][lengthStrings] instead?;
    


    while(numberStrings != 0){
        infile >> arrayDna[i];
        i++;
        numberStrings--;
    }
    
    insertionSort(arrayDna, numCopy);

 for (int i = 0; i < numCopy; i++) 
        cout << arrayDna[i] << "\n";

    
    d--;
    }
  }

The code is a jumbled mess, but the important part of the question IS the hole in the logic. If you do not address this hole, the answer is not overly useful. — user4581301, Jul 22 '20 at 16:35
Thank you Sai, I just needed to figure why I couldn't apply it to my string array. It now sorts it in order. I'll go and figure out how to sort based on unsortedness now. Ty — 101001, Jul 22 '20 at 16:39
Looks like I overthought the question that was being asked. One request: Highlight the changes you made and where it seems necessary, explain the change. — user4581301, Jul 22 '20 at 16:45

Insertion Sort on a String Array

1 Answers1