this is my first time implementing a quick sort application in c# and I think it works but it does not have a way out so it keeps looping recursively can anyone help and tell me how to fix this program without destroying and rebuild technique?
and here is the code:
using System;
namespace quickso2
{
class Program
{
static void Main(string[] args)
{
int[] arr = { 12, 3, 1, 45, 16, 91, 21, 38 ,443,1212,53,2,1,0};
sort ob = new sort();
Console.WriteLine("before Sorting: ");
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i]+ " ");
}
ob.quicksorting(arr, -1, arr.Length - 1);
Console.WriteLine("\n after Sorting: ");
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i]+" " );
}
}
}
class sort
{
public int partition(int[] arr, int low, int high)
{
for (int i = low+1; i < high; i++)
{
if (arr[i] < arr[high])
{
low++;
swap(ref arr[low], ref arr[i]);
}
}
swap(ref arr[high], ref arr[low + 1]);
//displaying sorting steps
Console.WriteLine();
for (int l = 0; l < arr.Length; l++) {
Console.Write(arr[l]+" ");
}
return low + 1;
}
public void swap(ref int x, ref int y)
{
int temp = x;
x = y;
y = temp;
}
public void quicksorting(int[] arr, int low, int high)
{
int pivot ;
if (low < high)
{
pivot = partition(arr, low, high);
quicksorting(arr, -1, pivot - 1);
quicksorting(arr, pivot + 1, arr.Length - 1);
}
}
}
}
Problem was due to the array index being passed in the calls to the quick-sort function.
Causes of the problem of the infinite loop:
ob.quicksorting(arr, 0, arr.Length-1); // In main method
quicksorting(arr, -1, pivot - 1); // Recursive call #1
quicksorting(arr, pivot + 1, arr.Length - 1); // Recursive call #2
Here is the working solution, with the updated array indices:
using System;
namespace quickso2 {
public class Program {
public static void Main(string[] args) {
int[] arr = { 12, 3, 1, 45, 16, 91, 21, 38 ,443,1212,53,2,1,0};
sort ob = new sort();
Console.WriteLine("before Sorting: ");
for (int i = 0; i < arr.Length; i++) {
Console.Write(arr[i]+ " ");
}
ob.quicksorting(arr, 0, arr.Length-1);
Console.WriteLine("\n after Sorting: ");
for (int i = 0; i < arr.Length; i++) {
Console.Write(arr[i]+" " );
}
}
}
class sort {
public int partition(int[] arr, int low, int high) {
int pivot = arr[low];
while (true) {
while (arr[low] < pivot) {
low++;
}
while (arr[high] > pivot) {
high--;
}
if (low < high) {
if (arr[low] == arr[high]) return high;
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
else {
return high;
}
}
}
public void quicksorting(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
if (pivot > 1) {
quicksorting(arr, low, pivot - 1);
}
if (pivot + 1 < high) {
quicksorting(arr, pivot + 1, high);
}
}
}
}
}
Output:
before Sorting:
12 3 1 45 16 91 21 38 443 1212 53 2 1 0
after Sorting:
0 1 1 2 3 12 16 21 38 45 53 91 443 1212