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

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

Войти
Регистрация
Восстановить пароль
 
strange_man
9 / 9 / 0
Регистрация: 17.05.2012
Сообщений: 118
#1

Быстрая сортировка - C++

05.01.2013, 22:22. Просмотров 838. Ответов 8
Метки нет (Все метки)

нормальный код? а то третий день парюсь, вроде сейчас получилось
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
void quicksort (int *a, int start, int end)
{
    int point = partition (a, start, end); //вызов функции, которая определит окончательную позицию одного элемента и делит массив на подмассивы
 
    //пока в подмасиве не останется один элемент, делаем рекурсивный вызов
    if (point - start >= 1) 
        quicksort (a, start, point-1);
    if (end - point >= 1)
        quicksort (a, point+1, end);
}
 
int partition (int *a, int start, int end)
{
    int pos = start; //определяем позицию элемента, находящегося первым в неотсортированном подмассиве
    while (1)
    {
        int i = end; //счетчик идет с конца подмассива
 
        while ((a[i] >= a[pos]) && (i > pos))
            i--;
 
        //меняем местами элементы в подмассиве, если нужный нам элемент пока не попал в свою позицию
        if (i != pos)
            swap (a[pos], a[i]); //меняем местами элементы массива
        else
        {
            return pos; //возвращаем номер позиции для последующих рекурсивных вызовов
            break;
        }
 
        pos = i;
        i = start + 1;
 
        //по аналогии с предыдущим действием, но теперь в части подмассива слева от элемента
        while ((a[i] <= a[pos]) && (i < pos))
            i++;
 
        if (i != pos)
            swap (a[pos], a[i]);
        else
        {
            return pos;
            break;
        }
 
        pos = i; 
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2013, 22:22
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрая сортировка (C++):

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

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

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

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

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

Сортировка расчёской и быстрая сортировка - C++
В файле in.txt записана последовательность целых чисел. Заданными методами отсортировать числа и записать в файлы out1.txt и out2.txt....

8
Stanis
52 / 41 / 8
Регистрация: 16.12.2012
Сообщений: 144
06.01.2013, 20:29 #2
Ты это по книге Дейтейлов делаешь ?
0
Igor3D
915 / 514 / 55
Регистрация: 01.10.2012
Сообщений: 2,547
06.01.2013, 20:47 #3
Если исходный массив уже сортирован, то partiton будет все время возвращать start + 1. Не ошибка но работать будет медленно. Можно посмотреть реализацию std::nth_element (но это зрелище не для слабонервных)
0
strange_man
9 / 9 / 0
Регистрация: 17.05.2012
Сообщений: 118
06.01.2013, 21:10  [ТС] #4
Stanis, да, по книге Дейтелов.
0
Stanis
52 / 41 / 8
Регистрация: 16.12.2012
Сообщений: 144
06.01.2013, 21:24 #5
я тоже сегодня пытался написать эту сортировку , весь день . Не понимал как эту функцию partition писать ,
в книге не написано что она должна возвращать номер отсортированного элемента , а сам как то не допер.
В общем пока твой код не увидел не получалось )). Вот сейчас только запустил все работает ) Только
не совсем понимаю момент когда на интервале подмассив начинается не сначала основного массива а
где то в середине и заканчивается не в конце , как программа там что сортирует , ведь мы передаем в
quicksort (начало основного массива ) а не начало подмассива в середине .
0
AlvinMax
0 / 0 / 0
Регистрация: 05.01.2013
Сообщений: 16
06.01.2013, 22:53 #6
Какая сортировка нужна?
0
Владслав
-173 / 0 / 1
Регистрация: 02.12.2012
Сообщений: 27
06.01.2013, 23:07 #7
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
#include<iostream>
using namespace std;
#define N 255
int a[N];
void qSort(int l, int r){
int w,x,i,j;
i=l;
j=r;
x=a[(l+r)/2];
while (i<=j){
   while (a[i]<x) i++; // Индекс i последовательно увеличивается до тех пор, пока i-й элемент не превысит опорный.
   while (x<a[j]) j--; // Индекс j последовательно уменьшается до тех пор, пока j-й элемент не окажется меньше опорной.
   if (i<=j){          // Если i <= j — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений i и j, которые были достигнуты.
       w=a[i]; a[i]=a[j]; a[j]=w;
       i++; j--;
   }
}
if (l<j) qSort(l,j); // Рекурсивно упорядочиваем подмассивы,
if (i<r) qSort(i,r); // лежащие слева и справа от опорного элемента.
}
void main()
{
int i,n;
printf("Enter N: "); cin>>n;
for (i=0; i<n; i++){
    cin>>a[i];
}
printf("\n");
qSort(0,n-1);
for (i=0; i<n; i++){
printf("%d ", a[i]);
}
printf("\n");
}
0
Igor3D
915 / 514 / 55
Регистрация: 01.10.2012
Сообщений: 2,547
07.01.2013, 10:47 #8
Цитата Сообщение от Владслав Посмотреть сообщение
C++
1
2
3
4
x=a[(l+r)/2];
while (i<=j){
   while (a[i]<x) i++; // Индекс i последовательно увеличивается до тех пор, пока i-й элемент не превысит опорный.
}
Если просто "чтобы работало" - то все гуд. А если говорить об оптимальности - то из каких соображений выбран "опорный"? Он может оказаться неудачным, тогда один из новых подмассивов короткий, др длинный.
0
Владслав
-173 / 0 / 1
Регистрация: 02.12.2012
Сообщений: 27
25.01.2013, 23:08 #9
Это не гуд
0
25.01.2013, 23:08
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2013, 23:08
Привет! Вот еще темы с ответами:

Быстрая сортировка - C++
Суть задания состоит в сортировке структуры по второму параметру. Сделал пузырьковым методом: #include &lt;iostream&gt; #include &lt;conio.h&gt;...

Быстрая сортировка - C++
Есть три файла: Функция: #ifndef QUICK #define QUICK #include &lt;vector&gt; using namespace std; template&lt;class...

Быстрая сортировка - C++
Друзья, здравствуйте! Как работает быстрая сортировка - у меня практически вопросов нет: #include &lt;iostream&gt; #include &lt;stdlib.h&gt; ...

Быстрая сортировка - C++
Здравствуйте. Ребята, очень нужна помощь. Есть функция быстрой сортировки, ей надо упорядочить массив из рандомных чисел - строки по...


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

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

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