VPF::[Haskell] Сортировка списка случайных чисел

110393

Дата 20.3.2011, 01:33 (ссылка)

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

Загрузка ...

Новичок

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

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

Здравствуйте.
Помогите пожалуйста в решении следующей задачи: написать программу, которая сортирует(в порядке возрастания) список случайно сгенерированных чисел. При этом, в функцию вводится только размер списка(т.е. количество чисел), например sortRandom 15 - генерирует и тут же сортирует 15 случайных чисел. Сортировать нужно с помощью quick sort, merge sort, insert sort, bubble sort и selection sort.

Коды, необходимые в решении прикрепляю ниже

функция-генератор случайного списка:

Код


rl :: Int -> [Int]
rl size  = take size randSeq

nextRand :: Int -> Int
nextRand n = (multiplier * n + increment) `mod` modulus

randSeq :: [Int]
randSeq  = iterate nextRand seed

seed :: Int
multiplier :: Int
increment :: Int
modulus :: Int

seed        = 17489
multiplier  = 25173
increment   = 13849
modulus     = 65536

quick sort:

Код


qsort []      = []
qsort (p:xs)  = qsort xs1  ++  [p]  ++  qsort xs2
                where  xs1 = [x | x <- xs, x <= p] 
                       xs2 = [x | x <- xs, x > p]

insert sort:

Код


isort :: [Int] -> [Int]
isort [] = []
isort (x:xs) = insert x (isort xs)

insert :: Int -> [Int] -> [Int]
insert x [] = [x]
insert x (y:ys)
    |x <= y    = x:y:ys
    |otherwise = y:(insert x ys)

merge sort:

Код


msort :: [Int] -> [Int]
msort []   =   []
msort [x]  =   [x]
msort xs   =   merge (msort xs1)  (msort xs2)
           where xs1 = take k xs
                 xs2 = drop k xs
                k   = length xs `div` 2 

merge :: [Int] -> [Int] -> [Int] 
merge [] xs     =   xs
merge xs []     =   xs
merge (x:xs) (y:ys)
      |x <= y       = x : merge xs (y:ys)
      |otherwise   = y : merge (x:xs) ys

selection sort

Код


ssort :: [Int] -> [Int]
ssort [] = []
ssort xs = m : ssort (delete m xs)
       where m = minimum xs

delete :: Eq a => a -> [a] -> [a]
delete deleted xs = [ x | x <- xs, x /= deleted ]

bubble sort:

Код


bsort :: [Int] -> [Int]
bsort []        = []
bsort [x]        = [x]
bsort xs        = bsort zs ++[m]
   where ys        = bpass xs
         (m:ws)        = reverse ys
         zs        = reverse ws
 
bpass :: [Int] -> [Int]
bpass [x]        = [x]
bpass (x:y:rest)
    | x <= y    = x:bpass(y:rest)
    | otherwise    = y:bpass(x:rest)a

Заранее спасибо за любую помощь

Это сообщение отредактировал(а) 110393 - 20.3.2011, 01:36

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »