Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 5.00
warspirit
3 / 3 / 0
Регистрация: 30.03.2011
Сообщений: 61
22.10.2012, 22:42     шейкерная сортировка + сортировка слиянием #1
вот часть когда,которая выполняет шейкерную сортировку : для символьного и целочисленого массива .
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;
}
Помогите написать функцию ,для сортировки слиянием для двух массивов.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.10.2012, 22:42     шейкерная сортировка + сортировка слиянием
Посмотрите здесь:

C++ Сортировка слиянием
Шейкерная сортировка C++
Сортировка слиянием C++
2 сортировки: пирамидальная сортировка и сортировка слиянием C++
Сортировка слиянием C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alexcoder
1438 / 652 / 86
Регистрация: 03.06.2009
Сообщений: 3,295
Завершенные тесты: 1
23.10.2012, 09:42     шейкерная сортировка + сортировка слиянием #2
В гугле забанили?
Сортировка слиянием С++
http://algolist.manual.ru/sort/merge_sort.php
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 необходимо поместить все оставшиеся из массива В.
"
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
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 минуту
Нижняя часть как раз и ответственна за сливание вместе...
Yandex
Объявления
23.10.2012, 13:30     шейкерная сортировка + сортировка слиянием
Ответ Создать тему
Опции темы

Текущее время: 03:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru