Форум программистов, компьютерный форум, киберфорум
Наши страницы
Haskell
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
Bein
0 / 0 / 0
Регистрация: 17.09.2016
Сообщений: 99
1

Переделать быструю сортировку

19.01.2018, 21:56. Просмотров 790. Ответов 5

Haskell
1
2
3
4
5
thirdElem (_,_,c) = c
 
qsort [] = []
qsort (h:t) = 
    qsort[x|x<-t, x<=h]++[h]++qsort[x|x<-t,x>h]
Функция быстрой сортировки, приведенная выше. прекрасно работает со списком чисел. Но что, если у нас есть некий кортеж , в котором третий элемент - число (Например, ('d','k',21)), то как переделать данную сортировку, чтобы она упорядочивала список кортежей из трёх элементов по возрастанию третьего эл-та в кортеже? Написал функцию therdElem, но вот приладить к qsort никак не получается
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2018, 21:56
Ответы с готовыми решениями:

Пример на быструю сортировку
форумчане пожалуйста, приведите пример на быструю сортировку, на одномерный массив, заполненными...

Как сделать быструю сортировку?
Как сделать быструю сортировку???

Поменять быструю сортировку на пузырьковую
Поменять быструю сортировку на пузырьковую. using System; using System.IO; using...

Можете обьяснить Быструю сортировку?
Алгоритм понял, но реализовать не получается?

Как оптимизировать быструю сортировку?
Помогите пожалуйста оптимизировать быструю сортировку. Какой лучше выбрать опорный элемент? ...

5
korvin_
2747 / 2019 / 364
Регистрация: 28.04.2012
Сообщений: 6,889
19.01.2018, 23:08 2
Цитата Сообщение от Bein Посмотреть сообщение
Функция быстрой сортировки, приведенная выше. прекрасно работает со списком чисел. Но что, если у нас есть некий кортеж , в котором третий элемент - число (Например, ('d','k',21)), то как переделать данную сортировку
Функцию сортировки переделывать не нужно никак. Нужно реализовать класс Ord для твоего типа кортежа.
1
Curry
2991 / 2072 / 257
Регистрация: 01.06.2013
Сообщений: 4,525
Записей в блоге: 9
19.01.2018, 23:28 3
Лучший ответ Сообщение было отмечено Bein как решение

Решение

Haskell
1
2
3
4
5
6
7
8
thirdElem :: Ord a => (b,c,a) -> a
thirdElem (_,_,c) = c
 
qsort :: Ord a => [(b,c,a)] -> [(b,c,a)]
qsort [] = []
qsort (h:t) = 
    let third = thirdElem h in
    qsort[x|x<-t, thirdElem x <= third]++[h]++qsort[x|x<-t, thirdElem x > third]
Добавлено через 15 минут
Можем написать промежуточную, более универсальную функцию
Haskell
1
2
3
4
5
6
7
8
9
10
11
thirdElem :: Ord a => (b,c,a) -> a
thirdElem (_,_,c) = c
 
qsortF :: Ord a => (b -> a) -> [b] -> [b]
qsortF _ [] = []
qsortF f (h:t) = 
    let hv = f h in
    qsortF f [x|x<-t, f x <= hv] ++ [h] ++ qsortF f [x|x<-t, f x > hv]
 
qsort :: Ord a => [(b,c,a)] -> [(b,c,a)]
qsort = qsortF thirdElem
2
korvin_
2747 / 2019 / 364
Регистрация: 28.04.2012
Сообщений: 6,889
20.01.2018, 00:56 4
М-да, не ожидал, что Ord для (a,b,c) уже определён в GHC.Classes

Ну, как по мне, так лучше определить свой тип, хотя бы тупо врапнуть кортеж (а лучше сразу запись с полями, для информативности) и определить для него Ord. Проще будет ипользовать в предопределённых функциях.

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
qsort [] = []
qsort (h:t) = 
    qsort [x | x <- t, x <= h] ++ [h] ++ qsort [x | x <- t, x > h]
 
data Foo = Foo (Char, Char, Int) deriving (Eq, Show)
 
data Bar = Bar {
    ch1 :: Char,
    ch2 :: Char,
    ord :: Int
} deriving (Eq, Show)
 
instance Ord Foo where
    compare (Foo (_, _, x)) (Foo (_, _, y)) = compare x y
 
instance Ord Bar where
    compare (Bar _ _ x) (Bar _ _ y) = compare x y
 
testDataFoo = [Foo ('d', 'k', 21), Foo ('a', 'b', 1), Foo ('x', 'y', 34)]
testDataBar = [Bar 'd' 'k' 21, Bar 'a' 'b' 1, Bar 'x' 'y' 34]
 
main = do
    print $ qsort testDataFoo
    print $ qsort testDataBar
https://ideone.com/MFXUZf

Код
[Foo ('a','b',1),Foo ('d','k',21),Foo ('x','y',34)]
[Bar {ch1 = 'a', ch2 = 'b', ord = 1},Bar {ch1 = 'd', ch2 = 'k', ord = 21},Bar {ch1 = 'x', ch2 = 'y', ord = 34}]
1
Bein
0 / 0 / 0
Регистрация: 17.09.2016
Сообщений: 99
20.01.2018, 11:38  [ТС] 5
KolodeznyDiver, поясните. пожалуйста, что происходит в этом коде. А именно, что такое Ord в 1 и 3 строке кода?

Haskell
1
2
3
4
5
6
7
8
thirdElem :: Ord a => (b,c,a) -> a
thirdElem (_,_,c) = c
 
qsort :: Ord a => [(b,c,a)] -> [(b,c,a)]
qsort [] = []
qsort (h:t) = 
    let third = thirdElem h in
    qsort[x|x<-t, thirdElem x <= third]++[h]++qsort[x|x<-t, thirdElem x > third]
0
Curry
2991 / 2072 / 257
Регистрация: 01.06.2013
Сообщений: 4,525
Записей в блоге: 9
20.01.2018, 12:28 6
Цитата Сообщение от Bein Посмотреть сообщение
что такое Ord в 1 и 3 строке кода
Ord - класс типов, т.е. набор функций реализуемых отдельно для разных типов, и, в данном случае, относящихся к сравнению значений одного типа между собой
Haskell
1
2
3
4
5
6
7
8
class Eq a => Ord a where
  compare :: a -> a -> Ordering
  (<) :: a -> a -> Bool
  (<=) :: a -> a -> Bool
  (>) :: a -> a -> Bool
  (>=) :: a -> a -> Bool
  max :: a -> a -> a
  min :: a -> a -> a
Eq - это тоже класс типов.
Haskell
1
2
3
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
Если мы реализуем функции из Ord для нашего типа (говорят реализуем экземпляр (instance) класса типов для типа), то нужно сделать и instance Eq для этого типа. Для большинства стандартных типов (Int,Double,Char) экземпляры Eq, Ord уже реализованы. Для созданных нами типов компилятор часто может сделать (вывести) реализации этих и других стандартных классов типов если указать deriving.
В описании функций, например,
Haskell
1
qsort :: Ord a => [(b,c,a)] -> [(b,c,a)]
Ord a => означает что для типа третьего элемента кортежа должен быть реализован класс типов Ord (а значит и Eq). Тип может быть любой, но вот с таким ограничением потому что внутри функции будут вызываться (<=) и (>) для третьего элемента кортежа, и нужно знать, функции от какого instance Ord подставить. Что же касательно функции thirdElem, то для неё я это ограничение написал зря, она не обращается к функциям из Ord.
1
20.01.2018, 12:28
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.01.2018, 12:28

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

Нужно написать полную быструю сортировку!!!
Нужно написать полную быструю сортировку, т.е. из массива{3, 10, 2, 5, 1, 8} взять любое число и...

Как вставить счетчик в быструю сортировку?
нужно написать счетчик, какой определяет кол-во перестановок и сравнений в быстрой сортировке ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.