Here's my quicksort working on a List, it's supposed to read from a large .txt file containing one number per line. After filling up the List from the file I tried to sort it, but for some reason it's taking way too long.
// Main.cs
List<int> myList = new List<int>();
string[] lines = System.IO.File.ReadAllLines("largeFile.txt");
foreach (string num in lines)
myList.Add(int.Parse(num));
QuickSort(ref myList, 0, myList.Count - 1);
quick.cs:
static void Swap(List<int> myList, int indexA, int indexB)
{
int tmp = myList[indexA];
myList[indexA] = myList[indexB];
myList[indexB] = tmp;
}
static int Partition(ref List<int> myList, int leftIdx, int rightIdx)
{
int pivot = leftIdx - 1;
for (int i = leftIdx; i < rightIdx; ++i)
{
if (myList[i] < myList[rightIdx])
{
++pivot;
Swap(myList, pivot, i);
}
}
++pivot;
Swap(myList, pivot, rightIdx);
return pivot;
}
static void QuickSort(ref List<int> myList, int leftIdx, int rightIdx)
{
if (rightIdx <= leftIdx)
return;
int pivotIdx = Partition(ref myList, leftIdx, rightIdx);
QuickSort(ref myList, leftIdx, pivotIdx - 1);
QuickSort(ref myList, pivotIdx + 1, rightIdx);
return;
}
Compared to List.Sort() (which sorts it almost immediately) this is ridiculously slow, how can I improve this? For instance List.Sort takes 3 milliseconds while my method takes 14769
Example code for classic Lomuto partition scheme. It swaps middle element with last element which is then used as the pivot. Recurse on smaller, loop on larger reduces stack space to O(log(n)), but worst case time complexity remains at O(n^2).
static public void QuickSort(int [] a, int lo, int hi)
{
while (lo < hi){
int t;
int p = a[(lo+hi)/2]; // use mid point for pivot
a[(lo+hi)/2]= a[hi]; // swap with a[hi]
a[hi] = p;
int i = lo;
for (int j = lo; j < hi; ++j){ // Lomuto partition
if (a[j] < p){ // if a[j] < pivot
t = a[i]; // swap a[i], a[j]
a[i] = a[j];
a[j] = t;
++i; // i += 1
}
}
t = a[i]; // swap a[i], a[hi]
a[i] = a[hi]; // to put pivot in place
a[hi] = t;
if(i - lo <= hi - i){ // recurse on smaller partiton
QuickSort(a, lo, i-1); // loop on larger
lo = i+1;
} else {
QuickSort(a, i+1, hi);
hi = i-1;
}
}
}