DataGridView Multiple Selection problem

Hi, I'm using a DGV to show a lot of Database entries and I would like to allow the user to select multiple rows and then perform actions on those rows. The problem is, since the DGVs multiselect option allows any kind of selection (shift, ctrl, top-to-bottom, bottom-to-top) the resulting .SelectedRows could be a set of non-contiguous rows. Even worst, the order of the .SelectedRows set is the order in which those rows where selected, so the resulting set of rows could be a real mess!

This affects Database access tremendously, since instead of just doing a SELECT between this and that date, I have to cycle through every row individually, since I don't know the first date, or the last date, or if there are "holes" in the middle. It took like a minute to modify 800 records... (I'm pretty sure this was also affected by the fact VS was Console.Writelining a lot too)

I could perform a search and order the .SelectedRows into small sets of contiguous elements and then perform the smallest amount of database queries, but is there any other way?
FYI, I have no SPs in my DB, I do absolutely everything SQLCommand related stuff from within mi C# app using preformated methods and a Dictionary<key, value> for the table's data, so I can pretty much do anything with it.

Code:

---

// DataGridViewSelectedRowCollection has no 'ordering' methods
DataGridViewSelectedRowCollection userSelectedRows = this.dgvHistory.SelectedRows;
 
foreach (DataGridViewRow row in userSelectedRows)
{
    row.Cells["Valid"].Value = newValidityState;
    DateTime rowDate = DateTime.Parse((string)row.Cells["Date"].Value);

    // Database actions here for every 'row'
}

// Instead of Database actions here for all 'userSelectedRows'

---

Thank you very much for any suggestions!