QuickSort implementation gets me an out-of-range error

I'm having some trouble with a quick sort function. Although I checked to make sure the bounds were the correct numbers when calling the method, I still get a System.ArgumentOutOfRangeException error message upon execution. Is there something within the method itself that causes it to go out of range? Or did I perhaps miss something silly? Below is a snippet of my code:
C#
static int MakePivot(List<int> mylist, int left, int right){ //for quick sort.
int pivot = mylist[right]; //pivot on the right
int cursor = mylist[left] - 1;
for(int i=left;i<right;i++){
if(mylist[i]<=pivot){
cursor++;
(mylist[cursor], mylist[i]) = (mylist[i], mylist[cursor]);
}
}
pivot = cursor + 1;
(mylist[pivot], mylist[right]) = (mylist[right], mylist[pivot]);
return pivot;
}
static void QuickSort(List<int> mylist, int left, int right){
if(left<right){
int pivot = MakePivot(mylist,left,right);
QuickSort(mylist,left,pivot-1);
QuickSort(mylist,pivot+1,right);
}
}
static void Main(string[] args){
List<int>x = MakeList("7,4,8,9,5,3,2,6"); //MakeList() takes a string of single digits and returns an integer list. Works fine.
Console.WriteLine("Before QS: ");
for(int i=0;i<x.Count;i++){
Console.Write("{0} ",x[i]);
}
QuickSort(x,0,x.Count-1);
Console.WriteLine("After QS: ");
for(int i=0;i<x.Count;i++){
Console.Write("{0} ",x[i]);
}
Console.WriteLine("");
}
C#
static int MakePivot(List<int> mylist, int left, int right){ //for quick sort.
int pivot = mylist[right]; //pivot on the right
int cursor = mylist[left] - 1;
for(int i=left;i<right;i++){
if(mylist[i]<=pivot){
cursor++;
(mylist[cursor], mylist[i]) = (mylist[i], mylist[cursor]);
}
}
pivot = cursor + 1;
(mylist[pivot], mylist[right]) = (mylist[right], mylist[pivot]);
return pivot;
}
static void QuickSort(List<int> mylist, int left, int right){
if(left<right){
int pivot = MakePivot(mylist,left,right);
QuickSort(mylist,left,pivot-1);
QuickSort(mylist,pivot+1,right);
}
}
static void Main(string[] args){
List<int>x = MakeList("7,4,8,9,5,3,2,6"); //MakeList() takes a string of single digits and returns an integer list. Works fine.
Console.WriteLine("Before QS: ");
for(int i=0;i<x.Count;i++){
Console.Write("{0} ",x[i]);
}
QuickSort(x,0,x.Count-1);
Console.WriteLine("After QS: ");
for(int i=0;i<x.Count;i++){
Console.Write("{0} ",x[i]);
}
Console.WriteLine("");
}
No description
18 Replies
springblitz
springblitzOP2w ago
Please ping me if you have anything to say.
hime
hime2w ago
you should be debugging it, not running the exe directly
springblitz
springblitzOP2w ago
VS Code is being weird and not letting me do the debug pack for C# The test file is just me isolating parts of the code so I can see what's wrong with it, and it turns out the QuickSort stuff is the problem.
hime
hime2w ago
Is there a reason you're using vs code and not visual studio?
springblitz
springblitzOP2w ago
Force of habit. Whoops.
hime
hime2w ago
I mean, sometimes it's cause tutorials use it, but it's not recommended for beginners Plug and play to debug it, vs setting it up None of those things you need to know immediately, sometimes even kills your motivation to learn
springblitz
springblitzOP2w ago
I was taught in schools to just run the stuff in terminal anyway so I didn't think it'd be that much of an issue til now :catshrug:
hime
hime2w ago
Your error is very clear, your index ended up negative And I see a -1 without checking if we're already at 0 That's only cause they don't know jack shit I've found only 1 teacher in my lifetime who knows how to use a debugger Imagine, they code in visual studio, then compile in the terminal instead of hitting run
springblitz
springblitzOP2w ago
They'd rather use Notepad++ or Vim than the VS stuff. anyway, I thought that putting cursor++ before doing the swapping stuff would keep the negative index from happening, as it did when I had implemented it in other languages like C++ and Java
hime
hime2w ago
There's actually a glaring mistake there regarding how you set your cursor position Debugging would have shown you this because you can actually see the values you have
springblitz
springblitzOP2w ago
Ah. Time to figure out how to debug in Visual Studio, then, because I have no idea how to use this lol google don't fail me now
hime
hime2w ago
A tutorial can get you mostly there, debugging is very trivial on how to get it working In VS at least, debugger and running the code is already just one click Set a breakpoint and code stops there
Angius
Angius2w ago
$debug
MODiX
MODiX2w ago
Tutorial: Debug C# code and inspect data - Visual Studio (Windows)
Learn features of the Visual Studio debugger and how to start the debugger, step through code, and inspect data in a C# application.
springblitz
springblitzOP2w ago
👍 fixed the error. now to fix the rest of the code because there's still some other problems apparently-
yourFriend
yourFriend2w ago
https://youtu.be/y-GNaO6OhdM?si=w5dHQkexUnS2HoUV I agree that debugging in VS Code is little weird. This is what I do. Making video on how to debug in VS Code took me more time than actually debugging the code.
yourFriend
yourFriend2w ago
Everything is alright at least for me. The problem was in MakePivot() method. I think it was mixing values with there index. I completely rewrote the method MakePivot(). Here's the whole program for reference: https://paste.mod.gg/ppikrzcciypc/0 Followed the algorithm mentioned in wikipedia: https://en.wikipedia.org/wiki/Quicksort This image sums the whole algorithm: https://en.wikipedia.org/wiki/File:Quicksort-diagram.svg
BlazeBin - ppikrzcciypc
A tool for sharing your source code with the world!
Quicksort
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions. Quicksort is a divi...
Anton
Anton2w ago
use spans, it's so much easier with them

Did you find this page helpful?