How can I make my Quick Sort Algorithm sort the arrays in both Ascending and Descending order?

Question

Currently my Quick Sort algorithm sorts the array in Ascending order in case 1 but I would like to make it so that when the user selects option 2 (case 2) then it sorts the array in Descending order. Do I have to create 2 separate algorithms for each case? Or is there a simpler and more efficient way?

Appreciate the help.

  static void Main(string[] args)
    {
        Console.WriteLine("Analysis of Seismic Data.\n");



        Console.WriteLine("Selection of Arrays:");
        //Display all the options.
        Console.WriteLine("1-Year");
        Console.WriteLine("2-Month");
        Console.WriteLine("3-Day");
        Console.WriteLine("4-Time");
        Console.WriteLine("5-Magnitude");
        Console.WriteLine("6-Latitude");
        Console.WriteLine("7-Longitude");
        Console.WriteLine("8-Depth");
        Console.WriteLine("9-Region");
        Console.WriteLine("10-IRIS_ID");
        Console.WriteLine("11-Timestamp\n\n");

        Console.WriteLine("Use numbers to select options.");
        //Read in user's decision.
        Console.Write("Select which array is to be analysed:");
            int userDecision = Convert.ToInt32(Console.ReadLine());

        //Selected which array is to be analyzed
            switch (userDecision)
            {
                case 1:
                    Console.WriteLine("\nWould you like to sort the Array in Ascending or Descending order?");
                    Console.WriteLine("1-Ascending");
                    Console.WriteLine("2-Descending");
                    //Create another switch statement to select either ascending or descending sort.
                    int userDecision2 = Convert.ToInt32(Console.ReadLine());
                    switch (userDecision2)
                    {
                        case 1:
                        //Here algorithm sorts my array in ascending order by default.
                        QuickSort(Years);
                        Console.WriteLine("Contents of the Ascending Year array: ");
                        foreach (var year in Years)
                        {
                            Console.WriteLine(year);
                        }
                        break;
                        case 2:
                        //How do I sort the same array in Descending order when Option 2 is selected?
                        //QuickSort(Years) Descendingly.
                            Console.WriteLine("Contents of the Descending Year array: ");
                            foreach (var year in Years)
                            {
                                Console.WriteLine(year);
                            }
                            break;

                    }
                    break;
                case 2:
                    Console.WriteLine("\nWould you like to sort the Array in Ascending or Descending order?");
                    Console.WriteLine("1-Ascending");
                    Console.WriteLine("2-Descending");
                    //Create another switch statement to select either ascending or descending sort.
                    int userDecision3 = Convert.ToInt32(Console.ReadLine());
                    switch (userDecision3)
                    {
                        case 1:
                        QuickSort(Years);
                        Console.WriteLine("Contents of the Ascending Month array: ");
                        foreach (var month in Months)
                        {
                            Console.WriteLine(month);
                        }
                        break;
                        case 2:
                        //Same problem, how do I sort it in descending order?
                            Console.WriteLine("Contents of the Descending month array: ");
                        foreach (var month in Months)
                        {
                            Console.WriteLine();
                        }
                        break;
                    }
                    break;


        }

    }
    public static void QuickSort<T>(T[] data) where T : IComparable<T>
    {
        Quick_Sort(data, 0, data.Length - 1);
    }

    public static void Quick_Sort<T>(T[] data, int left, int right) where T : IComparable<T>
    {
        int i, j;
        T pivot, temp;
        i = left;
        j = right;
        pivot = data[(left + right) / 2];
        do
        {
            while ((data[i].CompareTo(pivot) < 0) && (i < right)) i++;
            while ((pivot.CompareTo(data[j]) < 0) && (j > left)) j--;
            if (i <= j)
            {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
                i++;
                j--;
            }
        } while (i <= j);
        if (left < j) Quick_Sort(data, left, j);
        if (i < right) Quick_Sort(data, i, right);
    }

You could also pass a paramerter that decides the sort order but e.g. in Linq the developers from microsoft decided to create a own method OrderByDescending() — fubo
– fubo, Commented May 5, 2017 at 11:17

Matthew Watson · Accepted Answer · 2017-05-05 11:27:19Z

2

You can change your Quicksort method to accept an IComparer<T> comparer, and then use that to make the comparisons.

Then you can use Comparer<T>.Default if you want the default comparison order, or you can use Comparer<T>.Create() to create a custom (e.g. reversed) comparison.

Compilable example:

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Program
    {
        static void Main()
        {
            int[] data = {6, 7, 2, 3, 8, 1, 9, 0, 5, 4};

            QuickSort(data);

            Console.WriteLine(string.Join(", ", data)); // Prints 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

            QuickSort(data, Comparer<int>.Create((a, b) => b.CompareTo(a)));

            Console.WriteLine(string.Join(", ", data)); // Prints 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
        }

        public static void QuickSort<T>(T[] data)
        {
            Quick_Sort(data, 0, data.Length - 1, Comparer<T>.Default);
        }

        public static void QuickSort<T>(T[] data, IComparer<T> comparer)
        {
            Quick_Sort(data, 0, data.Length - 1, comparer);
        }

        public static void Quick_Sort<T>(T[] data, int left, int right, IComparer<T> comparer)
        {
            int i, j;
            T pivot, temp;
            i = left;
            j = right;
            pivot = data[(left + right) / 2];
            do
            {
                while ( (comparer.Compare(data[i], pivot) < 0) && (i < right)) i++;
                while ( (comparer.Compare(pivot, data[j]) < 0) && (j > left)) j--;
                if (i <= j)
                {
                    temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                    i++;
                    j--;
                }
            } while (i <= j);
            if (left < j) Quick_Sort(data, left, j, comparer);
            if (i < right) Quick_Sort(data, i, right, comparer);
        }
    }
}

This has two advantages:

The type T does NOT need to implement IComparable<T>. You can pass in an IComparer<T> object that does the comparison.
You can sort the same data in multiple ways, by passing in different custom IComparer<T> object.

This is the approach adopted by a number of the Linq IEnumerable extensions, for example Enumerable.OrderBy()

answered May 5, 2017 at 11:27

Matthew Watson

111k12 gold badges179 silver badges301 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Doctorhmmm Over a year ago

Thanks for the solution. I am new to programming and haven't learned about interfaces yet. What should I research to better understand the specific solution you showed here? Also does this solution use any built-in sorting and searching functions because I am not allowed to use these in my task.

Matthew Watson Over a year ago

@IllimarIssak It's not using any built-in sorting or searching; it's just using an interface to specify the way to compare to elements. For more info see IComparer<T>

MBo · Accepted Answer · 2017-05-05 11:27:02Z

0

Add parameter that allows to change result of comparisons

(data[i].CompareTo(pivot) < 0) 
and 
(pivot.CompareTo(data[j]) < 0)

One simple way: argument descending +1/-1 and use

 data[i].CompareTo(pivot) * descending < 0

answered May 5, 2017 at 11:27

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Comments

JNW · Accepted Answer · 2017-05-05 14:31:00Z

Just adding a bit of cream on @Matthew Watson answer. As after reading the post from @Illimar he wanted to give the user the choice in sorting the Array either in Ascending mode or in Descending mode. I have just edited @Matthew work to come up with the following:

    using System;
    using System.Collections.Generic;
    using System.Threading;

   namespace Test1
     {

            class Program
   {
    static void Main(string[] args)
    {
        MySorter();
    }

    static void MySorter()

    {
        int[] data = MyArray();
        Console.WriteLine();
        Console.WriteLine("Chose 1 to sort Ascending or 2 to sort Descending:");
        //int choice = Console.Read();
        ConsoleKeyInfo choice = Console.ReadKey();
        Console.WriteLine();
        if (choice.Key == ConsoleKey.D1 || choice.Key == ConsoleKey.NumPad1)
        {
            QuickSort(data);
            string result = string.Join(", ", data);
            Console.WriteLine(result);
            Thread.Sleep(4000);
        }
        else if (choice.Key == ConsoleKey.D2 || choice.Key == ConsoleKey.NumPad2)
        {
            QuickSort(data, Comparer<int>.Create((a, b) => b.CompareTo(a)));
            Console.WriteLine(string.Join(", ", data));
            Thread.Sleep(4000);
        }
        else
        {
            Console.WriteLine("wrong input.");
            Thread.Sleep(2000);
            Environment.Exit(0);
        }
    }

    public static int[] MyArray()
    {
        Console.WriteLine("Enter a total of 10 numbers to be sorted: ");
        int[] InputData = new int[10];
        for (int i = 0; i < InputData.Length; i++)
        {
            var pressedkey = Console.ReadKey();
            int number;
            bool result = int.TryParse(pressedkey.KeyChar.ToString(), out number);
            if (result)
            {
                InputData[i] = number;
            }

        }

        return InputData;
    }

    public static void QuickSort<T>(T[] data)
    {
        Quick_Sort(data, 0, data.Length - 1, Comparer<T>.Default);
    }

    public static void QuickSort<T>(T[] data, IComparer<T> comparer)
    {
        Quick_Sort(data, 0, data.Length - 1, comparer);
    }

    public static void Quick_Sort<T>(T[] data, int left, int right, IComparer<T> comparer)
    {
        int i, j;
        T pivot, temp;
        i = left;
        j = right;
        pivot = data[(left + right) / 2];
        do
        {
            while ((comparer.Compare(data[i], pivot) < 0) && (i < right)) i++;
            while ((comparer.Compare(pivot, data[j]) < 0) && (j > left)) j--;
            if (i <= j)
            {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
                i++;
                j--;
            }
        } while (i <= j);
        if (left < j) Quick_Sort(data, left, j, comparer);
        if (i < right) Quick_Sort(data, i, right, comparer);
     }

     }

    }

So In the above the User gives the numbers to be sorted as Input and then chooses how the sorting should be done?

Collectives™ on Stack Overflow

How can I make my Quick Sort Algorithm sort the arrays in both Ascending and Descending order?

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related