Sortowanie elementów listy

Sortowanie jest często wykorzystywanym algorytmem w życiu programisty. W przypadku Visual Studio 2005 sortowanie jest wbudowane w komponenty. Na przykład komponent LisBox (lista) posiada właściwość Sort, której zaznaczenie rozwiązuje sprawę sortowania jej elementów. Jest to rozwiązanie znacznie ułatwiające programowanie. W tym przykładzie zajmiemy się jednak algorytmami sortującymi. Nie skorzystamy więc z dobrodziejstwa automatycznego sortowania. Spróbujemy napisać własne algorytmy sortujące. Być może takie podejście jest delikatnie mówiąc utrudnianiem sobie życia, to jednak, ma także pozytywne a dokładniej poznawcze aspekty.  
Pierwszym etapem jest utworzenie nowego projektu. Wybierz rodzaj projektu – Aplikacja Windows Forms i wpisz jego nazwę (Name). Nasz projekt nazywa się po prostu – Sortowanie. Po utworzeniu projektu środowisko utworzy nowy projekt wraz z oknem głównym. Przede wszystkim zapisz na dysk nowo utworzony projekt w wybranym folderze. Następnie, wzorując się na Rysunku 1 umieszczaj na formie projektu elementy programu. Po umieszczeniu elementów, zaznaczaj po kolei każdy komponent i posługując się oknem Properties (Właściwości komponentu), zmień wymienione w tabeli właściwości.

Nazwa komponentu Nazwa (Name) Dodatkowe właściwości
Form1 okno_sort FormBorderStyle: FixedSingle

StartPosition: CenterScreen

Text: Sortowanie elementów

ListBox Lista BorderStyle: FixedSingle

Font: Courier New; 9,75pt

sortowanie1

Umieszczanie i nadawanie właściwości komponentom należy do żmudnych i mało ambitnych czynności. Na szczęście projekt nie jest zbyt skomplikowany. Jeśli udało ci się przebrnąć przez te czynności, to przekonasz się, że teraz pozostaje już tylko zaprogramowanie poszczególnych zdarzeń dla przycisków i innych komponentów. Przede wszystkim zaczniemy od wypełnienia listy ListBox wartościami losowymi. Założenie programu jest takie, aby ilość generowanych elementów oraz maksymalną wartość ustalać w parametrach komponentów NumericUpDown (Ilość elementów, Wartość maksymalna). Zwróć uwagę, że komponentom tym nadaliśmy właściwości Maximum, Minimum oraz Value. Pierwsza z nich określa maksymalną możliwą wartość jaką użytkownik może wpisać, druga analogicznie oznacza wartość najmniejszą. Należy pamiętać, że wpisanie dużej wartości spowoduje długi okres sortowania a w szczególnych przypadkach może powodować zawieszenie się programu. Ostatnia  właściwość – Value, służy do określenia wartości domyślnej, ustalonej automatycznie po uruchomieniu programu. Dzięki temu, że Visual Studio .NET jest narzędziem do szybkiego projektowania i testowania aplikacji, na każdym etapie projektowania możemy uruchomić dotychczas stworzony program wciskając klawisz F5 lub wybierając z menu Debug->Start Ddebugging. Koniec testowania i ponowne wejście do edycji programu następuje po jego zakończeniu lub, jeśli sprawia kłopoty, uruchomieniu opcji DebugStop Debugging w menu. Jak zapewne pamiętasz z pierwszego rozdziału opisującego podstawy tworzenia aplikacji w środowisku Visual Studio Express, aby dodać zdarzenie definiujące wciśnięcie przycisku, wystarczy w trybie projektowania (Design) wcisnąć podwójnie przycisk, do którego chcesz zdarzenie definiować. Na początek zdefiniuj przycisk Generuj losową tablicę.

Oto kod zdarzenia przycisku:

private void button_generuj_Click(object sender, EventArgs e)
 {
  lista.Items.Clear();
  postep.Maximum = Convert.ToInt32(maks.Value);
  Random losowa = new Random();
 
  for (int a = 1; a < maks.Value; a++)
  {
   lista.Items.Add(losowa.Next(1, Convert.ToInt32(max_liczba.Value)));
   postep.Value = a;
  }
   postep.Value = 0;
 }

Po wpisaniu powyższego kodu do metody zdarzenia wciśnięcia przycisku button_generuj zajmiemy się teraz przyciskiem kończącym program. Obsługa zdarzenia kończąca program jest na tyle prosta, że metodę sortującą zostawimy sobie na koniec. Podobnie jak z przyciskiem poprzednim klikamy dwukrotnie w trybie projektowania (Design) na przycisk Zakończ a gdy system przeniesie nas do edytora kodu, wpisujemy tylko: Application.Exit(); Instrukcja kończąca program będzie wyglądać tak:

 
private void button_koniec_Click(object sender, EventArgs e)
   {
     Application.Exit();
   }

Zakończenie programu realizuje tylko jedna funkcja Exit, będąca metodą klasy Application. Spróbujmy uruchomić nasz program używając do tego klawisza F5. Jak widać, program reaguje już na wciśnięcie przycisków generowania listy a także przycisku zakończenia programu. Spróbuj także generować elementy tablicy po zmianie ilości oraz wartości elementów tablicy. Jak widać, stworzyłeś już całkiem ciekawy program. Zauważ, że ustalając np. ilość elementów na 6 a wartość liczb na 49, możesz otrzymać prosty system generowania liczb np. dużego lotka. Należało by jedynie zadbać o niepowtarzalność generowanych wyników. W naszym przypadku nie będziemy stosować, gdyż wydłużyło by to znacznie generowanie większych tablic. Ale to nie koniec – zajmijmy się teraz projektowaniem właściwej funkcji programu. Słowo funkcja w liczbie pojedynczej jest nieco błędna. Nasz program posiada opcje sortowania w 5 różnych metodach sortowania. Oczywiście możesz wykorzystać tylko jedną z nich. Lepiej jednak, gdy zaimplementujesz w programie wiele różnych metod. Pozwoli ci to poznać różnice w prędkości sortowania a te, jak się przekonasz, są znaczące. Dodaj więc metodę obsługi zdarzenia przycisku Sortuj i wpisz poniższy kod:

private void button_sortuj_Click(object sender, EventArgs e)
 {
  if (lista.Items.Count > 0)
   {
    if (typ_babelkowe.Checked) Sort_babelkowe();
    if (typ_wybor.Checked) Sort_wybor();
    if (typ_wstawianie.Checked) Sort_wstawianie();
    if (typ_shella.Checked) Sort_shella();
    if (typ_szybkie.Checked) Sort_szybkie(0, lista.Items.Count - 1);
    postep.Value = 0;
   }
   else MessageBox.Show("Najpierw wygeneruj tablicę elementów.");
 }

Metoda ta ma na celu sprawdzenie przycisków radiowych (RadioButton), które służą do wyboru metody sortowania. Jednak przed kontrolą przycisków funkcja sprawdza, czy elementy tablicy zostały już wygenerowane (lista posiada więcej niż 0 elementów). Jeśli warunek ten nie jest spełniony, wyświetla się okno z komunikatem informujące o konieczności wygenerowania elementów tablicy. Jeśli warunek jest spełniony, następuje sekwencyjne sprawdzanie przycisków radiowych. Jeśli przycisk typ_babelkowe jest zaznaczony (Checked) to wywołaj funkcję Sort_babelkowe(). Przyciski radiowe mają tę właściwość, że tylko jeden z nich może być zaznaczony i przyjąć wartość Checked == true. Reszta przycisków zwraca Checked == false. Zauważ jednak, że po wpisaniu powyższego kodu, przy próbie uruchomienia otrzymasz błąd. Odwołujesz się do funkcji Sort_Babelkowe(), Sort_wybor(), Sort_wstawianie(), Sort_shella(), Sort_szybkie(), które nie zostały wcześniej napisane. Wyjaśnienie zobaczysz poniżej. Najpierw jednak wstaw znaki komentarza wyłączając poszczególne linie.

//  if (typ_babelkowe.Checked) Sort_babelkowe();
//  if (typ_wybor.Checked) Sort_wybor();
//  if (typ_wstawianie.Checked) Sort_wstawianie();
//  if (typ_shella.Checked) Sort_shella();
//  if (typ_szybkie.Checked) Sort_szybkie(0, lista.Items.Count - 1);

Ponownie spróbuj uruchomić program klawiszem F5. Tym razem, zapewne program się uruchomił. Jednak nadal nie działa funkcja sortująca. Choć mamy już możliwość wyboru metody sortowania, to jednak musimy te metody napisać i odznaczać w powyższym kodzie wywołanie metody po metodzie, na bieżąco je testując. Przejdź do edycji kodu źródłowego projektu klawiszem F7, i wpisz poniższą metodę poniżej metody button_sortuj_Click:

private void Sort_babelkowe()
  {
   // Sortowanie Bąbelkowe
   for (int j = 0; j < lista.Items.Count - 1; j++, postep.Value = j)
    for (int i = 0; i < lista.Items.Count - 1; i++)
if (Convert.ToInt32(lista.Items[i])>Convert.ToInt32(lista.Items[i+1]))
       {
           int x = Convert.ToInt32(lista.Items[i]); 
           lista.Items[i] = lista.Items[i + 1]; 
           lista.Items[i + 1] = x;                       
       }
    }

Jeśli nie jesteś pewien, gdzie dokładnie wstawić powyższy kod, spójrz na kod źródłowy Źródło 1. Mamy już zaimplementowaną funkcję sortującą lecz niestety w poprzednim kroku wyłączyliśmy jej wywołanie poprzez wstawienie znaków //. Teraz, gdy funkcja sortowania bąbelkowego jest już ukończona, usuńmy znaki // z wywołania tej funkcji.

if (typ_babelkowe.Checked) Sort_babelkowe();
 //  if (typ_wybor.Checked) Sort_wybor();
 //  if (typ_wstawianie.Checked) Sort_wstawianie();
 //  if (typ_shella.Checked) Sort_shella();
 //  if (typ_szybkie.Checked) Sort_szybkie(0, lista.Items.Count - 1);

Ponownie uruchom program klawiszem F5. Wygeneruj elementy, zaznacz jako metodę sortowanie bąbelkowe i kliknij przycisk Sortuj. Jeśli ustawiłeś zbyt dużą ilość elementów tablicy, to będziesz musiał trochę poczekać. Niestety sortowanie bąbelkowe jest bardzo wolne. Jak wcześniej wspomniałem, nasz program jest na tyle wspaniały, że oferuje różne metody sortowania. Aby dodać kolejną metodę, wystarczy że dopiszesz ją bezpośrednio pod metodą poprzednią:

private void Sort_wybor()
 { // Sortowanie przez wybór
  for (int j = 0; j < lista.Items.Count - 1; j++, postep.Value = j)
   {
    int pmin = j;
   for (int i = j + 1; i < lista.Items.Count; i++)
if (Convert.ToInt32(lista.Items[i])<Convert.ToInt32(lista.Items[pmin])) 
 pmin = i;
   int x = Convert.ToInt32(lista.Items[pmin]); 
   lista.Items[pmin] = lista.Items[j]; 
   lista.Items[j] = x;
   }
 }

Oczywiście, jak w przypadku poprzednim musisz odblokować wywołanie metody usuwając z wiersza  // if (typ_wstawianie.Checked) Sort_wstawianie();
Znaki //. Kolejne metody wstawiasz analogicznie. Całość programu znajduje się w listingu Źródło 1. Możesz także pobrać gotowy listing lub gotowy, skompilowany przykład z naszego serwera ftp.
W kodzie wykorzystujesz następujące elementy języka: ListBox (czyszczenie listy, wstawienie elementu), generowanie liczb pseudolosowych, metody paska postępu ProgressBar (przypisywanie wartości, minimalna wartość), konwersję typów. Jeśli nie rozumiesz tych pojęć lub chcesz je sobie przypomnieć, wróć do rozdziału pierwszego, który opisuje podstawy programowania w języku C#.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace Sortowanie
{
    public partial class okno_sort : Form
    {
        public okno_sort()
        {
            InitializeComponent();
        }
        private void button_generuj_Click(object sender, EventArgs e)
        {
            lista.Items.Clear();
            postep.Maximum = Convert.ToInt32(maks.Value);
            Random losowa = new Random();
 
            for (int a = 1; a < maks.Value; a++)
            {
          lista.Items.Add(losowa.Next(1, Convert.ToInt32(max_liczba.Value)));
          postep.Value = a;
            }
          postep.Value = 0;
        }
          private void button_koniec_Click(object sender, EventArgs e)
        {
            Application.Exit();
        }
        private void button_sortuj_Click(object sender, EventArgs e)
        {
            if (lista.Items.Count > 0)
            {
                if (typ_babelkowe.Checked) Sort_babelkowe();
                if (typ_wybor.Checked) Sort_wybor();
                if (typ_wstawianie.Checked) Sort_wstawianie();
                if (typ_shella.Checked) Sort_shella();
              if (typ_szybkie.Checked) Sort_szybkie(0, lista.Items.Count - 1);
                postep.Value = 0;
            }
            else MessageBox.Show("Najpierw wygeneruj tablicę elementów.");
        }
 
        private void Sort_babelkowe()
        {
           // Sortowanie Bąbelkowe
            for (int j = 0; j < lista.Items.Count - 1; j++, postep.Value = j)
                for (int i = 0; i < lista.Items.Count - 1; i++)
  if (Convert.ToInt32(lista.Items[i]) > Convert.ToInt32(lista.Items[i + 1]))
                    {
                     int x = Convert.ToInt32(lista.Items[i]); 
                     lista.Items[i] = lista.Items[i + 1]; 
                     lista.Items[i + 1] = x;                       
                    }
       }
 
        private void Sort_wybor()
        { // Sortowanie przez wybór
            for (int j = 0; j < lista.Items.Count - 1; j++, postep.Value = j)
            {
             int pmin = j;
             for (int i = j + 1; i < lista.Items.Count; i++)
if (Convert.ToInt32(lista.Items[i])<Convert.ToInt32(lista.Items[pmin])) pmin=i;
             int x = Convert.ToInt32(lista.Items[pmin]); 
             lista.Items[pmin] = lista.Items[j]; 
             lista.Items[j] = x;
            }
        }
        private void Sort_wstawianie()
        { // Sortowanie przez wstawianie
            for (int j = lista.Items.Count - 2; j >= 0; j--)
            {
              postep.Value = lista.Items.Count-j;
              int x = Convert.ToInt32(lista.Items[j]);
              int i = Convert.ToInt32(j + 1);
     while ((i < lista.Items.Count) && (x > Convert.ToInt32(lista.Items[i])))
              {                    
               lista.Items[i - 1] = lista.Items[i];
               i++;
              }
             lista.Items[i - 1] = x;
            } 
        }
        private void Sort_shella()
        { // Sortowanie Shella
            // Wyznaczamy wartość początkowego przesunięcia
            int h,j,x,i;
            for (h = 1; h < lista.Items.Count; h = 3 * h + 1);
            h /= 9;
 
           if (h == 0) h = 1;
            // Sortujemy
            while (h>0)
            {                
                for (j = lista.Items.Count - h - 1; j >= 0; j--)
                {
                    postep.Value = lista.Items.Count - h;
                    x = Convert.ToInt32(lista.Items[j]);
                    i = j + h;
   while ((i < lista.Items.Count) && (x > Convert.ToInt32(lista.Items[i])))
                    {
                        lista.Items[i - h] = lista.Items[i];
                        i += h;
                    }
                    lista.Items[i - h] = x;
                }
                h /= 3;
            }
            postep.Value = h;
        }
        private void Sort_szybkie(int lewy, int prawy)
        { // Sortowanie szybkie
            int i, j, piwot, x;
            i = (lewy + prawy) / 2;
            piwot = Convert.ToInt32(lista.Items[i]); 
            lista.Items[i] = lista.Items[prawy];
 
            for (j = i = lewy; i < prawy; i++)
                if (Convert.ToInt32(lista.Items[i]) < piwot)
                {
                    x = Convert.ToInt32(lista.Items[i]);
                    lista.Items[i] = lista.Items[j];
                    lista.Items[j] = x;
                    j++;
                }           
            lista.Items[prawy] = lista.Items[j]; 
            lista.Items[j] = piwot;
            if (lewy < j - 1) Sort_szybkie(lewy, j - 1);
            if (j + 1 < prawy) Sort_szybkie(j + 1, prawy);
            postep.Value = i;
        }
    }
}

463total visits,1visits today

Tagi , .Dodaj do zakładek Link.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

84 + = 85

This site uses Akismet to reduce spam. Learn how your comment data is processed.