How do I avoid two sentences with the same first letter being beside each other in a shuffle?

Question

I have a code that I've written which shuffles a text file of music tracks, how do I adapt my code so that each time I run the program, there won't be two tracks beside each other that start with the same first letter. For example, two tracks by the artists Hozier shouldn't be beside each other.

Correct:

Hozier - Take Me To Church
Pink - So What
Hozier - Cherry Wine

Incorrect:

Hozier - Take Me To Church
Hozier - Cherry Wine
Pink - So What

Here's my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// Accepts: command line input
// Returns: 0 if no error

int main(int num_args, char *arg_strings[])
{
    int x = 0, i, track_count = 0;
    unsigned long Max_Length = 0;
char line[500], *temp;
FILE *file = fopen("InputFiles/playlist.txt", "r" );
/* The next line checks if the playlist file exists and if it's not there, "Cannot Open File" is printed to the screen */
if (file == NULL){
    printf("Cannot open file\n");

}
/* The following code identifies each line in the text and lines are shuffled accordingly */

while (fgets(line, sizeof(line), file) != NULL)
{
    track_count++;
    if (strlen(line) > Max_Length)
        Max_Length = strlen(line);
}
rewind(file);
char *Array[track_count];
while (fgets(line, sizeof(line), file) != NULL)
{
    Array[x] = malloc(strlen(line));
    if (Array[x] == NULL){
        printf("A memory error occurred.\n");
        return(1);
    }
    strcpy(Array[x], line);
    /* change \n to \0 */
            Array[x][strlen(Array[x])-1] = '\0';
            x++;
        }

    printf("The original playlist is:\n");
    for (x = 0; x < track_count; x++)
    printf("%2d %s\n", x, Array[x]);
/*  The array will now be shuffled: */
srand( (unsigned int) time(NULL));
for (x = track_count - 1; x >= 0; x--){
    i = (int) rand() % track_count;
    temp = Array[x];
    Array[x] = Array[i];
    Array[i] = temp;
}
printf("\nShuffled Array\n");
for (x = 0; x < track_count; x++)
    printf("%2d %s\n", x, Array[x]);

return 0;
}

Answer 1

If repetitions of the same song were allowed (e.g., as when a music player is on both shuffle and repeat), you could just remember the previous first letter and pick each successive song randomly out of those that do not have the same first letter as the previous song.

However, for shuffling the songs without repetitions, considering only the last position does not work, e.g., if your songs had the first letters C A C B C A C, they could end up as A B A C C C C where you only have C-songs remaining at the end. You could detect this situation (i.e., number of unshuffled songs not beginning with the previous first letter is zero) and in those cases find the positions in the previously sorted list into which each new song can be inserted, and pick randomly from those. For example, if you had the above first letters and were at A B A C, then the next song beginning with C could be inserted into 3 different positions (C A B A C, A C B A C, or A B C A C).