Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Различные методы сортировки(С++)  (Прочитано 17012 раз)
0 Пользователей и 1 Гость смотрят эту тему.
demonhunterus
Интересующийся

ua
Offline Offline

« : 10-12-2010 13:35 » 

Добрый день.Я столкнулся с необходимостью освоить некоторые методы сортировки,такие как Быстрая сортировка,Сортировка Слиянием,Пирамидальная Сортировка и Порязрядная Сортировка.
И,если с первой всё понятно,то с другими не всё так прозрачно.Прошу помочь разобраться в некоторых кусочках кодов,реализующих данные методы сортировки.
Сортировка Слиянием
Код:
#include <iostream>
#include <conio.h>
using namespace std;
template <class T>
T* merge(T *m1, T* m2, int l1, int l2){
    T* ret = new T[l1+l2];
    int n = 0;
    // Сливаем массивы, пока один не закончится
    while (l1 && l2){
        if (*m1 < *m2){
           ret[n] = *m1;
           m1++; l1--;}
        else {
           ret[n] = *m2;
           m2++; l2--;}
       n++;}
    // Если закончился первый массив
    if (l1 == 0){
        for (int i=0; i<l2; i++){
            ret[n++] = *m2++;}}
    // Если закончился второй массив
    else {
        for (int i=0; i<l1; i++){
           ret[n++] = *m1++;}}
    return ret;}
 
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len){
    int n=1, l, ost;
    T * mas1;
    while (n<len){
        l=0;
        while (l<len){
           if (l+n >= len) break;
           ost = (l+n*2>len) ? (len-(l+n)) : n;
           mas1 = merge(mas+l, mas+l+n, n, ost);
           for (int i=0; i<n+ost; i++) mas[l+i] = mas1[i];
           delete [] mas1;
           l+=n*2;}
       n*=2;
}}
 
int main()
{
    float a[128];int dl;
    cout<<"Vvedite coli4estvo 4lenov v massive\n";
    cin>>dl;
    cout<<"Vvedite massiv\n";
    for(int i=0;i<dl;i++)
    {    cin>>a[i];}
   
    mergeSort(a, dl);
    for(int i=0;i<dl;i++)
        cout<<" "<<a[i];
            system("PAUSE");
    getch();
}
Непонятна функция mergeSort,а именно что за переменные такие l,n,ost и len.

Пирамидальная Сортировка
Код:
#include <iostream>
using namespace std;
 
template<typename T>
void downHeap(T a[], long k, long n) {
        //  процедура просеивания следующего элемента
        //  До процедуры: a[k+1]...a[n]  - пирамида
        //  После:  a[k]...a[n]  - пирамида
        T new_elem;
        long child;
        new_elem = a[k];
 
        while(k <= n/2) {               // пока у a[k] есть дети
                child = 2*k;
                //  выбираем большего сына
                if( child < n && a[child] < a[child+1] )
                        child++;
                if( new_elem >= a[child] ) break;
                // иначе
                a[k] = a[child];        // переносим сына наверх
                k = child;
        }
        a[k] = new_elem;
}
 
template<typename T>
void heapSort(T a[], long size) {
        long i;
        T temp;
 
        // строим пирамиду
        for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);
 
        // теперь a[0]...a[size-1] пирамида
 
        for(i=size-1; i > 0; i--) {
                // меняем первый с последним
                temp=a[i]; a[i]=a[0]; a[0]=temp;
                // восстанавливаем пирамидальность a[0]...a[i-1]
                downHeap(a, 0, i-1);
        }
}
int main()
{
 
        int arr[5] = {9,2,3,1,5};
        heapSort(arr,5);
 
        cout<<"[ ";
        for(int i = 0; i < 5; ++i)
                cout<<arr[i]<<" ";
        cout<<"]"<<endl;
        system("PAUSE");
        return 0;

}
Здесь непонятна DownHeap,а конкретно,что с чем сравнивается в if'ах и почему child = 2*k.

Подскажите,пожалуйста,что к чему...Заранее благодарю!
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 10-12-2010 13:42 » 

Давайте сделаем так.

Сначала почитайте теорию. Например, Кнут, "Искусство программирования, том 3. Сортировка и поиск" или Вирт, "Алгоритмы и структуры данных".

Если после этого что-то останется непонятным, обсудим в этой теме.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #2 : 10-12-2010 14:48 » new

а вот мне жутко интересно, что побуждает людей форматировать код так:
Код:
   if (l1 == 0){
        for (int i=0; i<l2; i++){
            ret[n++] = *m2++;}}

гонимся за минимальным количеством строк ? А как же глаза собеседника ? Ну что, вот так что ли хуже:
Код:
    if(l1==0)
    {
        for(int i=0; i<l2; i++, n++, m2++)
        {
            ret[n] = *m2;
        }
    }
Записан

Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 10-12-2010 18:29 » 

Алексей1153++, может люди к Python привыкли - там же роль играют не скобки, а отступы. На мой взгляд, если отступы соблюдены, текст воспринимается нормально. На скобки я лично смотрю редко.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #4 : 10-12-2010 19:44 » 

Dimka, тут же не питон. Пропустишь скобку - не будет блока Улыбаюсь
Записан

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #5 : 10-12-2010 21:55 » 

Алексей1153++, Есть несколько способов форматирования текста Улыбаюсь В последнее время я лично пишу первым, способом, который ты привел. Этому меня приучил NetBeans. У него такое восприятие мира Улыбаюсь
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 10-12-2010 23:03 » 

Finch, не знаю, кто такой NetBeans, но у меня с этим чуваком одинаковое восприятие мира ))
Записан

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #7 : 13-12-2010 04:25 » 

Кнута можно и не читать, Вика даёт достаточно понятное объяснение
http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8

Код: (C++)
 if(l1==0) {
        for(int i=0; i<l2; i++, n++, m2++)
            ret[n] = *m2;
 }
а можно и вот так
если блок из одной строки, скобки опускаем, если несколько, то первая скобка в строке условия или цикла
Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #8 : 13-12-2010 05:15 » 

Антон (LogRus), ага, только не забыть при таком стиле, что (сли приписали ещё что-то)

        for(int i=0; i<l2; i++, n++, m2++)
            ret[n] = *m2; ещё что-то;

то это ещё-что-то уже будет не в цикле Улыбаюсь


Записан

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #9 : 13-12-2010 12:26 » 

Алексей1153++, я никогда не пишу несколько ; в одной строке, имхо это не читаемо и можно огрести граблей
Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #10 : 13-12-2010 14:44 » 

Антон (LogRus), так ресь же не о тебе, а о demonhunterus , например Улыбаюсь
Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines