c# - paso - quicksort java

Implementando el algoritmo de quicksort

Question

Encontré el algoritmo quicksort de este libro

Este es el algoritmo

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

Y he hecho este código c #:

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] + " ";
    }
}

Cuando llamo a una función como esta quicksort(arr,0,arr.Length-1); Recibo este error. An unhandled exception of type ''System.StackOverflowException'' occurred que pasa una matriz vacía ... cuando la función de llamada es como esta quicksort(arr,0,arr.Length); Me sale el Index was outside the bounds of the array. error Index was outside the bounds of the array. en esta línea int pivot = input[high]; pero la matriz pasó con éxito.

También quiero imprimirlo como esta print(input,tbQuick); pero ¿dónde colocarlo para que se imprima cuando termine el pedido rápido?

Answer 1

Además de la respuesta de Deestan, también tiene este error:

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

Debería ser:

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

Answer 2

En caso de que desee un código más corto para 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))));
    }

Obtenga p (pivote) con cualquier método que sea adecuado, por supuesto.

Answer 3

Esta es la implementación más corta del algoritmo de ordenación rápida.

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)));
}

Answer 4

No implementó correctamente la terminación del caso base, lo que hace que quicksort nunca deje de recurrir a sí misma con sublistas de longitud 0.

Cambia esto:

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

a esto:

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

Answer 5

Una sencilla implementación de clasificación rápida.

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();
*/

Answer 6

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);



}