My first run ended in a stalemate situation in sector 6 after I ran out of fuel. I encountered the flagship for the first time within my first three attempts, iirc. My ninth attempt was the one in which I finally beat the flagship.
Mind you, I had played as the other ships and on Easy difficulty before beating the game, but that was just to unlock stuff. I believe I actually quit after getting to the flagship a few times because I wasn't playing on Normal and as the Kestrel A, and thus, refused to win.

So nine, counting only the runs in which I was playing in earnest.