Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/15: Рейтинг темы: голосов - 15, средняя оценка - 4.80
АРТЕ
0 / 0 / 0
Регистрация: 09.11.2014
Сообщений: 134
#1

Быстрая сортировка (сортировка методом Хоара)

29.03.2015, 14:11. Просмотров 2686. Ответов 13
Метки нет (Все метки)

Ввести массив x1,x2,...,x20 в диапазоне [-10; 10]. Требуется расположить отрицательные элементы в порядке убывания. Вывести массивы до и после сортировки. Сортировка Методом Хоара(Быстрая сортировка)

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.03.2015, 14:11
Ответы с готовыми решениями:

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива
Мне нужно отсортировать фрагмент массива, расположенный между первым и...

Быстрая сортировка (сортировка Хоара) для связных списков
есть у кого готовый алгоритм? или подскажите как реализовать

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена...

Сортировка Хоара / Быстрая сортировка
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void...

Быстрая сортировка Хоара
Быстрая сортировка Хоара (QSort) разбивает массив в ходе сортировки до ...

13
LaHaH
20 / 20 / 26
Регистрация: 17.03.2015
Сообщений: 119
Завершенные тесты: 2
29.03.2015, 14:40 #2
Лучший ответ Сообщение было отмечено АРТЕ как решение

Решение

Добрый день.
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
#include <iostream>
#include <ctime>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
 
typedef vector<int>::iterator vecIt;
 
 
void main()
{
    srand(time(NULL));
    const int N=20;
    vector<int> mass(N);
 
    for (vecIt i = mass.begin(); i != mass.end(); i++)
    {
        *i=-10+rand()%20;
        cout<<*i<<" ";
    }
    cout<<endl;
    sort(mass.begin(),mass.end());
    vecIt it=mass.begin();
    do
    {
        it++;
    } while (*it<0 || it==mass.end());
    sort(mass.begin(),it,greater<int>());
    for (vecIt i = mass.begin(); i != mass.end(); i++)
    {
        cout<<*i<<" ";
    }
    cout<<endl;
 
}
Добавлено через 1 минуту
Тут я сделал случайное заполнение массива, если необходимо, его можно переписать на ручное заполнение.
0
АРТЕ
0 / 0 / 0
Регистрация: 09.11.2014
Сообщений: 134
29.03.2015, 15:28  [ТС] #3
Спасибо большое)
Сделал программу, которая выводит меню,где просят выбрать 5 вариантов.
1.сортировка методом «пузырька»
2. сортировка выбором
3. сортировка вставкой
4.сортировка методом Хоара
5.Выход
Как можно в нее внести вашу программу с быстрой сортировкой?Помогите пожалуйста.
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
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "time.h"
#include "stdlib.h"
#include "iostream"
int _tmain(int argc, _TCHAR* argv[])
{
using namespace std;
    int a[20],b[20],c[20],d[20];
int n,i,k,z;
int loop;
int choice;
srand(time(NULL));
    
loop=1;
printf("massiv: ");
printf("\n");
printf("\n");
for ( i=0; i<20; i++)
{
a[i]=rand()%20-10; 
printf("%d",a[i]);printf(" ");
}
printf("\n");
 
for ( i=0; i<20; i++)
{
    if (a[i]<0) b[i]=0; 
    else
        b[i]=1; 
    
}
 
k=0;
 
for ( i=0; i<20; i++)
{
    if (a[i]<0)
    {c[k]=a[i];k++;}
    
     
}
 
while(loop)
{
    printf("\nVvedite nomer deistvia:\n");
    printf("\n");
    printf("1.Sortirowka puzirkom\n2.Sortirowka viborom");
    printf("\n3.Sortirowka vstavkoi\n4.Sortirowka metodom Hoara");
    printf("\n5.EXIT\n");
    scanf("%d",&choice);
 
if(choice==1) {  
  for (int z =k-1; z>=0; z--)
  {
    for (int j = 0; j < z; j++)
    {
      if (c[j] < c[j+1])
    {
        int tmp = c[j];
        c[j] = c[j + 1];
        c[j + 1] = tmp; 
      }
    }
  }
     
z=0;
 
for ( i=0; i<20; i++)
{
    if (b[i]==0) {d[i]=c[z];z++;}
    else d[i]=a[i];
    printf("%d",d[i]);printf(" ");
}}
 
 
else 
if(choice==2) {  
    for (int z = 0; z < k; z++) {
        int min_z = z;
        for (int j = z + 1; j < k; j++) {
        if (c[j] > c[min_z]) {
            min_z = j;
        }} 
        int temp = c[z];
    c[z] = c[min_z];
    c[min_z] = temp; 
    
}  
 
 
 
z=0;
for ( i=0; i<20; i++)
{
    if (b[i]==0) {d[i]=c[z];z++;}
    else d[i]=a[i];
    printf("%d",d[i]);printf(" ");
}}
 
 
 
 
else
if(choice==3) {  
    for (int z = 1; z < k; z++)
{
   int temp = c[z];
    for (int j = z - 1; j >= 0; j--)
    {
        if (c[j] > temp)
            break;
 
       c[j + 1] = c[j];
        c[j] = temp;
    }}
    
    z=0;
for ( i=0; i<20; i++)
{
    if (b[i]==0) {d[i]=c[z];z++;}
    else d[i]=a[i];
    printf("%d",d[i]);printf(" ");}
}
else
if(choice==4) { ?????????????????????????????????????
else
{
    printf("neverni  gfjh vibor");}}
 
getch();
 
 
    return 0;
}
0
LaHaH
29.03.2015, 16:17
  #4

Не по теме:

Сейчас посмотрю что можно сделать.

0
АРТЕ
0 / 0 / 0
Регистрация: 09.11.2014
Сообщений: 134
29.03.2015, 16:30  [ТС] #5
Вот попытался:
Но кажись что-то не то...Подредактируйте пожалуйста:
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
155
156
157
158
159
160
161
162
163
164
165
166
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "time.h"
#include "stdlib.h"
#include "iostream"
 
using namespace std;
int z, c[100]; //n - количество элементов
void qs(int* c, int first, int last)
{
    int i = first, j = last, x = c[(first + last) / 2];
 
    do {
        while (c[i] < x) i++;
        while (c[j] > x) j--;
 
        if(i <= j) {
            if (c[i] <c[j]) { int temp = c[i]; c[i] = c[j]; c[j] = temp; }
            i++;
            j--;
        }
    } while (i <= j);
  
    if (i < last)
        qs(c, i, last);
    if (first < j)
        qs(c, first, j);
}
 
int _tmain(int argc, _TCHAR* argv[])
{
using namespace std;
int a[20],b[20],c[20],d[20];
int n,i,k,z;
int loop;
int choice;
srand(time(NULL));
 
loop=1;
printf("massiv: ");
printf("\n");
printf("\n");
for ( i=0; i<20; i++)
{
a[i]=rand()%20-10; 
printf("%d",a[i]);printf(" ");
}
printf("\n");
 
for ( i=0; i<20; i++)
{
if (a[i]<0) b[i]=0; 
else
b[i]=1; 
 
}
 
k=0;
 
for ( i=0; i<20; i++)
{
if (a[i]<0)
{c[k]=a[i];k++;}
 
 
}
 
while(loop)
{
printf("\nVvedite nomer deistvia:\n");
printf("\n");
printf("1.Sortirowka puzirkom\n2.Sortirowka viborom");
printf("\n3.Sortirowka vstavkoi\n4.Sortirowka metodom Hoara");
printf("\n5.EXIT\n");
scanf("%d",&choice);
 
if(choice==1) { 
for (int z =k-1; z>=0; z--)
{
for (int j = 0; j < z; j++)
{
if (c[j] < c[j+1])
{
int tmp = c[j];
c[j] = c[j + 1];
c[j + 1] = tmp; 
}
}
}
 
z=0;
 
for ( i=0; i<20; i++)
{
if (b[i]==0) {d[i]=c[z];z++;}
else d[i]=a[i];
printf("%d",d[i]);printf(" ");
}}
 
 
else 
if(choice==2) { 
for (int z = 0; z < k; z++) {
int min_z = z;
for (int j = z + 1; j < k; j++) {
if (c[j] > c[min_z]) {
min_z = j;
}} 
int temp = c[z];
c[z] = c[min_z];
c[min_z] = temp; 
 
} 
 
 
 
z=0;
for ( i=0; i<20; i++)
{
if (b[i]==0) {d[i]=c[z];z++;}
else d[i]=a[i];
printf("%d",d[i]);printf(" ");
}}
 
 
 
 
else
if(choice==3) { 
for (int z = 1; z < k; z++)
{
int temp = c[z];
for (int j = z - 1; j >= 0; j--)
{
if (c[j] > temp)
break;
 
c[j + 1] = c[j];
c[j] = temp;
}}
 
z=0;
for ( i=0; i<20; i++)
{
if (b[i]==0) {d[i]=c[z];z++;}
else d[i]=a[i];
printf("%d",d[i]);printf(" ");}
}
 
else 
    if(choice==4) { qs(c, 0, z-1);
 
    
}
 
 
else
{
printf("neverni gfjh vibor");}}
 
getch();
 
 
return 0;
}
0
LaHaH
20 / 20 / 26
Регистрация: 17.03.2015
Сообщений: 119
Завершенные тесты: 2
29.03.2015, 17:02 #6
Лучший ответ Сообщение было отмечено АРТЕ как решение

Решение

У меня вопрос. Вам нельзя использовать STL?

Добавлено через 47 секунд
Просто, если нельзя, то надо переделывать мою программу.
1
АРТЕ
0 / 0 / 0
Регистрация: 09.11.2014
Сообщений: 134
29.03.2015, 17:20  [ТС] #7
Да, к сожалению нельзя.
0
LaHaH
20 / 20 / 26
Регистрация: 17.03.2015
Сообщений: 119
Завершенные тесты: 2
29.03.2015, 17:45 #8
Не хочу расстраивать, но по моему, у Вас вся программа не правильно работает.
Быстрая сортировка (сортировка методом Хоара)
0
АРТЕ
0 / 0 / 0
Регистрация: 09.11.2014
Сообщений: 134
29.03.2015, 17:56  [ТС] #9
Сейчас объясню.Программа должна сортировать только отрицательные числа в порядке убывания, а потом расставлять их в начальном массиве на те места где были отрицательные числа(простите за ужасное объяснение).
Допустим у нас массив -5 3 -1 -9 4 1 , мы сортируем отрицательные -1 -5 -9 и затем вставляем их обратно в массив на места отрицательных, получается -1 3 -5 -9 4 1
Тоесть сначала мы запоминаем все места где были отрицательные числа(создаем массив, где 0-отрицательные числа, а 1-положительные), затем делаем массив только с отрицательными числами, сортируем его и вписываем обратно в начальный массив.(Ставим вместо 0 отсортированные числа, а вместо 1 начальные).
А у меня просто не получается занести в функцию с быстрой сортировкой отрицательные числа, отсортировать их, и вывести на экран(чтоб посмотреть правильно ли работает сортировка), а затем вписать вместо нулей. Собственно в этом то вся проблема.
0
LaHaH
20 / 20 / 26
Регистрация: 17.03.2015
Сообщений: 119
Завершенные тесты: 2
29.03.2015, 18:48 #10
А, ну тогда все в разы проще

Вот код сортировки.
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
void QuickSort(int *array, int left, int right)
{
    long base, opposite, p;
    int c;
    base=left;
    opposite=right;
    while (base!=opposite){
        if ((array[base]>array[opposite])^(base>opposite)){
 
            c=array[base];
            array[base]=array[opposite];
            array[opposite]=c;
 
            p=base;
            base=opposite;
            if (p<opposite)
                opposite=p+1; else opposite=p-1;
        } else {
            if (base<opposite)
                opposite--; else opposite++;
        };
    };
 
    if (left<base-1) QuickSort(array,left,base-1);
    if (base+1<right) QuickSort(array,base+1,right);
};
Вызывается он следующим образом:
C++
1
2
3
4
5
6
7
8
9
10
 QuickSort( c,  0,  k-1);
 
 for (int i = 0,k=0; i < 20; i++)
 {
     if (b[i]==0)
     {
         a[i]=c[k];
         k++;
     }
 }
0
АРТЕ
0 / 0 / 0
Регистрация: 09.11.2014
Сообщений: 134
29.03.2015, 19:20  [ТС] #11
Спасибо большое
Вот вроде все подставил,но не выводит(
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "time.h"
#include "stdlib.h"
#include "iostream"
 
using namespace std;
int z, c[100]; //n - количество элементов
void QuickSort(int *array, int left, int right)
{
    long base, opposite, p;
    int c;
    base=left; 
    opposite=right;
    while (base!=opposite){
        if ((array[base]>array[opposite])^(base>opposite)){
 
            c=array[base];
            array[base]=array[opposite];
            array[opposite]=c; 
 
            p=base;
            base=opposite;
            if (p<opposite) 
                opposite=p+1; else opposite=p-1;
        } else {
            if (base<opposite)
                opposite--; else opposite++; 
        };
    };
 
    if (left<base-1) QuickSort(array,left,base-1); 
    if (base+1<right) QuickSort(array,base+1,right); 
};
 
int _tmain(int argc, _TCHAR* argv[])
{
using namespace std;
int a[20],b[20],c[20],d[20];
int n,i,k,z;
int loop;
int choice;
srand(time(NULL));
 
loop=1;
printf("massiv: ");
printf("\n");
printf("\n");
for ( i=0; i<20; i++)
{
a[i]=rand()%20-10; 
printf("%d",a[i]);printf(" ");
}
printf("\n");
 
for ( i=0; i<20; i++)
{
if (a[i]<0) b[i]=0; 
else
b[i]=1; 
 
}
 
k=0;
 
for ( i=0; i<20; i++)
{
if (a[i]<0)
{c[k]=a[i];k++;}
 
 
}
 
while(loop)
{
printf("\nVvedite nomer deistvia:\n");
printf("\n");
printf("1.Sortirowka puzirkom\n2.Sortirowka viborom");
printf("\n3.Sortirowka vstavkoi\n4.Sortirowka metodom Hoara");
printf("\n5.EXIT\n");
scanf("%d",&choice);
 
if(choice==1) { 
for (int z =k-1; z>=0; z--)
{
for (int j = 0; j < z; j++)
{
if (c[j] < c[j+1])
{
int tmp = c[j];
c[j] = c[j + 1];
c[j + 1] = tmp; 
}
}
}
 
z=0;
 
for ( i=0; i<20; i++)
{
if (b[i]==0) {d[i]=c[z];z++;}
else d[i]=a[i];
printf("%d",d[i]);printf(" ");
}}
 
 
else 
if(choice==2) { 
for (int z = 0; z < k; z++) {
int min_z = z;
for (int j = z + 1; j < k; j++) {
if (c[j] > c[min_z]) {
min_z = j;
}} 
int temp = c[z];
c[z] = c[min_z];
c[min_z] = temp; 
 
} 
z=0;
for ( i=0; i<20; i++)
{
if (b[i]==0) {d[i]=c[z];z++;}
else d[i]=a[i];
printf("%d",d[i]);printf(" ");
}}
 
 
 
 
else
if(choice==3) { 
for (int z = 1; z < k; z++)
{
int temp = c[z];
for (int j = z - 1; j >= 0; j--)
{
if (c[j] > temp)
break;
 
c[j + 1] = c[j];
c[j] = temp;
}}
 
z=0;
for ( i=0; i<20; i++)
{
if (b[i]==0) {d[i]=c[z];z++;}
else d[i]=a[i];
printf("%d",d[i]);printf(" ");}
}
 
else 
    if(choice==4) { QuickSort( c,  0,  k-1);
 
 for (int i = 0,k=0; i < 20; i++)
 {
     if (b[i]==0)
     {
         a[i]=c[k];
         k++;
     }
 }
}
 
else 
{
printf("neverni vibor");}}
 
getch();
 
 
return 0;
}
0
LaHaH
20 / 20 / 26
Регистрация: 17.03.2015
Сообщений: 119
Завершенные тесты: 2
29.03.2015, 19:27 #12
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 QuickSort( c,  0,  k-1);
 
 for (int i = 0,k=0; i < 20; i++)
 {
     if (b[i]==0)
     {
         a[i]=c[k];
         k++;
     }
 }
for ( i=0; i<20; i++)
{
cout<<a[i]<<" ";   
}
Вот так добавьте
1
АРТЕ
0 / 0 / 0
Регистрация: 09.11.2014
Сообщений: 134
29.03.2015, 19:47  [ТС] #13
Спасибо вам огромно, вы меня спасаете)
0
LaHaH
29.03.2015, 20:04     Быстрая сортировка (сортировка методом Хоара)
  #14

Не по теме:

Удачи Вам!:)

0
29.03.2015, 20:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.03.2015, 20:04
Привет! Вот еще темы с ответами:

Быстрая сортировка Хоара без рекурсивных функций
Здравствуйте мне нужно написать быстрою сортировку Хоара но без рекурсивных...

Сортировка методом Хоара
Дали задание 1. Пусть дано массив a1, a2, ..., an. Необходимо переставить его...

Сортировка методом Хоара
Здраствуйте помогите пожалуйста с программой не могу запрограммировать...


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

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

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