[C#] Sortowanie szybki


(Iamnothouse) #1

Ostatnio zmagam się z problemem napisania Sortowania Szybkiego tablicy (a wydawało się takie proste). Początkowo totalnie próbowałem sam napisać, ale ilość błędów które moje twory mi przynosiły, bardzo mnie rozczarowały, a i czasem brakło wiedzy by je rozwiązać. Zatem zacząłem szukać takiego programu w internecie. No i oczywiście znalazłem, ale nie w C#, więc podjąłem kilka prób "przepisania" na C#. Podszedłem do dwóch prób. Jedna mnie rozczarowała, a druga no cóż, niby nie wyrzuca błędów, ale też i nie sortuje, nic także nie wyświetla. Czy ktoś byłby w stanie pokazać mi błąd ?

Możliwe że popełniałem go w każdej próbie napisania owego programu.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;


namespace ConsoleApplication8

{

    class Program

    {


        static void Sortuj_szybko(int lewy, int prawy)

{

 int i,j,N,piwot;

 N=10;

 int[] tablica = new int[N] ;

 i = (lewy + prawy) / 2;

 piwot = tablica[i]; tablica[i] = tablica[prawy];

 for(j = i = lewy; i < prawy; i++)

 if(tablica[i] < piwot)

 {

   tablica[i]=tablica[j];

   j++;

 }

 tablica[prawy] = tablica[j]; tablica[j] = piwot;

 if(lewy < j - 1) Sortuj_szybko(lewy, j - 1);

 if(j + 1 < prawy) Sortuj_szybko(j + 1, prawy);

}





        static void Main(string[] args)


        {

int N;

int i;

N=10;

int[] tablica = new int[N] ;

tablica[0] = 1305 ;

tablica[1] = 12 ;

tablica[2] = -3 ;

tablica[3] = 788 ;

tablica[4] = 2 ;

tablica[5] = 788 ;

tablica[6] = -10 ;

tablica[7] = 0 ;

tablica[8] = 9 ;

tablica[9] = -55 ;


 Sortuj_szybko(0,N - 1);





 for(i = 0; i < N; i++) 

            Console.WriteLine(tablica[N]);

 Console.ReadKey();


}}}

(Blapiter) #2

Moje stare wypociny może się przyda :slight_smile:

static void q_sort(ref int[] tab, int lewy, int prawy)

        {

            int i = lewy, j = prawy;

            int pivot = tab[(lewy+prawy)/2];

            int temp;

            while (i <= j)

            {

                while (tab[i] < pivot)

                    i++;

                while (tab[j] > pivot)

                    j--;

                if (i <= j)

                {

                    temp = tab[i];

                    tab[i] = tab[j];

                    tab[j] = temp;

                    i++;

                    j--;

                }

            }


            if (lewy < j)

            {

                q_sort(ref tab, lewy, j);

            }

            if (prawy > i)

            {

                q_sort(ref tab, i, prawy);

            }

        }

Odpalenie

q_sort(ref tablica, 0, tablica.Length-1);

(Iamnothouse) #3

Niestety, zastosowałem twój przykład, ale w tym momencie otrzymuję taką liczbę niezrozumianych błędów że hoho


(Blapiter) #4

No zobacz a mi działa dziwna sprawa :stuck_out_tongue:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Globalization;


namespace zabawki

{

    class Program

    {

        static void q_sort(ref int[] tab, int lewy, int prawy)

        {

            int i = lewy, j = prawy;

            int pivot = tab[(lewy+prawy)/2];

            int temp;

            while (i <= j)

            {

                while (tab[i] < pivot)

                    i++;

                while (tab[j] > pivot)

                    j--;

                if (i <= j)

                {

                    temp = tab[i];

                    tab[i] = tab[j];

                    tab[j] = temp;

                    i++;

                    j--;

                }

            }


            if (lewy < j)

            {

                q_sort(ref tab, lewy, j);

            }

            if (prawy > i)

            {

                q_sort(ref tab, i, prawy);

            }

        }


        static void Main(string[] args)

        {

            Random rand = new Random();

            int[] qwerty;

            qwerty = new int[20];

            for (int i = 0; i < qwerty.Length; i++)

            {

                qwerty[i] = rand.Next(100);

            }

            foreach (int el in qwerty)

            {

                Console.Write("{0} ", el);

            }


            q_sort(ref qwerty, 0, qwerty.Length-1);


            Console.WriteLine();

            foreach (int el in qwerty)

            {

                Console.Write("{0} ", el);

            }


            Console.ReadKey(true);

        }

    }

}

(Frankfurterium) #5

Zawsze można zawartość tablicy przerzucić do ArryList, a ta już ma własną metodę quicksorta.


(Tomek Matz) #6

@Frankfurterium

ArrayList, Hashtable i podobnych nie powinno się już używać. W .NET jest coś takiego jak kolekcje generyczne. Poza tym quick sort jest zaimplementowany w .NET we wszystkich metodach sortujących (być może są jakieś pojedyncze wyjątki, ale nic mi o tym nie wiadomo). Do sortowania zwykłych tablic można użyć np. statycznej metody Array.Sort, która używa niczego innego jak właśnie quick sort.


(Iamnothouse) #7

Tak tylko, że nie jestem aż tak zaawansowany, ba, można powiedzieć, że raczkuję w C#. Stąd nie mam pojęcia co znaczą:

foreach (int el in qwerty) - el in ?

q_sort(ref tab, i, prawy) - ref tab ?