This is a homework project.
My goal is to sort my list of animals in alphabetical order by name by implementing a quick sort using recursion. I've accomplished this successfully with my animals weights as demonstrated below with a snippet of the code and my results that are associated with it.
public static SortResult QuickSortByWeight(List<Animal> animals, int leftIndex, int rightIndex, SortResult sortResult)
{
// define variables to keep track of the left and right points in the list
// initialize them to the passed-in indexes
int leftPointer = leftIndex;
int rightPointer = rightIndex;
// find the animal to pivot on (the middle animal in this case)
Animal pivotAnimal = animals[(leftIndex + rightIndex) / 2];
// define and initialize a loop variable
bool done = false;
// start looping
while (!done)
{
// while the weight of the animal at the left pointer spot in the list is less than the pivot animal's weight
while (animals[leftPointer].Weight < pivotAnimal.Weight)
{
// increment the left pointer
leftPointer++;
// increment the sort result's compare count
sortResult.CompareCount++;
}
// while the pivot animal's weight is less than the weight of the animal at the right pointer spot in the list
while (pivotAnimal.Weight < animals[rightPointer].Weight)
{
// decrement the right pointer
rightPointer--;
// increment the sort result's compare count
sortResult.CompareCount++;
}
// if the left pointer is less than or equal to the right pointer
if (leftPointer <= rightPointer)
{
// swap the animals at the left pointer and right pointer spots
SortHelper.Swap(animals, leftPointer, rightPointer);
// increment the sort result's swap count
sortResult.SwapCount++;
// then increment the left pointer and decrement the right pointer
leftPointer++;
rightPointer--;
}
// if the left pointer is greater than the right pointer,
// stop the outer while loop
if (leftPointer > rightPointer)
{
done = true;
}
}
// if the left index is less than the right pointer
// use recursion to sort the animals within the left index and right pointer
if (leftIndex < rightPointer)
{
// method call here
QuickSortByWeight(animals, leftIndex, rightPointer, sortResult);
}
//// if the left pointer is less than the right index
//// use recursion to sort the animals within the left pointer and right index
if (leftPointer < rightIndex)
{
// method call here
QuickSortByWeight(animals, leftPointer, rightIndex, sortResult);
}
sortResult.Animals = animals;
return new SortResult { SwapCount = sortResult.SwapCount, CompareCount = sortResult.CompareCount, ElapsedMilliseconds = sortResult.ElapsedMilliseconds, Animals = animals };
}
I thought when quickSorting by name I could use .CompareTo with my current animals name along with the same logic behind sorting by weight, however I've been unsuccessful in doing so with a IndexOutOfRange exception using the following code:
public static SortResult QuickSortByName(List<Animal> animals, int leftIndex, int rightIndex, SortResult sortResult)
{
// define variables to keep track of the left and right points in the list
// initialize them to the passed-in indexes
int leftPointer = leftIndex;
int rightPointer = rightIndex;
// find the animal to pivot on (the middle animal in this case)
Animal pivotAnimal = animals[(leftIndex + rightIndex) / 2];
// define and initialize a loop variable
bool done = false;
// start looping
while (!done)
{
// while the name of the animal at the left pointer spot in the list is less than the pivot animal's name
while (animals[leftPointer].Name.CompareTo(pivotAnimal.Name) < leftPointer)
{
// increment the left pointer
leftPointer++;
// increment the sort result's compare count
sortResult.CompareCount++;
}
// while the pivot animal's name is less than the name of the animal at the right pointer spot in the list
while (pivotAnimal.Name.CompareTo(animals[rightPointer].Name) < rightPointer)
{
// decrement the right pointer
rightPointer--;
// increment the sort result's compare count
sortResult.CompareCount++;
}
// if the left pointer is less than or equal to the right pointer
if (leftPointer <= rightPointer)
{
// swap the animals at the left pointer and right pointer spots
SortHelper.Swap(animals, leftPointer, rightPointer);
// increment the sort result's swap count
sortResult.SwapCount++;
// then increment the left pointer and decrement the right pointer
leftPointer++;
rightPointer--;
}
// if the left pointer is greater than the right pointer,
// stop the outer while loop
if (leftPointer > rightPointer)
{
done = true;
}
}
// if the left index is less than the right pointer
// use recursion to sort the animals within the left index and right pointer
if (leftIndex < rightPointer)
{
// method call here
QuickSortByName(animals, leftIndex, rightPointer, sortResult);
}
//// if the left pointer is less than the right index
//// use recursion to sort the animals within the left pointer and right index
if (leftPointer < rightIndex)
{
// method call here
QuickSortByName(animals, leftPointer, rightIndex, sortResult);
}
sortResult.Animals = animals;
return new SortResult { SwapCount = sortResult.SwapCount, CompareCount = sortResult.CompareCount, ElapsedMilliseconds = sortResult.ElapsedMilliseconds, Animals = animals };
}
If I can come out of this discussion understanding why my syntax is wrong for sorting by name I'm thankful for the insight.
