20

I found quicksort algorithm from this book

This is the algorithm

QUICKSORT (A, p, r)
if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q-1)
    QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
x=A[r]
i=p-1
for j = p to r - 1
  if A <= x
     i = i + 1
     exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1

And I made this c# code:

private void quicksort(int[] input, int low, int high)
{
    int pivot_loc = 0;

    if (low < high)
        pivot_loc = partition(input, low, high);
    quicksort(input, low, pivot_loc - 1);
    quicksort(input, pivot_loc + 1, high);
}

private int partition(int[] input, int low, int high)
{
    int pivot = input[high];
    int i = low - 1;

    for (int j = low; j < high-1; j++)
    {
        if (input[j] <= pivot)
        {
            i++;
            swap(input, i, j);
        }
    }
    swap(input, i + 1, high);
    return i + 1;
}



private void swap(int[] ar, int a, int b)
{
    temp = ar[a];
    ar[a] = ar[b];
    ar[b] = temp;
}

private void print(int[] output, TextBox tbOutput)
{
    tbOutput.Clear();
    for (int a = 0; a < output.Length; a++)
    {
        tbOutput.Text += output[a] + " ";
    }
}

When I call function like this quicksort(arr,0,arr.Length-1); I get this error An unhandled exception of type 'System.StackOverflowException' occurred it pass empty array... when call function like this quicksort(arr,0,arr.Length); I get error Index was outside the bounds of the array. on this line int pivot = input[high]; but array passed successfully.

I also want to print it like this print(input,tbQuick); but where to place it so it would print when quicksort finished?

Improve this question
4
  • I do not understand the last part of the question - the print thing - as your code doesn't show the bit where you're actually calling quicksort. Why not just print as the next statement after calling quicksort? Commented Nov 30, 2012 at 15:41
  • 1
    Because my code had infinitive loop so I didn't know here to put the print to print once... Now is ok.. Commented Nov 30, 2012 at 15:44
  • Just wrap the recursive function in another function to print it when it is done sorting. Commented Nov 30, 2012 at 15:45
  • Question has been protected, due to it attracting numerous answers which are simply copies of Quicksort implementations, rather than actually answering the question. Commented May 16, 2020 at 22:21

7 Answers 7

Reset to default
25

You did not properly implement the base case termination, which causes quicksort to never stop recursing into itself with sublists of length 0.

Change this:

if (low < high)
    pivot_loc = partition(input, low, high);
quicksort(input, low, pivot_loc - 1);
quicksort(input, pivot_loc + 1, high);

to this:

if (low < high) {
    pivot_loc = partition(input, low, high);
    quicksort(input, low, pivot_loc - 1);
    quicksort(input, pivot_loc + 1, high);
}
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

actually i get first time code from here algorithmist.com/index.php/Quicksort and then checked book and it was almost same... didnt see
16

In addition to Deestan's answer, you also have this wrong:

for (int j = low; j < high-1; j++)

It should be:

for (int j = low; j < high; j++)
Improve this answer

5 Comments

but you right... It was giving me wrong result after change it to high it worked... I didn't know books have errors o_0
This is 2way or 3way quicksort?
standard 2 way -- you sub-divide the partition into 2 more partitions on each recursive sort.
Ok thanks I wanted to confirm it.. I couldn't find anywhere good 3-way quicksort algorithm... Do you know how to do it or you know where i can find?
Book does not have error, if you are using high-1, you should have used <= so your statement be for (int j = low; j <= high-1; j++)
2

This is the shortest implementation of Quick Sort algorithm (Without StackOverflowException)

IEnumerable<T> QuickSort<T>(IEnumerable<T> i) where T :IComparable
{
    if (!i.Any()) return i;
    var p = i.ElementAt(new Random().Next(0, i.Count() - 1));
    return QuickSort(i.Where(x => x.CompareTo(p) < 0)).Concat(i.Where(x => x.CompareTo(p) == 0)).Concat(QuickSort(i.Where(x => x.CompareTo(p) > 0)));
}
Improve this answer

1 Comment

The question asked was about the StackOverflowException in the author's code. This answer does not in any way address that question.
1

Just in case you want some shorter code for Quicksort:

    IEnumerable<int> QuickSort(IEnumerable<int> i)
    {
        if (!i.Any())
            return i;
        var p = (i.First() + i.Last) / 2 //whichever pivot method you choose
        return QuickSort(i.Where(x => x < p)).Concat(i.Where(x => x == p).Concat(QuickSort(i.Where(x => x > p))));
    }

Get p (pivot) with whatever method is suitable of course.

Improve this answer

4 Comments

You are misusing Random. Either pass in a Random parameter into the QuickSort function or refer to a single instance outside of the method's scope. Initialization reseeds the object, which can result in not-so-random results if executed very quickly.
As mentioned 'p' can be obtained with whatever method is most appropriate - it's the method size I'm demonstrating for here, but yes your points regarding random are correct.
The question asked was about the StackOverflowException in the author's code. This answer does not in any way address that question.
It doesn't - but many refer to this "Implementing quicksort algorithm" question when viewing different implementations. It depends whether you limit yourself to a specific set of rules, or allow the page to continue to successfully act as a learning resource for many.
0

A Simple Quick Sort Implementation.

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/QuickSort.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgorithmsMadeEasy
{
    class QuickSort
    {
        public void QuickSortMethod()
        {
            var input = System.Console.ReadLine();
            string[] sInput = input.Split(' ');
            int[] iInput = Array.ConvertAll(sInput, int.Parse);

            QuickSortNow(iInput, 0, iInput.Length - 1);

            for (int i = 0; i < iInput.Length; i++)
            {
                Console.Write(iInput[i] + " ");
            }

            Console.ReadLine();
        }

        public static void QuickSortNow(int[] iInput, int start, int end)
        {
            if (start < end)
            {
                int pivot = Partition(iInput, start, end);
                QuickSortNow(iInput, start, pivot - 1);
                QuickSortNow(iInput, pivot + 1, end);
            }
        }

        public static int Partition(int[] iInput, int start, int end)
        {
            int pivot = iInput[end];
            int pIndex = start;

            for (int i = start; i < end; i++)
            {
                if (iInput[i] <= pivot)
                {
                    int temp = iInput[i];
                    iInput[i] = iInput[pIndex];
                    iInput[pIndex] = temp;
                    pIndex++;
                }
            }

            int anotherTemp = iInput[pIndex];
            iInput[pIndex] = iInput[end];
            iInput[end] = anotherTemp;
            return pIndex;
        }
    }
}

/*
Sample Input:
6 5 3 2 8

Calling Code:
QuickSort qs = new QuickSort();
qs.QuickSortMethod();
*/
Improve this answer

1 Comment

The question asked was about the StackOverflowException in the author's code. This answer does not in any way address that question.
0 
Code Implemented with Iteration With last element as Pivot
<code>https://jsfiddle.net/zishanshaikh/5zxvwoq0/3/    </code>

function quickSort(arr,l,u) {
 if(l>=u)
 {
  return;
 }


var pivot=arr[u];
var pivotCounter=l;
for(let i=l;i<u;i++)
{
    if(arr[i] <pivot )
    {
      var temp= arr[pivotCounter];
      arr[pivotCounter]=arr[i] ;
      arr[i]=temp;
      pivotCounter++;
    }
}


var temp2= arr[pivotCounter];
      arr[pivotCounter]=arr[u] ;
      arr[u]=temp2;


quickSort(arr,pivotCounter+1,u);
quickSort(arr,0,pivotCounter-1);



}

<code>https://jsfiddle.net/zishanshaikh/exL9cdoe/1/</code>

Code With first element as Pivot


//Logic For Quick Sort
function quickSort(arr,l,u) {
 if(l>=u)
 {
  return;
 }


var pivot=arr[l];
var pivotCounter=l+1;
for(let i=l+1;i<u;i++)
{
    if(arr[i] <pivot )
    {
      var temp= arr[pivotCounter];
      arr[pivotCounter]=arr[i] ;
      arr[i]=temp;
      pivotCounter++;
    }
}
var j=pivotCounter-1;
var k=l+1;
while(k<=j)
{
var temp2= arr[k-1];
      arr[k-1]=arr[k] ;
      arr[k]=temp2;
      k++;
      }

      arr[pivotCounter-1]=pivot;




quickSort(arr,pivotCounter,u);
quickSort(arr,0,pivotCounter-2);



}
Improve this answer

1 Comment

The question asked was about the StackOverflowException in the author's code. This answer does not in any way address that question.
-1

A simple generic C# implementation of QuickSort, can use first or last value or any other intermediate value for pivot

using System;

namespace QuickSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arInt = { 6, 4, 2, 8, 4, 5, 4, 5, 4, 5, 4, 8, 11, 1, 7, 4, 13, 5, 45, -1, 0, -7, 56, 10, 57, 56, 57, 56 };
            GenericQuickSort<int>.QuickSort(arInt, 0, arInt.Length - 1);

            string[] arStr = { "Here", "Is", "A", "Cat", "Really", "Fast", "And", "Clever" };
            GenericQuickSort<string>.QuickSort(arStr, 0, arStr.Length - 1); ;

            Console.WriteLine(String.Join(',', arInt));
            Console.WriteLine(String.Join(',', arStr));

            Console.ReadLine();
        }

    }

    class GenericQuickSort<T> where T : IComparable
    {

        public static void QuickSort(T[] ar, int lBound, int uBound)
        {
            if (lBound < uBound)
            {
                var loc = Partition(ar, lBound, uBound);
                QuickSort(ar, lBound, loc - 1);
                QuickSort(ar, loc + 1, uBound);
            }
        }

        private static int Partition(T[] ar, int lBound, int uBound)
        {
            var start = lBound;
            var end = uBound;

            var pivot = ar[uBound];

            // switch to first value as pivot
            // var pivot = ar[lBound];

            while (start < end)
            {

                while (ar[start].CompareTo(pivot) < 0)
                {
                    start++;
                }

                while (ar[end].CompareTo(pivot) > 0)
                {
                    end--;
                }

                if (start < end)
                {
                    if (ar[start].CompareTo(ar[end]) == 0)
                    {
                        start++;
                    }
                    else
                    {
                        swap(ar, start, end);
                    }
                }
            }

            return end;
        }

        private static void swap(T[] ar, int i, int j)
        {
            var temp = ar[i];
            ar[i] = ar[j];
            ar[j] = temp;
        }
    }
}

Output:

-7,-1,0,1,2,4,4,4,4,4,4,5,5,5,5,6,7,8,8,10,11,13,45,56,56,56,57,57

A,And,Cat,Clever,Fast,Here,Is,Really

One important thing to notice here is that this optimized and simple code properly handles duplicates. I tried several posted quick sort code. Those do not give correct result for this (integer array) input or just hangs, such as https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-9.php and http://www.softwareandfinance.com/CSharp/QuickSort_Iterative.html. Therefore, if author also wants to use the code which handles duplicates this would be a good reference.

Improve this answer

1 Comment

The question asked was about the StackOverflowException in the author's code. This answer does not in any way address that question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.