VPF::Обобщение в сортировке(Сравнение масивов)

kurzon

Дата 19.10.2007, 16:09 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 307
Регистрация: 12.8.2007

Репутация: -8
Всего: -11

Это обобщение в сортировке методом вставка.

Код


static class VstavSort
    {
        public static void Sort1<T>(T[] array, Comparison<T> comparison)
        {
           int i,j; 
            for (i = 0; i < array.Length - 1; i++)
            {
                T temp = array[i];
              
                for (j = i-1; (array[i-1] > temp)&&(j < 0) ; j--)
                {
                   array[j+1] = array[j];
                    
                }  

                array[j+1] = temp;
               
            }
           

        }
    }

У меня тут ошибка? ( by (array[i-1]> temp) )

Код


for (j = i-1; (array[i-1]> temp)&&(j < 0) ; j--)

Это сообщение отредактировал(а) kurzon - 19.10.2007, 16:12

marcusmae

Дата 19.10.2007, 16:32 (ссылка)

(нет голосов)

Загрузка ...

stravaganza

Профиль
Группа: Участник
Сообщений: 874
Регистрация: 26.3.2006

Репутация: 22
Всего: 39

kurzon, привет,

Дело в том, что ты используеш дженерик <T>, и для него в общем случае не определены операции сравнения. Так что написать

Код


array[i-1] > temp

не получится. Для сравнения значений типа T через аргумент функции специально передаётся делегат Comparison<T>. Так что попробуй написать :

Код


comparison(array[i-1], temp) > 0

--------------------

ἀπὸ μηχανῆς θεός

kurzon

Дата 19.10.2007, 16:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 307
Регистрация: 12.8.2007

Репутация: -8
Всего: -11

Вот я сделал и ошибка ( by http://forum.vingrad.ru/act-Attach/type/post/id-1292484.html )

Вот сам полный исходник:

Это сообщение отредактировал(а) kurzon - 19.10.2007, 16:56

Присоединённый файл ( Кол-во скачиваний: 11 )

1.jpg 94,62 Kb

marcusmae

Дата 19.10.2007, 16:55 (ссылка)

(нет голосов)

Загрузка ...

stravaganza

Профиль
Группа: Участник
Сообщений: 874
Регистрация: 26.3.2006

Репутация: 22
Всего: 39

Цитата(kurzon @ 19.10.2007, 16:40

)

Вот я сделал и ошибка...

Пардон, это уже другая проблема. Посмотри на внешний цикл : его счётчик i начинает с нуля :

Код


for (i = 0;

Пройдя дальше по коду, видим, что при i=0 индекс i-1 обращается в -1, это и вызвало исключение : выход за границы массива array.
Так что исправляй свой алгоритм сортировки. Кстати, многие примеры, что я нашёл в инете содержат такую же ошибку smile

. Вероятно, надо так :

Код


typedef int array_type; /* или typedef char array_type;*/
 
  void insertSort(array_type a[], int length) {
      int i, j;
      array_type value;
      for (i = 1; i < length; i++) {
          value = a[i];
          for (j = i-1; (j >= 0) && (a[j] > value); j--) {
              a[j+1] = a[j];
          }
          a[j+1] = value;
      }
  }

То есть, с i=1 начать. Пример взят из Википедии.

Это сообщение отредактировал(а) marcusmae - 19.10.2007, 16:59

--------------------

ἀπὸ μηχανῆς θεός

kurzon

Дата 19.10.2007, 17:33 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 307
Регистрация: 12.8.2007

Репутация: -8
Всего: -11

Уже исправил ошибку, но появилась новая(не совсем ошибка)
Мене надо что так было (comparison(array[ j -1], temp) , но не работает.
А работает так (comparison(array[ i -1], temp)

Код

static class VstavSort
    {
        public static void Sort1<T>(T[] array, Comparison<T> comparison)
        {
            int i, j;
            for (i = 1; i < array.Length; i++)
            {
                T temp = array[i];

                for (j = i - 1; (comparison(array[i-1], temp) > 0)&&(j>=0); j--)
                {
                    array[j + 1] = array[j];

                }

                array[j + 1] = temp;

            }

        }
    }

kurzon

Дата 19.10.2007, 18:27 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 307
Регистрация: 12.8.2007

Репутация: -8
Всего: -11

Ктото поможет...

Это сообщение отредактировал(а) kurzon - 19.10.2007, 18:31

kurzon

Дата 19.10.2007, 19:35 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 307
Регистрация: 12.8.2007

Репутация: -8
Всего: -11

Вот мой полный исходник:

Код


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

namespace Con_Sort
{
    struct Book
    {
        public Book(string author, int year)
        {
            this._year = year;
            this._author = author;
        }

        private int _year;

        public int Year
        {
            get { return this._year; }
            set { this._year = value; }
        }

        private string _author;

        public string Author
        {
            get { return this._author; }
            set { this._author = value; }
        }

        public override string ToString()
        {
            return String.Format("Название книги :{0}, Год :{1}", Author, Year);
        }
    }

    static class BubbleSort
    {
        public static void Sort<T>(T[] array, Comparison<T> comparison)
        {

            for (int i = array.Length - 1; i > 0; i--)
            {
                for (int j = 0; j < i; j++)
                {
                    if (comparison(array[j], array[j + 1]) > 0)
                    {
                        T temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }

        }
    }

    static class InsertSort
    {
        public static void Sort<T>(T[] array, Comparison<T> comparison)
        {
            int i, j, k;
            for (i = 1; i < array.Length; i++)
            {
                T temp = array[i];
                k = i;

                for (j = i - 1; (comparison(array[j-1], temp) > 0)&&(j>=0); j--)
                {
                    array[j + 1] = array[j];

                }

                array[j + 1] = temp;

            }

        }
    }
    static class selectSort
    {
        public static void Sort<T>(T[] array, Comparison<T> comparison)
        {
            int i, j, k;
            for (i = 0; i < array.Length; i++)
            {
                T temp = array[i];
                k = i;

                for (j = i + 1; j < array.Length; j++) // цикл выбора наименьшего элемента
                    if ((comparison(array[j], temp) > 0)) 
                {
                    k = j; temp = array[j]; // k - индекс наименьшего элемента
                }
            array[k] = array[i];
            array[i] = temp; // меняем местами наименьший с a[i]


            }

        }
    }


    class Teenager
    {
        private static Random random = new Random();
        private static readonly string[] messages = new string[6]
            { 
                "Троесент!", 
                "Ватсон!", 
                "Фаронов!", 
                "Шилд!", 
                "Агуров!", 
                "Глинський!" 
            };

        public static string Complain()
        {
            return messages[random.Next(messages.Length)];
        }
    }

    class Program
    {
        static void PrintBookTitles(Book[] books)
        {
            foreach (Book book in books)
            {
                Console.WriteLine(book);
            }
        }

        static void Main(string[] args)
        {
            Book[] books = new Book[10];
            Random random = new Random();

            for (int i = 0; i < books.Length; i++)
            {
                books[i] = new Book(Teenager.Complain(), random.Next(2007));
            }

            PrintBookTitles(books);
            //Console.Read();

            selectSort.Sort(books, delegate(Book a, Book b)
                    {
                        return a.Year.CompareTo(b.Year);
                    });

            Console.WriteLine("После сортировки:");

            PrintBookTitles(books);
            Console.ReadLine();
        }
    }
}

У меня уже реализовано двома методами сортировку, а надо сделать сортировку вставками.
Кто поможет реализовать сортировку методом вставка(еже сделано надо один глюк забрать)

Код


 static class InsertSort
    {
        public static void Sort<T>(T[] array, Comparison<T> comparison)
        {
            int i, j, k;
            for (i = 1; i < array.Length; i++)
            {
                T temp = array[i];
                k = i;

                for (j = i - 1; (comparison(array[j-1], temp) > 0)&&(j>=0); j--)
                {
                    array[j + 1] = array[j];

                }

                array[j + 1] = temp;

            }

        }
    }

Пожалуста плиз...

У меня только одна проблема:

Код


Мене надо что так было (comparison(array[j -1], temp) , но не работает.
А работает так (comparison(array[i-1], temp)

Это сообщение отредактировал(а) kurzon - 19.10.2007, 20:55

marcusmae

Дата 19.10.2007, 21:10 (ссылка)

(нет голосов)

Загрузка ...

stravaganza

Профиль
Группа: Участник
Сообщений: 874
Регистрация: 26.3.2006

Репутация: 22
Всего: 39

kurzon, дружище, в чём проблема? Я же тебе дал правильный работающий пример. Зачем тебе надо , чтобы

Цитата(kurzon @ 19.10.2007, 19:35

)

было (comparison(array[j -1], temp) , но не работает.

если это неправильно? Опять ведь вылетает за границы массива. Там должно не i-1, а просто j.

--------------------

ἀπὸ μηχανῆς θεός

kurzon

Дата 19.10.2007, 22:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 307
Регистрация: 12.8.2007

Репутация: -8
Всего: -11

Код


(comparison(array[j], temp)

Так тоже не работает...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »