Sorted array using quicksort

Question

I have an array creating 10 random integers and then sorting them using quicksort..My problem is that when I change this to creating 1,000,000 random integers it wont do it..Can you help please?

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

namespace RepeatAssignmentQ2
{
class Program
{
    static public int Partition(int[] myArray, int left, int right)
    {
        int pivot = myArray[left];
        while (true)
        {
            while (myArray[left] < pivot)
                left++;

            while (myArray[right] > pivot)
                right--;

            if (left < right)
            {
                int temp = myArray[right];
                myArray[right] = myArray[left];
                myArray[left] = temp;
            }
            else
            {
                return right;
            }

        }
    }

    static public void QuickSort_Recursive(int[] arr, int left, int right)
    {
        // For Recusrion
        if (left < right)
        {
            int pivot = Partition(arr, left, right);

            if (pivot > 1)
                QuickSort_Recursive(arr, left, pivot - 1);

            if (pivot + 1 < right)
                QuickSort_Recursive(arr, pivot + 1, right);
        }
    }

    static void Main(string[] args)
    {
        Random rnd = new Random();
        DateTime startTime = DateTime.Now;

        int ind = 0;
        int length = 1000000;
        int[] myArray = new int[length];

        while (ind < 1000000)
        {
            myArray[ind] = rnd.Next(1000000);
            ind++;
        }

        int lengthTwo = 10;

        Console.WriteLine("QuickSort by recursive method");

        QuickSort_Recursive(myArray,0, lengthTwo - 1 );



        for (int i = 0; i < 1000000; i++)
        {

            Console.WriteLine(myArray[i]);

        }
        Console.WriteLine("Total Time: {0}\n", DateTime.Now - startTime);
        Console.WriteLine();



    }
}
}

Thanks

Edit - When I tun the program with the array having 10 number it will display them and have them sorted. When I change it to 1,000,000 and run the program nothing displays.

Edit 2 - Okay for some weird reason it is doing this. I changed the code above to display the changes, It is now displaying the numbers it randomly generated but its not sorting them. But when IT only have to create 10 random numbers it did sort it.

[`Array.Sort`](http://msdn.microsoft.com/en-us/library/system.array.sort.aspx) uses quick sort interally. — Dustin Kingen, Aug 22 '13 at 18:32
"it wont do it" is a bit vague. Please be specific about your problem. — Mike Precup, Aug 22 '13 at 18:34
what ever is your problem go through this document it will surely give you clear picture http://vinayakgarg.wordpress.com/2011/10/25/time-comparison-of-quick-sort-insertion-sort-and-bubble-sort/ — Minav Patel, Aug 22 '13 at 18:36
@Remoku I believe they changed it in .net 4.5 http://stackoverflow.com/questions/12156627/string-sorting-performance-degradation-in-vs2010-vs-vs2008/12184039#12184039 — Mariusz Pawelski, Aug 22 '13 at 19:10

Usy · Accepted Answer · 2013-08-22T19:41:26.343

Populating and sorting 1,000,000 elements still should be very fast.

There is an error in your alhorithm, in Partition method. If left is lesser than right you should increase left and decrease right:

if (left < right)
{
    int temp = myArray[right];
    myArray[right] = myArray[left];
    myArray[left] = temp;
    left++;
    right--;
}

Analyze how your program behave if myArray[left] is greater or equal pivot, myArray[right] is lesser or equal than pivot and left is lesser than right. You have an infinite loop while (true), because two whiles are ignored and if doesn't change value of left or right. This situation occurs if there are duplicates in array. It happens for example when you try to populate 1,000,000 elements with only 1,000 numbers.

Btw. your code would be better if you replace every 1000000 with variable length and lengthTwo could be replaced by length. Why? In situations like this, when you want to check program behavior for bigger array. It's easier to change value of one variable than five numbers.

I hope I helped.

score 0 · Answer 2 · answered Aug 22 '13 at 18:41

0

Pardon me but how long did you wait? I suspect that the while loop that populates an array of 1mil integers is taking very long, since it's calling the Next method 1,000,000 times. Are you seeing the following output: 'QuickSort by recursive method'?

answered Aug 22 '13 at 18:41

Clocks

411
4
8

I am yes. I ran the program that popped up and I left it like that for 10 minutes and nothing else have happened – user2599678 Aug 22 '13 at 18:45

score 0 · Answer 3 · edited Apr 13 '17 at 12:48

I stumbled upon this just now, the error is here

QuickSort_Recursive(myArray,0, lengthTwo - 1 );

change it to

QuickSort_Recursive(myArray,0, length - 1 );

For your partitioning I recognize hoare's algorithm (faster than the alternative) https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto here's pseudo code for both of them (you'll see the i=p+1 and j=p-1 at the start otherwise it's good)

score 0 · Answer 4 · answered Jan 28 '18 at 12:14

Although this reply is very far away from the time of asking the question, the following is useful for anyone reading the question.

The problem with the code mentioned in the question, that it will make infinite loop on Partition function whenever the pivot element is similar on both ends(left, and right)

Here is the modified code to get it working:

static int Partition(int[] myArray, int left, int right)
    {
        int pivot = myArray[left];
        while (true)
        {
            while (myArray[left] < pivot)
                left++;

            while (myArray[right] > pivot)
                right--;

            if (left < right && myArray[left] == myArray[right])
                left++;
            else if (left < right)
            {
                int temp = myArray[right];
                myArray[right] = myArray[left];
                myArray[left] = temp;
            }
            else
            {
                return right;
            }

        }
    }

Sorted array using quicksort

4 Answers4