html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Сортировка пузырьком и быстрая сортировка на C#

Привет, читатель :) Вот я и решил начать, причем начать я решил не с азов (я считаю что рассматривать их не стоит) но и чего-то запредельно сложного тут не найти. Я всего лишь студент который учиться как и ты.
Итак, первое о чем я хотел написать, так это о сортировке и ее реализации. Почему именно с нее? все просто, очень часто на собеседованиях требуют знания как работает тот или иной метод сортировки, или просят его реализовать, а во вторых всегда приятнее уметь самому делать то что уже реализовано. Так что то я заговорился не по делу, пора начинать.

Задача: Реализовать *.DLL библиотеку которая будет реализовывать сортировку массива методом пузырька или быстрой сортировкой по возрастанию и убыванию.

Так с задачей мы определились, начнем реализовывать.
Подробно о этих методах сортировки можно ознакомиться тут:
Сортировка пузырькомБыстрая сортировка.
Так с теорией мы тоже разобрались :) Быстро продвигаемся.
Начнем с реализации метода пузырька, так как он проще: Создадим класс с именем "BubbleSort.cs"

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

namespace ASort
{
    public class BubbleSort
    {
    }
}

Заглянем немного на перед и вспомним что потом нам придется реализовывать сортировку по возрастанию и убыванию, следовательно нам нужно свойство которое бы содержало эту информацию, давайте его добавим:

private  bool IsDown;
public bool IsDownValue
{
    get
    {
        return IsDown;
    }
    set
    {
        IsDown = value;
    }
}

Почему мы сделали именно так? все просто, потому что нам необходимо обеспечить безопасность этого свойства и мы не хотим что бы в него попало не хорошее значение, непонятно откуда.

Теперь начнем самое интересное саму сортировку, так как мы не знаем какой тип данных будет в массиве используем универсальный интерфейс IComparable, объявление метода будет следующим:

public Array Sort(T[] arr)where T:IComparable
{
//тут происходит сортировка
return arr;
}


Я продемонстрирую как сделать сортировку по возрастанию, для убывания вы с легкостью сделаете сами:

for (int i = 0; i < arr.Length; i++)
            {
                for (int j = 0; j < arr.Length-1; j++)
                {
                    if (!IsDownValue)
                    {
                        if (arr[j].CompareTo(arr[j + 1]) > 0)//возрастание
                        {
                            T temp = arr[j];
                            arr[j] = arr[j + 1];
                            arr[j + 1] = temp;
                        }
                    }
                    else
                    {
                        //по аналогии с предыдущем условием делаем для убывания
                    }
                }
            }

Результатом работы данного метода будет массив той же размерности и типа что входной, однако уже упорядоченный.

Теперь давай те попробуем сделать тоже самое но методом быстрой сортировки. Создадим новый класс в проекте назовем, например "QuickSort.cs" и как и в прошлый раз создадим в нем точно такое же свойство.

C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable

int partition( T[] m, int a, int b) where T :IComparable
{
    int i = a;
    for (int j = a; j <= b; j++)         // просматриваем с a по b
    {        
        if (m[j].CompareTo( m[b]) <= 0)  // если элемент m[j] не превосходит m[b],
        {
            T t = m[i];                  // меняем местами m[j] и m[a], m[a+1], m[a+2] и так далее...
            m[i] = m[j];                 // то есть переносим элементы меньшие m[b] в начало,
            m[j] = t;                    // а затем и сам m[b] «сверху»
            i++;                         // таким образом последний обмен: m[b] и m[i], после чего i++
        }
    }
    return i - 1;                        // в индексе i хранится <новая позиция элемента m[b]> + 1
}
 
void quicksort( T[] m, int a, int b) where T : IComparable// a - начало подмножества, b - конец
{                                        // для первого вызова: a = 0, b = <элементов в массиве> - 1
    if (a >= b) return;
    int c = partition( m, a, b);
    quicksort( m, a, c - 1);
    quicksort( m, c + 1, b);
}
 
//Пример вызова
//double[] arr = {9,1.5,34.4,234,1,56.5};
//quicksort(arr,0,arr.Length-1);

Теперь добавим возможность выбора сортировки по возрастанию и убыванию.

private int partition(T[] arr, int start, int end) where T : IComparable
        {
            int i = start;
            for (int j = start; j <= end; j++)
            {
                if (!IsDownValue)
                {
                    if (arr[j].CompareTo(arr[end]) <= 0)
                    {
                        T t = arr[i];
                        arr[i] = arr[j];
                        arr[j] = t;
                        i++;
                    }
                }
                else
                {
                    if (arr[j].CompareTo(arr[end]) >= 0)
                    {
                        T t = arr[i];
                        arr[i] = arr[j];
                        arr[j] = t;
                        i++;
                    }
                }
            }
            return i - 1;
        }
Ну вот и все. Все готово. Советую собирать проект в виде dll и использовать как библиотеку, как ее использовать описано тут в заголовке ASort, там же можно скачать то что получилось у меня.

Не давно нашел пример быстрой сортировки с помощью лямбда выражений:

using System;
using System.Collections.Generic;
using System.Linq;
 
static public class Qsort
    {
        public static IEnumerable QuickSort(this IEnumerable list) where T : IComparable
        {
            if (!list.Any())
            {
                return Enumerable.Empty();
            }
            var pivot = list.First();
            var smaller = list.Skip(1).Where(item => item.CompareTo(pivot) <= 0).QuickSort();
            var larger = list.Skip(1).Where(item => item.CompareTo(pivot) > 0).QuickSort();
 
            return smaller.Concat(new[] { pivot }).Concat(larger);
        }
 
//(тоже самое, но записанное в одну строку, без объявления переменных)
 
        public static IEnumerable shortQuickSort(this IEnumerable list) where T : IComparable
        {
            return !list.Any() ? Enumerable.Empty() : list.Skip(1).Where(
                item => item.CompareTo(list.First()) <= 0).shortQuickSort().Concat(new[] { list.First() })
                    .Concat(list.Skip(1).Where(item => item.CompareTo(list.First()) > 0).shortQuickSort());
        }       
    }
Ну вот и все, спасибо за внимание.

Читать дальше
Twitter
Одноклассники
Мой Мир

материал с i-am-a-kernel.blogspot.ru

1

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • mister_arti
          • домен blogspot.ru
          • домен i-am-a-kernel.blogspot.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции