Сегодня 6 мая, понедельник

Какой рейтинг вас больше интересует?

получить код

Главная / Каталог блогов / Cтраница блогера Непутевые заметки о C# / Запись в блоге

	Непутевые заметки о C# Голосов: 0 Адрес блога: http://i-am-a-kernel.blogspot.com/ Добавлен: 2012-10-31 18:45:33

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

2012-10-30 16:35:00 (читать в оригинале)

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

Задача: Реализовать *.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());
        }       
    }

Ну вот и все, спасибо за внимание.

Тэги: .net, быстрый, пузырек, сортировка

Блограйдеров
14489

Блогов
219902
(+0 сегодня)

Сообществ
1309
(+0 сегодня)

ЖЖ все стерпит
по количеству голосов (152) в категории «Истории»

Категория «Образование»

Взлеты Топ 5


+493	506	В интересном положении
+450	511	Документальное кино
+439	471	ГОРОСКОП
+406	514	Документальные фильмы
+377	445	Темы_дня

Падения Топ 5


-1	13	Волонтеры. Красный крест
-1	30	Skytao
-3	8	Улицы Праги
-7	5	Планирование проекта
-8	6	Адреналин продаж

Загрузка...

BlogRider.ru не имеет отношения к публикуемым в записях блогов материалам. Все записи
взяты из открытых общедоступных источников и являются собственностью их авторов.