Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 5.00
warspirit
3 / 3 / 0
Регистрация: 30.03.2011
Сообщений: 61
#1

Шейкерная сортировка + сортировка слиянием - C++

22.10.2012, 22:42. Просмотров 1591. Ответов 3
Метки нет (Все метки)

вот часть когда,которая выполняет шейкерную сортировку : для символьного и целочисленого массива .
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
// ConsoleApplication15.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include<iostream>
#include<conio.h>
 
#pragma hdrstop
using namespace std;
 
// функция сравнения:
bool compare_less(int Left, int Right)
{
    if (Left<Right)
        return true;
    else
        return false;   
}
 
 
void Swap(int Arr[], int i) //Поменять местами i-й и i-1-й элементы массива Arr
{
    int temp;       //буфер
    temp = Arr[i];
    Arr[i] = Arr[i-1];
    Arr[i-1] = temp;
}
void Swap(char Arr[], int i) // перестановка для  символьного массива
 
{
    int temp;       //буфер
    temp = Arr[i];
    Arr[i] = Arr[i-1];
    Arr[i-1] = temp;
}
 
void ShakerSort(int Arr[], int Start, int N)
{
    int Left,Right; //границы сортировки
    int Last;       //место последней перестановки
 
    Left=Start;
    Right = N-1;
    Last = N-1;
 
    do
    {
        //Сдвигаем к концу массива "легкие элементы"
        for (int i =Right; i >= Left; i--)
        {
            if (Arr[i-1]>Arr[i])
            {
                Swap(Arr, i);
                Last = i; //Запомнить место последней перестановки
            }
        }
 
        Left = Last + 1;
 
        //Сдвигаем к началу массива "тяжелые элементы"
        for (int i =Left; i <= Right; i++)
        {
            if (Arr[i-1]>Arr[i])
            {
                Swap(Arr, i);
                Last = i; //Запомнить место последней перестановки
            }
        }
 
        Right = Last - 1;
    }
    while (compare_less( Left, Right));
}
 
void ShakerSort(char Arr[], int Start, int N) // сортировка символьного массива
 
{
    int Left,Right; //границы сортировки
    int Last;       //место последней перестановки
 
    Left=Start;
    Right = N-1;
    Last = N-1;
 
    do
    {
        //Сдвигаем к концу массива "легкие элементы"
        for (int i =Right; i >= Left; i--)
        {
            if (Arr[i-1]>Arr[i])
            {
                Swap(Arr, i);
                Last = i; //Запомнить место последней перестановки
            }
        }
 
        Left = Last + 1;
 
        //Сдвигаем к началу массива "тяжелые элементы"
        for (int i =Left; i <= Right; i++)
        {
            if (Arr[i-1]>Arr[i])
            {
                Swap(Arr, i);
                Last = i; //Запомнить место последней перестановки
            }
        }
 
        Right = Last - 1;
    }
    while (compare_less( Left, Right));
} 
 
 
void ArrayOutput(int* Arr, int Start, int N) //Вывод элементов массива на консоль
{
    for (int i = 0; i < N; i++)
    {
        cout << Arr[i] << " ";
    }
    
}
void ArrayOutput(char* Arr, int Start, int N) //Вывод элементов символьного массива на консоль
{
    for (int i = 0; i < N; i++)
    {
        cout << Arr[i] << " ";
    }
    
}
 
 
 
int main(int argc, TCHAR* argv[])
{
    const int Count = 10;
    int TestArr[Count] = {9,8,7,6,5,4,3,2,1,0};
 
    int TestArr_2[Count] = {-9,-8,-7,16,15,-4,-3,20,12,11};
    
    const int Count_C=11;
    char TestArr_C[Count_C] = {"baecfdighl"};
 
    ShakerSort(TestArr,0,Count);
    ShakerSort(TestArr_C,0,Count_C);
 
 
    ArrayOutput(TestArr,0,Count);
    cout<<'\n';
    ArrayOutput(TestArr_C,0,Count_C);
    cout<<'\n';
 
    return 0;
}
Помогите написать функцию ,для сортировки слиянием для двух массивов.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.10.2012, 22:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Шейкерная сортировка + сортировка слиянием (C++):

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include &lt;iostream&gt; ...

2 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....

Шейкерная сортировка массива - C++
Не удается с внизсходящего поменять сортировку на вверхсходящую #include &lt;iostream&gt; #include &lt;windows.h&gt; #include &lt;time.h&gt; ...

Шейкерная сортировка двусвязного списка - C++
Здравствуйте! У меня возникла проблема с сортировкой двусвязного списка. Получилось реализовать двусвязный список и отдельно...

Шейкерная сортировка без использования while цикла - C++
Ребят, сделал шейкерную сортировку через два вложенных цикла - не работает. Не могу понять в чем проблема, подскажите пожалуйста. ...

Шейкерная сортировка массива (в виде функции) - C++
Выполнить сортировку целочисленного массива(поиск в массиве) из n элементов. Алгоритм сортировки(поиска) Шейкер-сортировка, оформить в виде...

3
alexcoder
1546 / 691 / 90
Регистрация: 03.06.2009
Сообщений: 3,663
Завершенные тесты: 1
23.10.2012, 09:42 #2
В гугле забанили?
Сортировка слиянием С++
http://algolist.manual.ru/sort/merge_sort.php
0
warspirit
3 / 3 / 0
Регистрация: 30.03.2011
Сообщений: 61
23.10.2012, 12:58  [ТС] #3
Цитата Сообщение от alexcoder Посмотреть сообщение
1 ссылка программа там выполнена,записью в результирующий массив двух предыдущих и после сортируеться.

Я же прошу к выше написанной программе ,написать или обьяснить,как реализовать вот такой алгоритм
" 1.3.5.3 Сортировка слиянием
В данном методе мы предположим существование двух массивов, каждый из которых уже отсортирован по возрастанию. Цель состоит в том, что необходимо “слить” эти два массива (назовем их A, B) в результирующий (C) так, чтобы этот третий массив был отсортирован по возрастанию. Алгоритм данного метода может быть кратко изложен так:
1) необходимо взять из каждого из массивов самый первый элемент (очевидно, что это два самых маленьких элемента, которые вообще есть в наших двух массивах) и наименьший из них поместить в результирующий.
2) в том массиве, откуда мы изъяли один элемент, предположить, что первым будет тот, который находился ранее на второй позиции, по сути мы сдвигаем элементы на одну позицию влево.
3) необходимо повторять шаги 1,2 до тех пор, пока в каком-либо из массивов не закончатся числа.
Предположим, что это был массив A.
4) в результирующий массив C необходимо поместить все оставшиеся из массива В.
"
0
nonedark2008
931 / 670 / 147
Регистрация: 28.07.2012
Сообщений: 1,827
23.10.2012, 13:30 #4
Тырнул из своих старых исходников:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template< class T >
  VOID MergeSort( T *a, INT n )
  {
    if (n == 1)
      return ;
    INT i = n / 2;
    MergeSort(a, i);
    MergeSort(a + i, n - i);
 
    T *a1 = a;
    T *a2 = a + i;
    INT n1 = i, n2 = n - i;
     T *bulk = new T[n1 + n2];
    INT j = 0, k = 0, inc = 0;
    while (j < n1 && k < n2)
      if (a1[j] < a2[k])
        bulk[inc++] = a1[j++];
      else
        bulk[inc++] = a2[k++];
    if (j < n1)
      memcpy(bulk + inc, a1 + j, (n1 - j) * sizeof(INT));
    else if (k < n2)
      memcpy(bulk + inc, a2 + k, (n2 - k) * sizeof(INT));
    memcpy(a1, bulk, (n1 + n2) * sizeof(INT));
    delete[] bulk;
  }
template можно убрать, T заменить на тип массива - все будет работать. У нас есть изначально один массив, который разделяется на два подмассива(что и надо), которые опятьже сортируются...

Добавлено через 1 минуту
Нижняя часть как раз и ответственна за сливание вместе...
0
23.10.2012, 13:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.10.2012, 13:30
Привет! Вот еще темы с ответами:

Сортировка слиянием - C++
Всем доброго время суток, дана задача: Требуется упорядочить элементы некоторого массива целых чисел, который следует упорядочить по...

Сортировка слиянием - C++
Требуется отсортировать слиянием массив структур. По одному из элемерту структуры. Вторая ночь без сна, не могу понять даже реализацию...

Сортировка слиянием - C++
Здравствуйте, изучая сортировку, в интернете наткнулся на код сортировки слиянием. int a; void merge(int,int,int); void...

Сортировка слиянием - C++
На лабороторной задали написать сортировку массива слиянием, рабочую версию реализовать удалось, только вот она жрёт лишнюю память, которая...


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

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

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